|
|
> No.2962[元記事へ]
> 問題
> 全ての自然数n対して必ず0と1からなるnの倍数が存在する
すべての桁が1（111…1という数）をベースに考えれば一般解になります。
考察
nが2や5の倍数でない場合、すべての桁が1（111…1という数）のnの倍数がある。
このとき、1/nは循環小数になるので、1/n={循環節}/(10^k-1)と表される。
よって、(10^k-1)/9={循環節}/9*N
・nが3で割り切れない場合
左辺は、すべての桁が1の数で、{循環節}/9倍したものである。
例 n=7のとき、1/7=0.{142857}=142857/999999なので、999999/9=(142857/9)*7
・nが3で割り切れる場合
n=3^r*M（Mは3で割り切れない自然数）として、
上記より、すべての桁が1の数をMの倍数にすることができる。
この桁数を3^r倍に増やせば、nで割り切れる。
例 n=33=3*11のとき、1/11=0.{09}=9/99なので、循環節の長さは2
これより、2*3=6個として、111111
n=2^p*5^qのとき、10^MAX(p,q)とすればよい。
以上をまとめると、
n=2^p*5^q*3^r*M（Mは2,5,3で割り切れない自然数）のとき、
1/Mの循環節の長さをkとすると、
(10^(k*3^r)-1)/9 *10^MAX(p,q) がnの倍数となる。
n=2^p*5^q*3^rのとき、
(10^(3^r)-1)/9 *10^MAX(p,q) がnの倍数となる。
（終り）
OPTION ARITHMETIC RATIONAL !多桁の整数
FOR N=1 TO 100
LET M=N
LET P=0
DO WHILE MOD(M,2)=0 !2^p
LET M=M/2
LET P=P+1
LOOP
LET Q=0
DO WHILE MOD(M,5)=0 !5^q
LET M=M/5
LET Q=Q+1
LOOP
LET R=0
DO WHILE MOD(M,3)=0 !3^r
LET M=M/3
LET R=R+1
LOOP
!!!PRINT P;Q;R;M !debug
FOR K=1 TO M-1 !1/Mの循環節の長さを求める 10^k≡1 mod mを満たす最小のk
IF modpow(10,K,M)=1 THEN EXIT FOR
NEXT K
LET W=(10^(lcm(K,3^R))-1)/9 *10^MAX(P,Q)
PRINT N; "×"; W/N; "="; W; "（";lcm(K,3^R);"個の1）"; " k=";K; "r=";R
!※
!LET W=(10^(K*3^R)-1)/9 *10^MAX(P,Q)
!PRINT N; "×"; W/N; "="; W; "（";K*3^R;"個の1）"; " k=";K; "r=";R
!※同値
!IF M>1 THEN !n=2^p*5^q*3^r*Mの場合
! FOR K=1 TO M-1 !1/Mの循環節の長さを求める 10^k≡1 mod mを満たす最小のk
! IF modpow(10,K,M)=1 THEN EXIT FOR
! NEXT K
! LET W=(10^(K*3^R)-1)/9 *10^MAX(P,Q)
! PRINT N; "×"; W/N; "="; W; "（";K*3^R;"個の1）"; " k=";K; "r=";R
!ELSE !n=2^p*5^q*3^rの場合
! LET W=(10^(3^R)-1)/9 *10^MAX(P,Q)
! PRINT N; "×"; W/N; "="; W; "（";3^R;"個の1）"; " r=";R
!END IF
NEXT N
END
EXTERNAL FUNCTION modpow(a,n,b) !a^n≡x mod b のxを返す ※nは非負整数
OPTION ARITHMETIC RATIONAL !多桁の整数
LET S=MOD(1,b)
DO WHILE n>0 !べき乗nを２進展開する
IF MOD(n,2)=1 THEN LET S=MOD(S*a,b) !ビットが１なら計算する
LET a=MOD(a*a,b)
LET n=INT(n/2)
LOOP
LET modpow=S
END FUNCTION
EXTERNAL FUNCTION gcd(a,b) !最大公約数
OPTION ARITHMETIC RATIONAL !多桁の整数
DO UNTIL b=0
LET t=b
LET b=MOD(a,b)
LET a=t
LOOP
LET gcd=a
END FUNCTION
EXTERNAL FUNCTION lcm(a,b) !最小公倍数
OPTION ARITHMETIC RATIONAL !多桁の整数
IF a>b THEN !少しでも桁あふれを防止するために大きい方を先に割る
LET lcm=(a/gcd(a,b))*b
ELSE
LET lcm=a*(b/gcd(a,b))
END IF
END FUNCTION
実行結果
1 × 1 = 1 （ 1 個の1） k= 1 r= 0
2 × 5 = 10 （ 1 個の1） k= 1 r= 0
3 × 37 = 111 （ 3 個の1） k= 1 r= 1
4 × 25 = 100 （ 1 個の1） k= 1 r= 0
5 × 2 = 10 （ 1 個の1） k= 1 r= 0
6 × 185 = 1110 （ 3 個の1） k= 1 r= 1
7 × 15873 = 111111 （ 6 個の1） k= 6 r= 0
8 × 125 = 1000 （ 1 個の1） k= 1 r= 0
9 × 12345679 = 111111111 （ 9 個の1） k= 1 r= 2
10 × 1 = 10 （ 1 個の1） k= 1 r= 0
11 × 1 = 11 （ 2 個の1） k= 2 r= 0
12 × 925 = 11100 （ 3 個の1） k= 1 r= 1
13 × 8547 = 111111 （ 6 個の1） k= 6 r= 0
14 × 79365 = 1111110 （ 6 個の1） k= 6 r= 0
15 × 74 = 1110 （ 3 個の1） k= 1 r= 1
16 × 625 = 10000 （ 1 個の1） k= 1 r= 0
17 × 65359477124183 = 1111111111111111 （ 16 個の1） k= 16 r= 0
18 × 61728395 = 1111111110 （ 9 個の1） k= 1 r= 2
19 × 5847953216374269 = 111111111111111111 （ 18 個の1） k= 18 r= 0
20 × 5 = 100 （ 1 個の1） k= 1 r= 0
21 × 5291 = 111111 （ 6 個の1） k= 6 r= 1
22 × 5 = 110 （ 2 個の1） k= 2 r= 0
23 × 48309178743961352657 = 1111111111111111111111 （ 22 個の1） k= 22 r= 0
24 × 4625 = 111000 （ 3 個の1） k= 1 r= 1
25 × 4 = 100 （ 1 個の1） k= 1 r= 0
26 × 42735 = 1111110 （ 6 個の1） k= 6 r= 0
27 × 4115226337448559670781893 = 111111111111111111111111111 （ 27 個の1） k= 1 r= 3
28 × 396825 = 11111100 （ 6 個の1） k= 6 r= 0
29 × 38314176245210727969348659 = 1111111111111111111111111111 （ 28 個の1） k= 28 r= 0
30 × 37 = 1110 （ 3 個の1） k= 1 r= 1
31 × 3584229390681 = 111111111111111 （ 15 個の1） k= 15 r= 0
32 × 3125 = 100000 （ 1 個の1） k= 1 r= 0
33 × 3367 = 111111 （ 6 個の1） k= 2 r= 1
34 × 326797385620915 = 11111111111111110 （ 16 個の1） k= 16 r= 0
35 × 31746 = 1111110 （ 6 個の1） k= 6 r= 0
36 × 308641975 = 11111111100 （ 9 個の1） k= 1 r= 2
37 × 3 = 111 （ 3 個の1） k= 3 r= 0
38 × 29239766081871345 = 1111111111111111110 （ 18 個の1） k= 18 r= 0
39 × 2849 = 111111 （ 6 個の1） k= 6 r= 1
40 × 25 = 1000 （ 1 個の1） k= 1 r= 0
41 × 271 = 11111 （ 5 個の1） k= 5 r= 0
42 × 26455 = 1111110 （ 6 個の1） k= 6 r= 1
43 × 2583979328165374677 = 111111111111111111111 （ 21 個の1） k= 21 r= 0
44 × 25 = 1100 （ 2 個の1） k= 2 r= 0
45 × 24691358 = 1111111110 （ 9 個の1） k= 1 r= 2
46 × 241545893719806763285 = 11111111111111111111110 （ 22 個の1） k= 22 r= 0
47 × 23640661938534278959810874704491725768321513 = 1111111111111111111111111111111111111111111111 （ 46 個の1） k= 46 r= 0
48 × 23125 = 1110000 （ 3 個の1） k= 1 r= 1
49 × 2267573696145124716553287981859410430839 = 111111111111111111111111111111111111111111 （ 42 個の1） k= 42 r= 0
50 × 2 = 100 （ 1 個の1） k= 1 r= 0
51 × 2178649237472766884531590413943355119825708061 = 111111111111111111111111111111111111111111111111 （ 48 個の1） k= 16 r= 1
52 × 213675 = 11111100 （ 6 個の1） k= 6 r= 0
53 × 20964360587 = 1111111111111 （ 13 個の1） k= 13 r= 0
54 × 20576131687242798353909465 = 1111111111111111111111111110 （ 27 個の1） k= 1 r= 3
55 × 2 = 110 （ 2 個の1） k= 2 r= 0
56 × 1984125 = 111111000 （ 6 個の1） k= 6 r= 0
57 × 1949317738791423 = 111111111111111111 （ 18 個の1） k= 18 r= 1
58 × 191570881226053639846743295 = 11111111111111111111111111110 （ 28 個の1） k= 28 r= 0
59 × 18832391713747645951035781544256120527306967984934086629 = 1111111111111111111111111111111111111111111111111111111111 （ 58 個の1） k= 58 r= 0
60 × 185 = 11100 （ 3 個の1） k= 1 r= 1
61 × 1821493624772313296903460837887067395264116575591985428051 = 111111111111111111111111111111111111111111111111111111111111 （ 60 個の1） k= 60 r= 0
62 × 17921146953405 = 1111111111111110 （ 15 個の1） k= 15 r= 0
63 × 1763668430335097 = 111111111111111111 （ 18 個の1） k= 6 r= 2
64 × 15625 = 1000000 （ 1 個の1） k= 1 r= 0
65 × 17094 = 1111110 （ 6 個の1） k= 6 r= 0
66 × 16835 = 1111110 （ 6 個の1） k= 2 r= 1
67 × 1658374792703150912106135986733 = 111111111111111111111111111111111 （ 33 個の1） k= 33 r= 0
68 × 1633986928104575 = 111111111111111100 （ 16 個の1） k= 16 r= 0
69 × 1610305958132045088566827697262479871175523349436392914653784219 = 111111111111111111111111111111111111111111111111111111111111111111 （ 66 個の1） k= 22 r= 1
70 × 15873 = 1111110 （ 6 個の1） k= 6 r= 0
71 × 156494522691705790297339593114241 = 11111111111111111111111111111111111 （ 35 個の1） k= 35 r= 0
72 × 1543209875 = 111111111000 （ 9 個の1） k= 1 r= 2
73 × 152207 = 11111111 （ 8 個の1） k= 8 r= 0
74 × 15 = 1110 （ 3 個の1） k= 3 r= 0
75 × 148 = 11100 （ 3 個の1） k= 1 r= 1
76 × 146198830409356725 = 11111111111111111100 （ 18 個の1） k= 18 r= 0
77 × 1443 = 111111 （ 6 個の1） k= 6 r= 0
78 × 14245 = 1111110 （ 6 個の1） k= 6 r= 1
79 × 14064697609 = 1111111111111 （ 13 個の1） k= 13 r= 0
80 × 125 = 10000 （ 1 個の1） k= 1 r= 0
81 × 1371742112482853223593964334705075445816186556927297668038408779149519890260631 = 111111111111111111111111111111111111111111111111111111111111111111111111111111111 （ 81 個の1） k= 1 r= 4
82 × 1355 = 111110 （ 5 個の1） k= 5 r= 0
83 × 133868808567603748326639892904953145917 = 11111111111111111111111111111111111111111 （ 41 個の1） k= 41 r= 0
84 × 132275 = 11111100 （ 6 個の1） k= 6 r= 1
85 × 130718954248366 = 11111111111111110 （ 16 個の1） k= 16 r= 0
86 × 12919896640826873385 = 1111111111111111111110 （ 21 個の1） k= 21 r= 0
87 × 1277139208173690932311621966794380587484035759897828863346104725415070242656449553 = 111111111111111111111111111111111111111111111111111111111111111111111111111111111111 （ 84 個の1） k= 28 r= 1
88 × 125 = 11000 （ 2 個の1） k= 2 r= 0
89 × 124843945068664169787765293383270911360799 = 11111111111111111111111111111111111111111111 （ 44 個の1） k= 44 r= 0
90 × 12345679 = 1111111110 （ 9 個の1） k= 1 r= 2
91 × 1221 = 111111 （ 6 個の1） k= 6 r= 0
92 × 1207729468599033816425 = 111111111111111111111100 （ 22 個の1） k= 22 r= 0
93 × 1194743130227 = 111111111111111 （ 15 個の1） k= 15 r= 1
94 × 118203309692671394799054373522458628841607565 = 11111111111111111111111111111111111111111111110 （ 46 個の1） k= 46 r= 0
95 × 11695906432748538 = 1111111111111111110 （ 18 個の1） k= 18 r= 0
96 × 115625 = 11100000 （ 3 個の1） k= 1 r= 1
97 × 1145475372279495990836197021764032073310423825887743413516609392898052691867124856815578465063 = 111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111 （ 96 個の1） k= 96 r= 0
98 × 11337868480725623582766439909297052154195 = 1111111111111111111111111111111111111111110 （ 42 個の1） k= 42 r= 0
99 × 1122334455667789 = 111111111111111111 （ 18 個の1） k= 2 r= 2
100 × 1 = 100 （ 1 個の1） k= 1 r= 0
|
|