【算数】「フィボナッチ数列」は「ユークリッドの互除法」であると言っても過言ではある。

以前書いたオリジナル問題の解説編です。2023年の慶應義塾大学に似たような問題が出題されていたそうなので、種明かしします(動画)。

【問題】剰余ボナッチ数列

2つ前の数を1つ前の数で割ったときの余りを次の数とする整数の列を考えます。例えば111、30から始めると、数列は111、30、21、9、3、0となります。数列は、0が現れたところで終わりとします。以下の問いに答えてください。
(1) 20250、833から始めたとき、最後から2番目の数は何ですか。
(2) 次の数列の□に入る数は何ですか。左から順番に答えてください。
　　2122、□、99、□、□、□、0
(3) 10番目の数が0となるような数列のうち、1番目の数として最も小さいものは何ですか。

算数PLAYオリジナル問題

---

【解説】またの名を「互除ボナッチ」

(1)設定通りに作業してみます。
20250÷833＝24あまり258
833÷258＝3あまり59
258÷59＝4あまり22
59÷22＝2あまり15
22÷15＝1あまり7
15÷7＝2あまり1
7÷1＝7あまり0
よって、最後から2番目は1と分かります。繰り下りが多くて面倒ですね。

★賢めの受験生ならここで気づくことと思いますが、実はこの数列は、いわゆる「ユークリッドの互除法」を行っています。「2数で割り算をし、割る数を余りで割る」を繰り返し、割り切れた数が元の2数の最大公約数と判明する、というアルゴリズムですね。この数列においては最後から2番目の数が最初の2数の最大公約数にあたります。

これを利用する場合、20250と833の最大公約数を直接探せばよく、20250が容易に素因数分解できるため、互除法よりも手短に答えが求められます。
20250＝2025×10＝45×45×10＝3×3×5×3×3×5×2×5、また、833は2でも3でも5でも割り切れないため、20250と833は1以外に公約数を持たない。よって最後から2番目の数は1。ちなみに833＝7×7×17。

---

(2)2122、□、99、□、□、□、0。逆算するだけです。
2122÷□＝△あまり99より、2122＝□×△＋99。
よって、□×△＝2122−99＝2023。
2023＝7×17×17より、□は99より大きい119か289か2023のいずれか。
　・2122、119、99、20、19、1、0→適する。
　・2122、289、99、91、8、3、2、1、0→数が多いので不適。
　・2122、2023、99、43、13、4、1、0→数が多いので不適。
よって□に入る数は、119、20、19、1。4つの数だけを使った数列でした。

---

(3)10番目の数が0となるような数列のうち、1番目の数として最も小さいものを求める問題。作業だけです。
最小の数を考えるので、できるだけ小さい数を右から並べて戻していく。
0の前は1。
1の前は2。(わる数と余りの関係なので、前は必ず大きくなる。)
2の前は3。(2で割って1余る数で最小)
3の前は5。(3で割って2余る数で最小)
5の前は8…13…21…34…55
ということで、55が答えです。他の数だと、どうしても55より大きくなります。

★これらの数は正に、前の2数を足して作られるフィボナッチ数になっていますね。この互除ボナッチ数列(適当)は、前の2数で引き算をしています（割り算は、引けるだけ引く計算）から、逆に並べるとフィボナッチ数列の性質が出てきます。1、1から始まるフィボナッチ数列は、隣り合う数は全て互いに素となっています。

---

【余談】

当初、これが互除法と気づかずに目新しいパズルができたと思っていました。いずれも基本的な知識や作業のみで答えが出ますが、他の知識とのつながりがあって面白いと思います。もう少し捻ってみたい。
2024年7月14日