150621

Ruby


f（i) = 2^i + 3^i + 5^i + 7^i

i が自然数のとき、f(i) が素数になるのはどのようなときか
100以下で調べてみた。

# バイナリ法
def power(a, n)
  return 1 if n == 0
  k = power(a, n >> 1)
  k *= k
  return k if n & 1 == 0
  return k * a
end

=begin
i = 79 のとき素数かどうかで時間がかかる。ちなみにこのとき、
j = 5790887942465741731117612854834794040914070728974646702390797618223
=end
(1..100).each{|i|
  j = power(2, i) + power(3, i) + power(5, i) + power(7, i)
  k = Math.sqrt(j).to_i
  # jは2で割り切れない
  l = 3
  while j % l > 0 && l <= k
    l += 2
  end
  if l <= k
    p [i, l]
  else
    p [i, 'prime', j]
  end
}

出力結果

[1, "prime", 17]

[2, 3]

[3, "prime", 503]

[4, 3]

[5, 11]

[6, 3]

[7, 149]

[8, 3]

[9, 19]

[10, 3]

[11, 13]

[12, 3]

[13, 79]

[14, 3]

[15, 11]

[16, 3]

[17, 17]

[18, 3]

[19, "prime", 11417969834487023]

[20, 3]

[21, 1603919]

[22, 3]

[23, 13]

[24, 3]

[25, 11]

[26, 3]

[27, 19]

[28, 3]

[29, 55313]

[30, 3]

[31, 1901]

[32, 3]

[33, 17]

[34, 3]

[35, 11]

[36, 3]

[37, 149]

[38, 3]

[39, 67]

[40, 3]

[41, 83]

[42, 3]

[43, 47]

[44, 3]

[45, 11]

[46, 3]

[47, 13]

[48, 3]

[49, 17]

[50, 3]

[51, 103]

[52, 3]

[53, 19]

[54, 3]

[55, 11]

[56, 3]

[57, 229]

[58, 3]

[59, 13]

[60, 3]

[61, 139]

[62, 3]

[63, 19]

[64, 3]

[65, 11]

[66, 3]

[67, 2377]

[68, 3]

[69, 101]

[70, 3]

[71, 13]

[72, 3]

[73, 17333]

[74, 3]

[75, 11]

[76, 3]

[77, 23]

[78, 3]

[79, 1483384709]

[80, 3]

[81, 17]

[82, 3]

[83, 13]

[84, 3]

[85, 11]

[86, 3]

[87, 1741]

[88, 3]

[89, 19]

[90, 3]

[91, 79]

[92, 3]

[93, 223]

[94, 3]

[95, 11]

[96, 3]

[97, 17]

[98, 3]

[99, 19]

[100, 3]

以上より、

2 + 3 + 5 + 7 = 17（素数）

2^3 + 3^3 + 5^3 + 7^3 = 503（素数）

2^19 + 3^19 + 5^19 + 7^19 = 11417969834487023（素数）

なお、Prime Curious! の2357のページ（http://primes.utm.edu/curios/page.php/2357.html）には
2^1013 + 3^1013 + 5^1013 + 7^1013 は素数
と載っている。