条件付きの倍数

「とっておきの数学パズル」に0,1,2という問題があった. 2.2

「十進表記で0と1のみからなる自然数nの0でない倍数が存在する」というのである.

計算してみると0から9のnについて, 次のようになる. つまり3は37倍すると1だけの十進数111となる.

n       倍  十進表記
0        1         0
1        1         1
2        5        10
3       37       111
4       25       100
5        2        10
6      185      1110
7      143      1001
8      125      1000
9 12345679 111111111

この9の場合はタイガー計算器でよく遊んだ計算である.

十進表記の求め方を考えてみた. %で剰余を表すと, 3の場合は, 1%3=1, 10%3=1, 100%3=1だから, 111ではその和が3, つまり剰余が0, よって111は3の倍数である.

7の場合は, 1%7=1, 10%7=3, 100%7=2, 1000%7=6だから, 和が7の倍数になるように1と1000を選び, 1001が7の倍数となるわけだ.

そこで早速プログラムを考えてみる.

10のべきをnで割った剰余のべき集合の和のnによる剰余が0のものを求めたい.

まず(0)なるリストを用意する. これは空のべき集合である. 次に10の0乗, 1をnで割った剰余1を, これまでのリストの各要素に足し, (1)が出来, これを(0)の前にappendする. (1 0)が出来る.

次は10の1乗, 10をnで割った剰余を, これまでのリストの各要素に足す. nが7なら, 剰余3を足し, (4 3)が出来る. appendすると(4 3 1 0)になる. それぞれ(11 10 1 0)を7で割った剰余である.

同様に100を7で割った剰余2を足すと(6 5 3 2)が出来, appendして(6 5 3 2 4 3 1 0)になる. この段階では, 最後の0以外に7の倍数はないので, まだ続ける.

1000でやると剰余は10の時の剰余3と100の時の剰余2の積で6. よって新しいリストは(12 11 9 8 10 9 7 6)となり, べき集合に7の倍数7が現れた.

7は新しいリストにあるから1000番台は1, リストの右半分にあるから, 100番台は0, そのまた右半分にあるから, 10番台も0, その(7 0)では左にあるから, 1番台は1で, 結局1001が7の0と1による倍数(の最小のもの)であった.

Schemeのプログラムは次のとおり.

(define (zeroone n e rs)
 (let* ((r (modulo e n))
  (rs1 (map (lambda (x) (modulo (+ x r) n)) rs)))
  (if (member 0 rs1)
   (- (length (member 0 (append rs1 rs))) 1)
   (zeroone n (* e 10) (append rs1 rs)))))

引数のeは10の順次のべきで, 最初の起動では1, rsはリストで最初は(0). let*で用意するrはこの桁の剰余, rs1は新しいリストである. let*の後の本体のifは, 新しいリストに0があるかを見, あればその位置を返す. なければ次の桁へ進む.

起動は次のようにする.

(zeroone 13 1 '(0))

9が結果の値だが, これを二進で1001としたのが求める十進表記になる. n=2から20までの値は

(map (lambda (x) (zeroone x 1 '(0))) (a2b 2 21)) =>
 (2 7 4 2 14 9 8 511 2 3 28 9 18 14 16 29 1022 25 4)

二進で示すと

(map (lambda (x) (number->string (zeroone x 1 '(0)) 2))
 (a2b 2 21)) =>
 ("10" "111" "100" "10" "1110" "1001" "1000" "111111111"
  "10" "11" "11100" "1001" "10010" "1110" "10000" "11101"
  "1111111110" "11001" "100")

ところでこういう倍数が存在する理由はなにか. 10のべきをnで割った剰余を表示してみると:

(define (foo n)
 (map (lambda (x) (modulo (expt 10 x) n)) (a2b 0 20)))

(foo 2) =>
 (1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0)
(foo 3) =>
 (1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1)
(foo 4) =>
 (1 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0)
(foo 5) =>
 (1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0)
(foo 6) =>
 (1 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4)
(foo 7) =>
 (1 3 2 6 4 5 1 3 2 6 4 5 1 3 2 6 4 5 1 3)
(foo 8) =>
 (1 2 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0)
(foo 9) =>
 (1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1)

のようで, 0があるものはその桁を1つとれば完成. 0がないものは剰余だから当然同じ数が何回も現れる. その桁をn個足せば当然nの倍数が得られるわけだ.

面白い問題であった. ところでこういう条件付き倍数の生成を対数表の計算で利用した人がいた. Edward Sangのその話は次回に.