インテジャーズ

読者です 読者をやめる 読者になる 読者になる

インテジャーズ

数、特に整数に関する記事。

43:Göbel数列(エイプリルフール問題、問3の解説)

エイプリルフール記事
integers.hatenablog.com
で出題した問3の解説を行います。

問題は次のようなものでした:

問3 数列\{a_n\}_{n=1}^{\infty}a_1=1および
na_{n+1}=1+a_1^2+a_2^2+\cdots +a_n^2
によって定義する。
a_1=1, a_2=2, a_3=3, a_4=5, a_5=10, a_6=28, a_7=154, a_8=3520, \dots
このとき、任意の自然数nに対してa_nが整数であることを証明せよ。

これはGöbel数列と呼ばれている数列で普通はx_0=1,

\displaystyle x_{n+1} = \frac{1+x_0^2+x_1^2+\cdots +x_n^2}{n+1}

で定義されるため、以降\{x_n\}を用いて解説します。

最初のいくつかの値を見てみると少し大きめの数が現れることが分かります:

x_{0}= 1
x_{1}= 2
x_{2}= 3
x_{3}= 5
x_{4}= 10
x_{5}= 28
x_{6}= 154
x_{7}= 3520
x_{8}= 1551880
x_{9}= 267593772160
x_{10}= 7160642690122633501504
x_{11}= 4661345794146064133843098964919305264116096

\begin{equation}\begin{split}x_{12}= &1810678717716933442325741630275004084414865420898591223522682\\ &022447438928019172629856\end{split}\end{equation}

\begin{equation}\begin{split}x_{13}= &2521967245225414108125790971603617696902880162601604453290592\\
&8081411909054521468963035694105796668300270624304582308082917\\ &4307488383892818892448294858132739063481087616\end{split}\end{equation}

\begin{equation}\begin{split}x_{14}= &4543084847135617156827912757388745495368280304614840838595881\\
&8661849168624845686113232512374665144002986660355054429212523\\ &5174147640872384813465160305130148273242631727996782469247359\\
&0004311667893669816825659451437945264179017683087851534875769\\ &6125204303587647947798961480564408541809837455171811504569258\\
&94414444744263895766823050176\end{split}\end{equation}

\begin{equation}\begin{split}x_{15}= &1375974661884883593958307872179178705368405647167653708277552\\
&9680289124738126091022173768501691117657105157738355993025260\\ &1425024116126030171739982076897018413487680419215088685480135\\ &6030366186182424436442996889021994405615153205582903467344478\\ &7921231066181141022355650321865049688497263508855993365332059\\ &2235241033475869594100438984490724838465142948408287279920217\\ &4077593625353904681667598612880451668712691329300699545740348\\ &4379871141076455337522809690676805736112642146030785614549616\\ &2822829306418740752779770509108256234815385182670930999924522\\ &4806527712609283567103740647842272786590546895644500236443431\\ &510130695525780542823497682908835486798511724130649088896\end{split}\end{equation}


しかし、確かに整数になっています。この問題のどこらへんがエイプリルフールかというと、x_{42}までは整数であるけれども、実はx_{43}が整数ではないのです。

つまり、成り立たないものを証明せよと言っているので、どれだけ証明しようと努力しても証明できません。

更に質の悪いことに、数がとても大きくなっていくのでプログラムを組んで数列の値を実際に出力して整数でないことを示そうと思ってもそうそう簡単ではありません。

天下りではありますが、合同式を使って証明するのがよいです:

補題 \ \ \ (n+1)x_{n+1}=x_n(x_n+n)が成立する。
証明. n \geq 1のとき、
(n+1)x_{n+1}=1+x_0^2+x_1^2+\cdots +x_{n-1}^2+x_n^2=nx_n+x_n^2=x_n(x_n+n)
と計算できる。 Q.E.D.

命題 \ \ \ x_{43} \not \in \mathbb{Z}.

証明. 補題を使って逐次的に\bmod{43}計算を行う:

x_6 \equiv 25, x_7 \equiv 37, \dots, x_{42} \equiv 33  \pmod{43}

そうして

43x_{43}=x_{42}(x_{42}+42)\equiv 33(33+42) = 2475 \equiv 24 \not \equiv 0 \pmod{43}

であることからx_{43} \not \in \mathbb{Z}がわかる。 Q.E.D.

3-Göbel数列

3-Göbel数列\{y_n\}y_0=1および

\displaystyle y_{n+1}=\frac{1+y_0^3+y_1^3+\cdots +y_n^3}{n+1}

によって定義されます。このとき、

y_{0}= 1
y_{1}= 2
y_{2}= 5
y_{3}= 45
y_{4}= 22815
y_{5}= 2375152056927
y_{6}= 2233176271342403475345148513527359103

\begin{equation}\begin{split}y_{7}= &1591002909245851102188660218618116637818488622409702751192275\\ &216849119621798426607577261282879455499092734335\end{split}\end{equation}

