1から順に2, 3, 4,...と数字が書かれた六角形のタイルを中心から外側に向かって反時計回りに敷き詰めていく。周の開始は時計でいう12時の位置とする(詳しくはリンク先問題文中の図を参照)。
値nが書かれたタイルは6枚のタイルに囲まれているが、その6枚のタイルのうち、nとの値の差が素数であるようなタイルの枚数をPD(n)で表す。
例として、PD(8)=3、PD(17)=2。
このとき、PD(n)の最大値は3であることが示せる。
PD(n)=3であるタイルを昇順に列挙すると、10番目のタイルに書かれた値は271である。さて、2000番目のタイルに書かれた値はいくつか。
最初任意のnから周囲の6枚を生成する方法を考えていたけどどうにも無理だったので少しググった。
そうするとどうも探索範囲が絞れるらしい、ということで図を再度よく見てみると何のことはない簡単に絞れる。ある部分を除けばタイルは連番で並んでいるのだから。
絞った範囲について6枚のタイルを生成するのは簡単だったので、残りは力技で求めた。7.5秒。
library(gmp) up <- function(n){ if(n == 1 || n == 2) return(n) 2 + (6 + 6*(n -2))*(n-2)/2 } chk1 <- function(n){ abs(up(n) - c(up(n + 1) + 1, up(n + 1) - 1, up(n + 2) - 1)) } chk2 <- function(n){ abs(up(n+1)-1 - c(up(n), up(n - 1), up(n + 2) - 2)) } isallprime <- function(x) !is.element(0, isprime(x)) count <- 1 ## PD(1) = 3 n <- 2 limit = 2000 repeat{ if(isallprime(chk1(n))) count <- count + 1 if(count >= limit){ ans <- up(n); break } if(isallprime(chk2(n))) count <- count + 1 if(count >= limit){ ans <- up(n + 1) - 1; break } n <- n + 1 } ans
