Y箱

この問題はちょっと気合が入った。

まず、f(n) = n² + an + b とすると、
2階微分 f''(n) = 2 なので、nが1増えると、増分が2ずつ増えることになります。
n²+n+41でできる数列はたしかにそうなってます。
元 41 43 47 53 61 71 83 97 113 ...
増分 2 4 6 8 10 12 14 16 ...

n²-79n+1601 のほうは、
元 1601 1523 1447 1373 1301 1231 1163 1097 1033 ...
増分 -78 -76 -74 -72 -70 -68 -66 -64 ...
ちゃんと2づつ増えてます。

あと、こっちの数列を良く見てみると
1601 1523 1447 ...省略... 47 43 41 41 43 47 ...省略... 1447 1523 1601
のように、41で折りかえしていて、ここに出てくる数字は、オイラーの公式のものと
全く同じです。

この「41」は魔法の数字かなと思って、他の素数を調べてみました。
nは0から始まらなくてはならないので、最初の増分の増分はかならず2で、4、6、8..と続かなくてはだめです。
1000までの素数にそのような数字はあるのかな？と思って全部調べてみると他にはないことがわかります。ということはこの41の系列がかならず登場するということです。

ということは、答えは、
(1) 41からはじまるもの (n²+n+41のパターン)
(2) 41の両側に広がっているもの (n²-79n+1601のパターン)
のどちらかです。

さて、(1)の41からはじまるパターンの場合n=0のときに41にならなくてはならないのでb=41に決まりです。また、n=1のときには43にならなくてはならないので、a=1に決まってしまいます。結局、これしかないということです。

そんなわけで解は(2)のパターンでだけみつかるはずです。
このパターンは、始めに減っていく必要があるので、bは負の数です。
また、増分の増分が2になる数列は41の系列しかありませんので、bはこの数列の中にあるはずです。

こまででしらみつぶそうかと思ったのですが、もうちょっと考えました。

f(n)を変形すると、
f(n) = (n + a)² + b - a²/4
で、この後ろのb - a²/4に注目すると、
n²+n+41 は 41-1/4 = 163/4
n²-79n+1601 は 1601-(-79)²/4 = 163/4
おー。
よくわからんのだけれど、始めのころにこの公式を調べていたら、「虚二次体 Q(sqrt (-163)) の類数が 1 であることと関係している」というのを見付けていたのだけど、こんなところに 163 が出てきてびっくり。

ともあれ、いつでも b - a²/4 の値が 163/4 であるということにしてしまって、
- bは数列(41 43 47...)の中にある
- そのbについて b - a²/4 の値が 163/4 になるようなaを見つける
という方針でいくことにします。

b - a²/4 = 163/4 なので
a = sqrt ( 4b-163)

bの大きいほうから順にチェックして最初に出てきたのが答えでしょう。

;;
;; Problem 27  : 2011/5/12
;;"Elapsed time: 0.776914 msecs"

(def num-list (reverse (map #(+ (expt % 2) % 41) (range 40))))

(first (filter #(integer? (second %)) 
                (map #(list % (sqrt (- (* 4 %) 163))) 
                     (drop-while #(> 999) num-list)))))
;;