例題：數論 2進位表示法 與 除法原理結合的問題
[quote]題目：數列1,2,3,4,5,10,20,40,80....前五項成等差，第五項起為等比試証所有正整數都可以表成此數列中元素的和。
[/quote]
此數列1,2,3,4,5,10,20,40,80....
其實就是 [color=darkorange]1[/color], [color=darkorange]2[/color], [color=darkorange]3[/color], [color=darkorange]4[/color], ,[color=darkgreen]5[/color]*[color=blue]2^0[/color] , [color=darkgreen]5[/color]*[color=blue]2^1[/color], [color=darkgreen]5[/color]*[color=blue]2^2[/color], [color=darkgreen]5[/color]*[color=blue]2^3[/color], [color=darkgreen]5[/color]*[color=blue]2^4[/color], ...
對任意正整數 M ，被 5 除之後，
假設餘數為r，則 r 屬於 {1,2,3,4}，
將商以唯一的二進位表示法寫為 a[size=1]n[/size]*2^n + a[size=1]n-1[/size]*2^(n-1) + ... + a[size=1]1[/size]*2 + a[size=1]0[/size]
其中 a[size=1]n[/size]=1 且 a[size=1]n-1[/size], a[size=1]n-2[/size], ..., a[size=1]1[/size], a[size=1]0[/size] 屬於 {0,1}
亦即
M = [color=darkgreen]除數[/color] * [color=blue]商[/color] + [color=darkorange]餘數[/color]
= [color=darkgreen]5[/color]*[color=blue](a[size=1]n[/size]*2^n + a[size=1]n-1[/size]*2^(n-1) + ... + a[size=1]1[/size]*2 + a[size=1]0[/size])[/color] + [color=darkorange]r[/color]
= a[size=1]n[/size]*[color=darkgreen]5[/color]*[color=blue]2^n[/color] + a[size=1]n-1[/size]*[color=darkgreen]5[/color]*[color=blue]2^(n-1)[/color] + ... + a[size=1]1[/size]*[color=darkgreen]5[/color]*[color=blue]2[/color] + a[size=1]0[/size]*[color=darkgreen]5[/color] + [color=darkorange]r[/color]
其中 r 為此數列的前四項之中的一個，
若 a[size=1]i[/size]=1 ，則表示有加上 [color=green]5[/color]*[color=blue]2^i[/color] (這個數字是此數列中的第 i+4 項)
若 a[size=1]i[/size]=0 ，則表示[b]沒有[/b]加上 [color=green]5[/color]*[color=blue]2^i[/color] (這個數字是此數列中的第 i+4 項)
頁:
[1]