2が現れる素数という面白い素数が紹介されていた。
2が現れる素数 - INTEGERS
昔せっかく高速素数判定器を作ったので、どうせならNが現れる素数を見つけてやろう!と思い立った。
プログラム
(※プログラムはpython(2.7.12)で動作します)
ルールとしては
①四隅のみの数字を変える(もちろん先頭は1以上の数字)
②四隅の数字はN以外の数字にする
としています。
なので、それぞれ5832(8*9*9*9)個の数字の中から素数を探すことになります。
高速素数判定のプログラム(再掲)
primechecker.pyという名前で保存
import random import numpy as np class PrimeChecker: def __init__(self, list_limit = pow(10,3)): if list_limit < 5: list_limit = 5 self.prime_list = self.set_prime_list(list_limit) self.list_limit = list_limit @staticmethod def set_prime_list(n): def mark(primes,x): for i in xrange(2*x, n+1, x): primes[i-2] = False primes = [(i%2!=0 and i%3!=0 and i%5!=0) for i in range(2,n+1)] primes[0] = primes[1] = primes[3] = True for x in xrange(7, int(np.sqrt(n+1))+1): if primes[x-2]: mark(primes, x) prime_list = [] for i in range(n-1): if primes[i]: prime_list.append(i+2) return prime_list def is_prime(self, n): k = 50 # number of iteration times if n < self.list_limit: return True if n in self.prime_list else False for prime in self.prime_list: if n%prime == 0: return False else: s, d = 0, n-1 while d%2==0: s,d = s+1, d/2 while k > 0: k = k-1 a = random.randint(1,n-1) t, y = d, pow(a,d,n) while t != n-1 and y != 1 and y != n-1: y = pow(y,2,n) t <<= 1 if y != n-1 and t%2 == 0: return False return True if __name__=="__main__": pc = PrimeChecker() pc.is_prime(58427) # True
Nが現れる素数を見つけるためのプログラム
from primechecker import PrimeChecker def display_letter(p): """ display letter on commandline for checking """ print("-"*18) for i in range(0,216,18)[::-1]: print(str(p/pow(10,i) + pow(10,18))[1:]) p = p%pow(10,i) print("-"*18) def tex_command(p,num,f): """ output tex command to file """ f.write("\\begin{align} \n") for i in range(0,216,18)[::-1]: f.write("&") string = str(p/pow(10,i) + pow(10,18))[1:] string = string.replace(str(num), "\color{red}{%d}"%num) f.write(string) p = p%pow(10,i) f.write("\\\\ \n") f.write("\\end{align} \n") letters = [""" 000000000000000000 000000001111000000 000000011111000000 000000111111000000 000001101111000000 000000001111000000 000000001111000000 000000001111000000 000000001111000000 000000001111000000 000001111111111000 000000000000000000 """,""" 000000000000000000 000000222222000000 000022222222220000 000222000002220000 000000000022220000 000000000222200000 000000002222000000 000000022220000000 000002222000000000 000222222222222000 000222222222222000 000000000000000000 """,""" 000000000000000000 000000333333000000 000033333333330000 000333000003333000 000000000033333000 000000033333300000 000000033333300000 000000000033333000 000333000003333000 000033333333330000 000000333333000000 000000000000000000 """,""" 000000000000000000 000000004444400000 000000044444400000 000000444444400000 000004440444400000 000044400444400000 000444000444400000 004444444444444400 004444444444444400 000000000444400000 000000000444400000 000000000000000000 """] pc = PrimeChecker() f = open("result.txt","w") for n, letter in enumerate(letters): num = n+1 prime_letter = int(letter.replace("\n","")) for i in range(1000,10000)[::-1]: if (i/1000)!=num and ((i%1000)/100)!=num and ((i%100)/10)!=num and i%10 != num: pl = prime_letter pl += pow(10,215) * (i/1000) pl += pow(10,198) * ((i%1000)/100) pl += pow(10,17) * ((i%100)/10) pl += i%10 if pc.is_prime(pl): display_letter(pl) tex_command(pl,num,f) break f.close()
実際の素数
1
900000000000000007000000001111000000000000011111000000000000111111000000000001101111000000000000001111000000000000001111000000000000001111000000000000001111000000000000001111000000000001111111111000400000000000000003
2
900000000000000004000000222222000000000022222222220000000222000002220000000000000022220000000000000222200000000000002222000000000000022220000000000002222000000000000222222222222000000222222222222000400000000000000009
3
800000000000000002000000333333000000000033333333330000000333000003333000000000000033333000000000033333300000000000033333300000000000000033333000000333000003333000000033333333330000000000333333000000400000000000000009
4
900000000000000009000000004444400000000000044444400000000000444444400000000004440444400000000044400444400000000444000444400000004444444444444400004444444444444400000000000444400000000000000444400000500000000000000003
本当は5,6,7,8,9と求めたかったけれど、文字を作るのが面倒で断念してしまいました。
誰か頑張って作ってください。。。
(追記)
そこまで珍しいことだとは思わず、一例しか挙げていませんでした。
存在自体が不思議という話があったので、数を数えてみたのですが
1: 14個
2: 15個
3: 4個
4: 17個
と、そこまで珍しくないことがわかります*1
素数定理に従えば、216桁以下の素数の存在確率は1/log(10^217)≒0.2%らしいです。
リーマン予想の意味,素数分布との関係 | 高校数学の美しい物語
5832*0.002 = 11.6個
だいたいそれくらいですね。
5832個の数字が独立に0.2%の確率で素数かどうか決まるとすると、
各Nに対してそのような素数が存在しない確率は実に0.000850%と非常に低い確率であることがわかります。
*1:4~17/5832を珍しいと考えるかどうかは人によるけれど