創作整数問題と題して20問ほど整数問題ばかり投稿してきましたが、そろそろ酷似した問題を出題しかねないので、近いうちにまとめの固定ページを設置したいところですね。今回の問題#21は難問の部類かも･･･？
《問題#21》
$[x]$は$x$を超えない最大の整数を表すとする。
$\alpha=4+\sqrt{13}$とし、数列$\{a_{n}\}$を$$a_n=[{\alpha}^{n}]+[{\alpha}^{n+1}]$$によって定める。このとき数列$\{a_{n}\}$のすべての項はある正の整数$d$の倍数になっているという。$d$の最大値を求めよ。
（創作問題(編集済み)）
どこかの大学で出題されてもおかしくないような題材ですが、誘導設問やヒントは全カットしてあります。ご了承ください(笑)。いわゆるガウス記号が登場していますが、中身が何であろうと所詮は整数の値しか取りません。
» 答えはこちら
答えは $\color{red}{8}$ です。
» 閉じる
創作整数問題#20（解き方）
| 数字根とは、ある自然数$N$の各位の和$S_1$を求め、さらに$S_1$の各位の和$S_2$を求める、･･･という操作を繰り返し行い、最終的に得られる$1$桁の数のことを指す。例えば、$3^{10}=59049$の数字根は$9$であるが、これは$5+9+0+4+9= 27 \to 2 + 7 = 9$のように計算される。 $n$を自然数とするとき、$2^n$の数字根として得られる値をすべて求めよ。 |
《考え方》
「数字根」という単語はあまり聞きなれないと思いますが、これは具体例の通りに各位の数の和をどんどん計算していくことで最終的に得られる値のことを指しています。ということで「各位の数の和」を文字で式化してみましょう。十進法で$$(a_n a_{n-1} \cdots a_1)_{(10)}$$と表せる数$N$の各位の数の和$S$は、当然ながら$$S=a_n + a_{n-1} + \cdots + a_1$$として得られます。実はこれは$N$の各位の数を$9$で割った余りの和になっているのです。例えば$12345$という数字であれば各位の和は$15$となりますが、これは$$\begin{align} &\ \ \ \ \ 1 \cdot 10^4+2 \cdot 10^3+3 \cdot 10^2+4 \cdot 10 +5 \\ &=(9999+1)+2 (999+1)+3(99+1)+4(9+1) +5 \\ &\equiv 1+2+3+4+5 \pmod{9} \\ &=15 \end{align}$$という計算に相当します。数字根というのは１桁の数ですから、ある整数$N$について、$N$が１桁の数になるまでこれと同様の演算を繰り返せばよく、つまり、十進法において数字根を考える際は
「$\text{mod}$ $9$で考えればよい」
ということになります。これに気が付けば、$2^n \pmod{9}$として現れるすべての数が$2$の冪乗の数字根として得られる値となります。
$2^1 \equiv 2 \pmod{9}$、$2^2 \equiv 4 \pmod{9}$、$2^3 \equiv 8 \pmod{9}$$2^4 \equiv 7 \pmod{9}$、$2^5 \equiv 5 \pmod{9}$、$2^6 \equiv 1 \pmod{9}$、$2^7 \equiv 2 \pmod{9}$、･･･
となるので、求める数字根は$1,2,4,5,7,8$の６つとなります。
（コメント）
$\text{mod}$ $9$で考える、というのがミソですね。
合同式では加法、減法、乗法が成立しますから、数字根についても加法、減法、乗法が同様に成立します。
以下、$m、n$は整数であるとします。ここで$R(n)$を$n$の数字根（英語で”digital root”）を表す関数と定義すると、$$\begin{cases} R \left( R(n) \pm R(m) \right) =R(n \pm m) \\ R \left( R(n) \cdot R(m) \right) =R(n \cdot m) \end{cases}$$が成立するというワケです。これの何がありがたいかというと、実は数字根は計算結果の検算に利用できるのです。例えば$$11111 \cdot 12345=137165295$$ですが、数字根についても$$\begin{cases} R\left(R(11111) \cdot R(12345)\right)=R(5 \cdot 6) =3 \\ R(137165295)=3 \end{cases}$$と一致するのです（ｍｏｄで考えれば当たり前のことではありますが…）。これにより簡易的な検算が可能となります。ただし1/9の確率でパスしてしまうので完璧な検算法とは言えませんが、計算が正しいかどうかを簡単に判別するための道具として利用するとよいでしょう。ただ、数字根（つまり$\text{mod}$ $9$）と$\text{mod}$ $11$の２つｎ値を計算すれば更に精度が増しますが、それをするくらいなら実際に計算し直した方が良さそうです･･･。
a[n]は，a[1]=64,a[2]=496,a[n+2]=8a[n+1]-3a[n]+8によって定まり，
その各項は確かに8の倍数になりますが，
「a[n]/8とa[n+1]/8は互いに素である」は不成立ではないでしょうか．
実際，a[1]=64,a[2]=496はともに16の倍数です．
素因数2の個数については，以下のように処理することができますが，
最大公約数を求めるのは難しそうな気がします．
a[n]/8=b[n]として，b[n+2]=8b[n+1]-3b[n]+1=4(2b[n+1]-b[n])+b[n]+1.
よって，b[n+2]≡b[n]+1 (mod 4)であり，
b[n]を4で割った余りは「0,2,1,3,2,0,3,1」の繰り返しとなる．
よって，a[n]とa[n+1]の最大公約数が持つ素因数2の個数は，
nが4で割って1余るときは4個，それ以外のときは3個．
連続する3項a[n],a[n+1],a[n+2]の最大公約数ならば8となりますね．
ご指摘ありがとうございます。
確かに隣接２項では公約数の議論は難しいですね…。
適切な出題に改めるとすれば たけちゃん 様の仰るような隣接３項バージョンか、或いは「数列$\{a_n\}$のすべての項の最大公約数$d$を求めよ。」などという形に訂正しても良いかもしれません。いずれにせよ原題では解答不可能でしょう。まともに確かめもしないからこんなことになるんですね…。反省です。
因みに$\alpha=x+\sqrt{y}$とすると、ご指摘の通り$a_n=[{\alpha}^{n}]+[{\alpha}^{n+1}]$は$$a_{n+2}=2xa_{n+1}-(x^2-y)a_{n} \color{blue}{\underline{+2x}}$$という漸化式を満たします。今回の問題では最大公約数が$2x$に相当していますが、数列$\{a_n\}$の最大公約数が$2x$となるのは $y \equiv 1 \pmod{x}$ の場合には限ることが言えます。これは$$\begin{align} a_1 &=2x^2+2x+2y-2 \\ &=\color{red}{2x}(x+1)+2(y-1) \end{align}$$となるので、$a_1$が$\color{red}{2x}$で割り切れるためには$$y-1 \equiv 0 \pmod{x}$$が必要条件として得られることから導かれます。全くの余談ですが…。
（※(2017/07/21付)注：青字下線部分は「$-2(x-1)^2+2y$」の誤りです）
α=x+√y,β=x-√yとし，α^n+β^n=p[n]とすると，
p[n+2]=2xp[n+1]-(x^2-y)p[n]が成り立ちますね．これを[*]とします．
[*]からp[n+3]=2xp[n+2]-(x^2-y)p[n+1]であり，[*]と辺々加えて
p[n+3]+p[n+2]=2x(p[n+2]+p[n+1])-(x^2-y)(p[n+1]+p[n]).…[**]
さて，
・p[1]=2x,p[2]=2(x^2+y)だから，x,yが整数であれば帰納的にp[n]は整数
・さらに0<β<1であれば，0<β^n<1が成り立ち，[α^n]=p[n]-1
となるので，このとき(つまり，x,yが整数で，(x-1)^2<y<x^2のとき)は，
a[n]=(p[n]-1)+(p[n+1]-1)=p[n]+p[n+1]-2の満たす漸化式は，[**]から
a[n+2]+2=2x(a[n+1]+2)-(x^2-y)(a[n]+2),
すなわち
a[n+2]=2xa[n+1]-(x^2-y)a[n]-2(x-1)^2+2y
となりそうです．
たけちゃん 様、コメントありがとうございます。
訂正する前に早速ご指摘を頂いてしまいましたね…
是非今後ともよろしくお願いいたします。
実際の試験問題レベルにするには誘導設問で $p_n={\alpha}^{n}+{\beta}^{n}$ によって定まる数列$\{p_n\}$を登場させるべきなのでしょうが、今回はカットしています。
$\beta$を持ち出せば見通しがすっきりすることに普通の受験生は気付けるものでしょうかね…？