\begin{equation}\begin{split}y_{8}= &5034112704245798738298258322579188433476515817956466946429212\\
&5321348158160494269116946265506555020806549020811668825458977\\
&3339597096425592058664300289453019603872547494341604380616942\\
&8406091398196863516063919549766986682160558163874313636469151\\
&4396231405780452828968277892968875196701042128377420495077899\\
&3750712646710773215\end{split}\end{equation}

\begin{equation}\begin{split}y_{9}= &1417510529593941229163479235889460904358029209430937165180487\\
&8075109688677066754239862080937922894104109566106688602909371\\
&7065791254272891571957698266943382187727272648019439861606841\\
&5365168345409156531272469369787020724219927792888859941586531\\
&8266041185090321318922889072299624613269784310714337125744372\\
&9524152817530517759276618211402439707845296514436982359897560\\
&3742918513365469074570063182737559885577377504500739130769457\\
&5418235438612494742910833355283052576052356196346388466588678\\
&6559687088369238285433690189566236145296733916233735809030446\\
&3975748625812092444313643276205895704703020154742718640803934\\
&4205146911599066337595012626372663648842452917921796528910990\\
&8489302192015667526403585806176551838389629118580869504542037\\
&1111821841409904822868055560380614991254586393151655752590322\\
&2506774172200989708650250130203622322858568744014655527646115\\
&8534862992849368003605983553169882270404743859389158697662275\\
&82759917655939988738946864442144554488094148868149655455\end{split}\end{equation}

と最初の方の値は整数になっていますが、y_{89}に至って整数でない値をとります。

k-Göbel数列

k2以上の整数とするとき、同様にk-Göbel数列\{x_n^{(k)}\}x_0^{(k)}=1および

\displaystyle x_{n+1}^{(k)}=\frac{1+(x_0^{(k)})^k+(x_1^{(k)})^k+\cdots +(x_n^{(k)})^k}{n+1}

によって定義することができます。このとき、新しい数列\{a_k\}_{k=2}^{\infty}k-Göbel数列が初めて整数でない値をとるときの数列の番号によって定義します*1a_2=43, a_3=89です。

補題と同様にして(n+1)x_{n+1}^{(k)}\equiv x_n^{(k)}((x_n^{(k)})^{k-1}+n)を証明することができるので、これを用いてnx_n^{(k)} \not \equiv 0 \pmod{n}なる最小のnを見つければ一応a_kを計算することはできます。

a_kのいくつかの値をみると

a_2=43 ←素数!
a_3=89 ←素数!
a_4=97 ←素数!
a_5=214
a_6=19 ←素数!
a_7=239 ←素数!
a_8=37 ←素数!
a_9=79 ←素数!
a_{10}=83 ←素数!
a_{11}=239 ←素数!
a_{12}=31 ←素数!
a_{13}= 431 ←素数!
a_{14}= 19 ←素数!
a_{15}= 79 ←素数!
a_{16}= 23 ←素数!
a_{17}= 827 ←素数!
a_{18}= 43 ←素数!
a_{19}= 173 ←素数!
a_{20}= 31 ←素数!
a_{21}= 103 ←素数!
a_{22}= 94
a_{23}= 73 ←素数!
a_{24}= 19 ←素数!
a_{25}= 243
a_{26}= 141
a_{27}= 101 ←素数!
a_{28}= 53 ←素数!
a_{29}= 811 ←素数!
a_{30}= 47 ←素数!
a_{31}= 1077
a_{32}= 19 ←素数!
a_{33}= 251 ←素数!
a_{34}= 29 ←素数!
a_{35}= 311 ←素数!
a_{36}= 134
a_{37}= 71 ←素数!
a_{38}= 23 ←素数!
a_{39}= 86
a_{40}= 43 ←素数!
a_{41}= 47 ←素数!
a_{42}= 19 ←素数!
a_{43}= 419 ←素数!
a_{44}= 31 ←素数!
a_{45}= 191 ←素数!
a_{46}= 83 ←素数!
a_{47}= 337 ←素数!
a_{48}= 59 ←素数!
a_{49}= 1559 ←素数!
a_{50}= 19 ←素数!
a_{51}= 127 ←素数!
a_{52}= 109 ←素数!
a_{53}= 163 ←素数!
a_{54}= 67 ←素数!
a_{55}= 353 ←素数!
a_{56}= 83 ←素数!
a_{57}= 191 ←素数!
a_{58}= 83 ←素数!
a_{59}= 107 ←素数!
a_{60}= 19 ←素数!
a_{61}= 503 ←素数!

と、ところで素数ばっかり出てくるのは流石に偶然ですよね(震え声)。

数列を0番目から始めたわけですが、最初の出題のように1番目から始めると最後の数列は全て1ずつずれるわけですし。。。

*1:well-definedかどうかは知りません。