平成１６年7月１８日

[流れ星]

　　　　　第１４０回数学的な応募問題解答

　　　　　　＜解答募集期間：６月２７日〜７月１８日＞
［ある数列］

太郎さんは、ある数列の問題を見つけました。考えてください。

「初項１，公比３の等比数列　１，３，９，２７，８１，２４３，７２９，・・・がある。
　この数列から異なるいくつかの数をとってたしてできる数列を小さい順に並べてできる数列

　１，３，４，９，１０，１２，１３，・・・を考えるとき、この数列の１００番目はどんな数か。」

ＮＯ１「Iga」　　　6/27: 02時21分受信 更新7/18更新
お久しぶりです、Ｉｇａです。今回は割と早くひらめきましたので送ります。
「初項１，公比３の等比数列　１，３，９，２７，８１，２４３，７２９，・・・がある。
　この数列から異なるいくつかの数をとってたしてできる数列を小さい順に並べてできる数列　１，３，４，９，１０，１２，１３，・・・　を考えるとき、この数列の１００番目はどんな数か。」

初項１，公比３の等比数列をＡｍ、Ａｍからいくつかの異なる数をとってたしてできる数を小さい順に並べてできる数列をＢｎとします。
Ａ1〜Ａｍまでのｍ個の数でできるＢｎの項数は、その作り方から(２＾ｍ−１)個になります。ここで、Ｂｎの元の和の形と、ｎを２のべき乗の和で表したものを比較してみると次のようになります。
　　ｎ　  Ｂｎ            　　ｎを２のべき乗の和で表す
　　１　　　１＝１                　１
　　２　　　３＝　　３              　　２
　　３　　　４＝１＋３              １＋２
　　４　　　９＝　　　　９          　　　　４
　　５　　１０＝１　　＋９          １　　＋４
　　６　　１２＝　　３＋９          　　２＋４
　　７　　１３＝１＋３＋９          １＋２＋４
　　　・・・
この比較から、Ｂｎは、ｎを２のべき乗の和で表したものを３のべき乗なおしたものでることがわかります。
したがって、Ｂｎの１００番目は１００＝２＾２＋２＾５＋２＾６であることから
　Ｂ100 ＝３＾２＋３＾５＋３＾６＝９８１　になります。

これからも楽しい問題をよろしくお願いします。

ＮＯ２「H7K」 6/27: 23時44分受信 更新7/18更新
%% 時間ないで，非常におおまかな話だけ．a(n,i) = (nを2進数で表したもの)の，2^iの位の数とすると，
この数列の第n項は，x_n = a(n,0)+3a_(n,1)+9a(n_2)+...となる．(1+3+9+...+3^m<3^(m+1)であることに注意．)
よって，
100を2進数で表すと1100100なので，
x_100 = 1*3^6+1*3^5+0*3^4+0*3^3+1*3^2+0*3^1+0
      = 729+243+9 = 981.

「H7K」 7/09: 21時44分受信 更新7/18更新
やっと時間がテきたので，説明を加えた答案を書きます．
∀k>=1;1+3+3^2+...+3^(k-1)<3^k より，
問の数列は，
1, 3, 3+1, 9, 9+1, 9+3, 9+3+1, 27,...
となるが，これは3進法で表すと，
1, 10, 11, 100, 101, 110, 111, 1000,...
となり，どの項も，1と0のみを使って表される．
即ち，求める数は，
「3進法で0と1のみを使って表される数（>=1)で，100番目のもの」である．
これは，100を2進法で表示した数を，そのまま3進法に読み替えたものにほかならず，その値は981.

ＮＯ３「kashiwagi」6/28: 15時04分受信 更新7/18更新
お世話になります。今回の問題は非常に愉しく且つ面白く考えさせて頂きました。 そうなのですね、数列をじっくり睨んでいたら規則性が見えて参りました。公比３の 数列そのものに前の項全てを加えていくのですね。非常に面白い数列ですね。細かく 記述するのが面倒ですので、エクセルを使い計算して見ました。これですと機械的で すが間違えなく100番目の項が981であると分かります。

「kashiwagi」6/28: 15時04分受信 更新7/18更新
140回 解答

今、１，３，４，９，１０，１２，１３を３進法で表すと

１，１０，１１，１００，１０１，１１０，１１１となる。

ここで、視点を変えて、これらの数値を２進法で表されたものと見なすと、

１０進法に直した場合、１，２，３，４，５，６，７を表す。

因って１００番目の数を２進法で表すと１１００１００となる。

この値を３進法で表記されたものと見なすと、９８１となる。

以上より求める値は９８１である。

ＮＯ４「toru」　　 6/29: 11時21分受信 更新7/18更新
第１４０回問題の解答を応募します。考え方としては同じようですが、一応、２通りの解答を考えてみました。

１）３進法で各位の数字が０か１のものを小さい順に並べると考えれば、１００番目の数字は、
100=2^6+2^5+2^2より1100100これを１０進法にもどして、 3^6+3^5+3^2=981　―――答え）

２）第n項をA(n) (ただしA(0)=0とする)とすれば、１）と同様に考えて、A(2n)は３進法では、A(n)の右側に０を一つ増やしたことになり、10進法に戻せば、 A(2n)=3A(n)、A(2n+1)=A(2n)+1 とから
 A(100)=(3^2)A(25)=9(A(24)+1)=9((3^3)A(3)+1)=9(27×4+1)=981―――答え）

やっていることは２進法になおして、３進法と考えるということですが、どうも混乱
しそうで、上記のように説明してみましたが、　　　ペンネーム　Toru

ＮＯ５「kasama」　 6/29: 18時29分受信 更新7/18更新
等比数列1=3⁰、3=3¹、 9=3²、27=3³、･･･は3べき乗ですから、この数列から異なるいくつかの数をとってたしてできる数の指数部に着目します。すると、これらは二進数に対応させることができますね。例えば、

　10 = 3^2 + 3^1 + 3^0 = 1×3^2 + 0×3^1 + 1×3^0 ⇒ 101

です。もう少し例を挙げると、下表のようになります。

数	べき数の和	べき数の和(係数付き)	二進数
1	3^0	0×3^2 + 0×3^1 + 1×3^0	001
3	3^1	0×3^2 + 1×3^1 + 0×3^0	010
4	3^1 + 3^0	0×3^2 + 1×3^1 + 1×3^0	011
9	3^2	1×3^2 + 0×3^1 + 0×3^0	100
10	3^2 + 3^0	1×3^2 + 0×3^1 + 1×3^0	101
12	3^2 + 3^1	1×3^2 + 1×3^1 + 0×3^0	110
13	3^2 + 3^1 + 3^0	1×3^2 + 1×3^1 + 1×3^0	111

ここで、○番目の数を調べるには、規則正しく増加している二進数を調べると簡単です。100番目の二進数は1100100ですから、

　100番目の数 = 3⁶ + 3⁵ + 3² = 981　です。

ＮＯ６「中川幸一」　 7/18: 05時23分受信 更新7/19更新

今回の数列の問題は
『Numbers n such that base 3 representation contains no 2』という名前が付いている数列ですね。
一応 3 通りの解法を作ってみました。どれも Program にしてみました。
一応, 解答 1 のやり方を用いれば, Program を組まなくても今回の値は求まりますが, 一般的に『早く』求めることを配慮してこのような解答にしました。

　　　　＜自宅＞　　mizuryu@aqua.ocn.ne.jp