發新話題
打印

例題:數論 2進位表示法 與 除法原理結合的問題

推到噗浪
推到臉書

例題:數論 2進位表示法 與 除法原理結合的問題

引用:
題目:數列1,2,3,4,5,10,20,40,80....前五項成等差,第五項起為等比
試証所有正整數都可以表成此數列中元素的和。
此數列1,2,3,4,5,10,20,40,80....
其實就是 1, 2, 3, 4, ,5*2^0 , 5*2^1, 5*2^2, 5*2^3, 5*2^4, ...


對任意正整數 M ,被 5 除之後,
假設餘數為r,則 r 屬於 {1,2,3,4},
將商以唯一的二進位表示法寫為 an*2^n + an-1*2^(n-1) + ... + a1*2 + a0
其中 an=1 且 an-1, an-2, ..., a1, a0 屬於 {0,1}
亦即
M = 除數 * + 餘數
 = 5*(an*2^n + an-1*2^(n-1) + ... + a1*2 + a0) + r
 = an*5*2^n + an-1*5*2^(n-1) + ... + a1*5*2 + a0*5 + r

其中 r 為此數列的前四項之中的一個,
若 ai=1 ,則表示有加上 5*2^i (這個數字是此數列中的第 i+4 項)
若 ai=0 ,則表示沒有加上 5*2^i (這個數字是此數列中的第 i+4 項)

TOP

發新話題