問題12494・・・やどかりさんのブログ
http://blogs.yahoo.co.jp/oka_yadokary/37536924.html より Orz〜
a1＝0 ，ｎが自然数のとき a2n＝an＋1，a2n+1＝an で 表される数列｛ an ｝について、
a1＋a2＋a3＋a4＋……＋a1069＋a1070＝？
解答
[解答1]
Sn＝a1＋a2＋a3＋a4＋……＋an-1＋an とします。
a2n＋a2n+1＝an＋1＋an＝2an＋1 だから、
S2n+1＝a1＋a2＋a3＋a4＋a5＋……＋a2n＋a2n+1＝0＋2a1＋1＋2a2＋1＋……＋2an＋1＝2Sn＋n 、
S2n＝S2n+1−a2n+1＝2Sn＋n−an 、
S2n＝2Sn＋n−an ，S2n+1＝2Sn＋n です。
S1070＝2S535＋535−a535＝2(2S267＋267)＋535−a267＝4S267＋1069−a267＝4(2S133＋133)＋1069−a133
＝8S133＋1601−a133＝8(2S66＋66)＋1601−a66＝16S66＋2129−a66＝16(2S33＋33−a33)＋2129−(a33＋1)
＝32S33＋2656−17a33＝32(2S16＋16)＋2656−17a16＝64S16＋3168−17a16
＝64(2S8＋8−a8)＋3168−17(a8＋1)＝128S8＋3663−81a8＝128(2S4＋4−a4)＋3663−81(a4＋1)
＝256S4＋4094−209a4＝256(2S2＋2−a2)＋4094−209(a2＋1)＝512S2＋4397−465a2
＝512(2S1＋1−a1)＋4397−465(a1＋1)＝1024S1＋4444−977a1＝1024･0＋4444−977･0＝4444 です。
[解答2]
an は ｎを２進法で表したときの 0 の個数です。
ｎが２進法でｋ桁の数であるとき、すなわち、2k-1≦n≦2k−1 のとき、
該当する自然数は 2k-1 個あり、２進法で首位を除いて 0，1 が同数個あるので、
平均して (k−1)/2 個の 0 があることになり、総数は 2k-2(k−1) です。
1023＝1111111111(2) なので、 S＝a1＋a2＋a3＋……＋a1023 とすれば、
S＝2-1･0＋20･1＋21･2＋22･3＋23･4＋24･5＋25･6＋26･7＋27･8＋28･9 、
2S＝20･0＋21･1＋22･2＋23･3＋24･4＋25･5＋26･6＋27･7＋28･8＋29･9 、
4S＝21･0＋22･1＋23･2＋24･3＋25･4＋26･5＋27･6＋28･7＋29･8＋29･18 、
S＋4S−2･2S＝1＋21(2＋0−2･1)＋22(3＋1−2･2)＋……＋28(9＋7−2･8)＋29(8＋18−2･9) 、
S＝1＋0＋……＋0＋29･8＝1＋4096＝4097 です。
1024＝10000000000(2) から 1055＝10000011111(2) までの 32個について、
２進法で下５桁は 0，1 が同数個あるので、0 は 32･(10＋5)/2＝240 個、
1056＝10000100000(2) から 1071＝10000101111(2) までの 16個について、
２進法で下４桁は 0，1 が同数個あるので、0 は 16･(9＋5)/2＝112 個です。
a1＋a2＋a3＋a4＋……＋a1069＋a1070＝4097＋240＋112−5＝4444 です。
*よくわからず…2進法の0の個数かもなんてことまで考えたはずなのに…
気づけないまま…^^;;...
a(2n+1)=an の個数が抜けてることに後で気づきましたが...面倒そうで思考放棄したものを以下に…Orz…
2で割れて4で割れない…+1
4でわれて8で割れない…+2
…
so…
[1070/2]*1+([1070/2]-[1070/4])*1=535*2-267
[1070/4]+([1070/4]-[1070/8])*2=267*3-2*133
[1070/8]+([1070/8]-[1070/16])*3=4*133-3*66
[1070/16]+([1070/16]-[1070/32])*4=5*66-4*33
[1070/32]+([1070/32]-[1070/64])*5=6*33-5*16
[1072/64]+([1070/64]-[1070/128])*6=7*16-6*8
[1072/128]+([1070/128]-[1070/216])*7=8*8-7*4
[1070/216]+([1070/216]-[1070/512])*8=9*4-8*2
[1070/512]+([1070/512]-[1070/1024])*9=10*2-1*9
[1070/1024]+([1070/1024]-[1070/2048])*10=11*1
so...
2*(535+267+133+66+33+16+8+4+2+1)=2130
・友人からのもの…
2^nのところで区切って群数列とする
第1群 a(1)=0
第2群1,0
3群 2,1,1,0
4群 3,2,2,1,2,1,1,0
5群 4,3,3,2,3,2,2,1,3,2,2,1,2,1,1,0
6群 5,4,4,3,4,3,3,2,4,3,3,2,3,2,2,1,4,3,2,3,2,2,1,3,2,2,1,2,1,1,0
…………….
k群の項数は2^(k-1) 個
k+1群の後半はk群と同じ、前半はk群の各項+1
漸化式を追ってみれば、一般に成り立つことは分かる
よってS(k+1)=2S(k)+k群の項数=2S(k)+2^(k-1)
よってs(1)=0 s(2)=1 s(3)=4 s(4)=12……..s(9)=1024 s(10)=2304
S(10)までの和Σ{a(1)〜a(1023)}=4097
1024から1070項の和Σ(1024~1070)は項数が47であるから
=Σ(512〜558)+47=……..=Σ(64〜110)+47*4
=Σ(32〜63)+32*5+Σ(32〜46)+15*4=347 （63項までは手作業）
よって4097+347=4444
*わたしにゃよくわからずですばい…^^;...
コメント（1）
