無限級数
を考える。
ここで、で、
、
である。これに従うと1, 4, 5, 9, 14, 23,...のような数列ができる。
この問題では、が正整数となるようなxについて考える。
x 
1 2/5 2 
3 4 1/2 5 xが有理数となるような
最初の30個のgolden nuggetの総和を求めよ。
Ploblem 137と同様に考えると、
であり、
が平方数となればよいということがわかる。これを整理すると
というペル方程式みたいなものが出てくる(ここで、nは自然数)。
ただ解き方がよく分からないのでWikipediaの英語版のペル方程式のページ(Pell's equation - Wikipedia)を見ると、
という形の方程式の解(x, y, i)を2つ用意すれば、
という形で別の解を生成できるということが書いてある。
ということは(7, 1, 44)と(9, 4, 1)から解を生成していけば終わりか？と思ったけどこれではダメな感じだった。解は次々に生成できるものの、網羅できない。
ただ、いろいろやって見るとと
から
と
が生成できることが分かった。
というわけで最初の6つだけ総当りで求めておいて、残りを漸化式で求めるという形をとった。
ただ、見てわかるように何の証明もしていなくて、たまたま出てきた数字が正解の判定を貰えたという感じは強い。
anext <- function(a, n) 9*a + 20*n nnext <- function(a, n) 9*n + 4*a a <- c(7, 8, 13, 17, 32, 43) n <- c(1, 2, 5, 7, 14, 19) ans <- 7 cnt <- 2 limit <- 30 while(cnt < limit){ a[7] <- anext(a[1], n[1]) n[7] <- nnext(a[1], n[1]) if((a[7] - 7) %% 5 == 0){ ans <- ans + (a[7]-7)/5 cnt <- cnt + 1 } a <- a[-1] n <- n[-1] } as.character(ans)
