余りが異なる(07/26大幅追記)
オンライン整数列大辞典に載っていなかったのでメモ
算トラ第４回の問１を見ていて思いついた問題
問い
2,3,…,Nで割った余りがすべて異なるような最小の自然数を求めよ。
ただし割り切れる場合は「余り０」として扱う。
※明らかに、(2～Nの最小公倍数)-1または2 は条件をみたすので、それより小さなものを探す問題
以下適当に回答
算トラ第４回の問１を見ていて思いついた問題
問い
2,3,…,Nで割った余りがすべて異なるような最小の自然数を求めよ。
ただし割り切れる場合は「余り０」として扱う。
※明らかに、(2～Nの最小公倍数)-1または2 は条件をみたすので、それより小さなものを探す問題
以下適当に回答
求める数をA[N]とする
A[2]=1
A[3]=2 (0,2) 3,4,5も条件を満たす。
A[4]=3 (1,0,3) 10,11も条件を満たす。
Nが偶数ならば、偶数かつ条件をみたすような数は(最大公約数)-2しか存在しないことは少し考えれば明らか。
（算トラの模範解答のように表を埋めて考える）
Nが奇数の時は(0,1,…,N-3,N-2)以外に、(0,1,…,N-3,N-1)のパターンが考えられるが、これが存在するのはNが素数の時のみ。
なので、以下、奇数とこのパターンについてのみ考える。
奇数で条件を満たすものについてわかったこと：
・素数が来ると候補数が倍になる（明らか）
・「２×素数p」が来ると候補数が半分になる
（pの余りはp-1以外のものが半分含まれるが、それらは必ず（？）重複する）
N=5のとき
12k+3 (1,0,3,2k+3) k=2→27、k=3→39
12k+11 (1,2,3,2k+1)k=2→35、k=4→59
(0,1,2,4)は34
以上よりA[5]=27
N=6のとき
27 (1,0,3,2,3)不適
35 (1,2,3,0,5)OK
39 (1,0,3,4,3)不適
59 (1,2,3,4,5)OK
A[6]=35
N=7の時
60k+35 (1,2,3,0,5,4k) k=1→95、k=5→335
60k+59 (1,2,3,4,5,4k+3）k=1→119、k=6→419
(0,1,2,3,4,6)は118
A[7]=95
N=8の時
420k+95 (1,2,3,0,5,4,4k+7)k=0→95
420k+119 (1,2,3,4,5,0,4k+7)k=0→119
420k+335 (1,2,3,0,5,6,4k+7)k=0→335
420k+419 (1,2,3,4,5,6,4k+3)k=1→839
A[8]=95
N=9の時
840k+95 (1,2,3,0,5,4,7,3k+5) k=1→935
840k+119 (1,2,3,4,5,0,7,3k+2) k=2→1799
840k+335 (1,2,3,0,5,6,7,3k+2) k=2→2015
840k+839 (1,2,3,4,5,6,7,3k+8) k=2→2519
A[9]=935
N=10
935 (1,2,3,0,5,4,7,8,5)不適
2015(1,2,3,0,5,6,7,8,5)不適
1799(1,2,3,4,5,0,7,8,9)OK
2519(1,2,3,4,5,6,7,8,9)OK
A[10]=1799
N=11
2520k+1799(1,2,3,4,5,0,7,8,9,k+6)k=0→1799、k=4→11879
2520k+2519(1,2,3,4,5,6,7,8,9,k)k=0→2519、k=10→27719
(0,1,2,3,4,5,6,7,8,10)は2518
A[11]=1799
N=12
上記４数、全て余り11でOK
A[11]=1799
N=13
27720k+1799(1,2,3,4,5,0,7,8,9,6,11,4k+5)k=5→140399、k=11→306719
27720k+2519(1,2,3,4,5,6,7,8,9,0,11,4k+10)k=0→2519、k=7→196559
27720k+11879(1,2,3,4,5,0,7,8,9,10,11,4k+10)k=7→205919、k=12→344519
27720k+27719(1,2,3,4,5,6,7,8,9,10,11,4k+3)k=9→277199、k=12→360359
(0,1,2,3,4,5,6,7,8,9,10,12)は277198
A[13]=2519
N=14
2519(1,2,3,4,5,6,7,8,9,0,11,10,13)OK
140399(1,2,3,4,5,0,7,8,9,6,11,12,7)不適
196559(13,1,2,3,4,5,6,7,8,9,0,11,12,13)OK
205919(1,2,3,4,5,0,7,8,9,10,11,12,7)不適
277199(1,2,3,4,5,6,7,8,9,10,11,0,13)OK
306719(1,2,3,4,5,0,7,8,9,6,11,10,7)不適
344519(1,2,3,4,5,0,7,8,9,10,11,6,7)不適
360359(1,2,3,4,5,6,7,8,9,10,11,12,13)OK
A[14]=2519
N=15
上記４数、全て余り14でOK
A[15]=2519
N=16
360360k+2519(1,2,3,4,5,6,7,8,9,0,11,10,13,14,8k+7)k=1→362879
360360k+196559(13,1,2,3,4,5,6,7,8,9,0,11,12,13,14,8k+15)k=0→196559
360360k+277199(1,2,3,4,5,6,7,8,9,10,11,0,13,14,8k+15)k=0→277199
360360k+360359(1,2,3,4,5,6,7,8,9,10,11,12,13,14,8k+7)k=1→720719
A[16]=196559
N=17
720720k+196559(0,11,12,13,14,15,5k+5)k=1→917279、k=9→6683039
720720k+277199(10,11,0,13,14,15,5k+14)k=3→2439359、k=14→10367279
720720k+362879(0,11,10,13,14,15,5k+14)k=3→2525039、k=14→10452959
720720k+720719(10,11,12,13,14,15,5k+4)k=6→5045039、k=16→12252239
(10,11,12,13,14,16)は5045038
A[17]=917279
N=18
上記8数全て余り17でOK
A[18]=917279
N=19
12252240k+n型
917279
k=0,917279(0,11,12,13,14,15,10,17,16)
k=11,135691919(0,11,12,13,14,15,10,17,18)
2439359
k=9,112709519(10,11,0,13,14,15,12,17,18)
k=17,210727439(10,11,0,13,14,15,12,17,16)
2525039
k=7,88290719(0,11,10,13,14,15,12,17,18)
k=15,186308639(0,11,10,13,14,15,12,17,16)
5045039
k=2,29549519(10,11,12,13,14,15,0,17,16)
k=13,164324159(10,11,12,13,14,15,0,17,18)
6683039
k=9,116953199(0,11,12,13,14,15,16,17,10)
k=15,190466639(0,11,12,13,14,15,16,17,18)
10367279
k=5,71628479(10,11,0,13,14,15,16,17,18)
k=10,132889679(10,11,0,13,14,15,16,17,12)
10452959
k=3,47209679(0,11,10,13,14,15,16,17,18)
k=8,108470879(0,11,10,13,14,15,16,17,12)
12252239
k=14,183783599(10,11,12,13,14,15,16,17,0)
k=18,232792559(10,11,12,13,14,15,16,17,18)
(10,11,12,13,14,15,16,18)は183783598
A[19]=917279
N=20
上記16数全て余り19でOK
A[20]=917279
N=21
上記16数全て余り20でOK
A[21]=917279
N=22
29549519
71628479
112709519
132889679
164324159
183783599
210727439
232792559
の8数が余り21で条件を満たす。残りは余り11で不適
A[22]=29549519
N=23
順にkとして
5,17 5,12 12,17 1,12
2,20 10,21 8,19 19,22がとれ、昇順に並べると
365682239
629909279
1193512319
1235591279
2073067919
2511709199
2865139199
2906220239
2926400399
3987023039
4070183039
4633786079
4655851199
4820175359
5072427359
5354228879
の16数
(10,11,12,13,14,15,16,17,18,19,20,22)は4655851198
A[23]=365682239
N=24
全てOK
A[24]=365682239
N=25
上から順にk=2,4,1,4,1,0,0,2,0,2,2,4,0,3,3,4で、昇順に並べると
2511709199
2865139199
2926400399
4655851199
6547741199
7427296799
11074139999
13614677999
14695480799
14778640799
20882861999
21135113999
22046824799
22652506799
26050701599
26771144399
の16数
A[25]=2511709199
N=26
2511709199
4655851199
6547741199
14695480799
20882861999
21135113999
22046824799
26771144399
の8数がOK 残りは余り13で不適
A[26]=2511709199
N=27
k=2,1,1,2,1,0,2,2がとれ、昇順に並べると
21135113999
31426995599
33318885599
47654006399
56053997999
68237769599
75589113599
80313433199
A[27]=21135113999
N=28
全て適
A[28]=21135113999
飽きた。以上まとめ
1,2,3,27,35,95,95,935,1799,
1799,1799,2519,2519,2519,196559,917279,917279,917279,917279,
917279,29549519,365682239,365682239,2511709199,
2511709199,21135113999,21135113999,…
A[2]=1
A[3]=2 (0,2) 3,4,5も条件を満たす。
A[4]=3 (1,0,3) 10,11も条件を満たす。
Nが偶数ならば、偶数かつ条件をみたすような数は(最大公約数)-2しか存在しないことは少し考えれば明らか。
（算トラの模範解答のように表を埋めて考える）
Nが奇数の時は(0,1,…,N-3,N-2)以外に、(0,1,…,N-3,N-1)のパターンが考えられるが、これが存在するのはNが素数の時のみ。
なので、以下、奇数とこのパターンについてのみ考える。
奇数で条件を満たすものについてわかったこと：
・素数が来ると候補数が倍になる（明らか）
・「２×素数p」が来ると候補数が半分になる
（pの余りはp-1以外のものが半分含まれるが、それらは必ず（？）重複する）
N=5のとき
12k+3 (1,0,3,2k+3) k=2→27、k=3→39
12k+11 (1,2,3,2k+1)k=2→35、k=4→59
(0,1,2,4)は34
以上よりA[5]=27
N=6のとき
27 (1,0,3,2,3)不適
35 (1,2,3,0,5)OK
39 (1,0,3,4,3)不適
59 (1,2,3,4,5)OK
A[6]=35
N=7の時
60k+35 (1,2,3,0,5,4k) k=1→95、k=5→335
60k+59 (1,2,3,4,5,4k+3）k=1→119、k=6→419
(0,1,2,3,4,6)は118
A[7]=95
N=8の時
420k+95 (1,2,3,0,5,4,4k+7)k=0→95
420k+119 (1,2,3,4,5,0,4k+7)k=0→119
420k+335 (1,2,3,0,5,6,4k+7)k=0→335
420k+419 (1,2,3,4,5,6,4k+3)k=1→839
A[8]=95
N=9の時
840k+95 (1,2,3,0,5,4,7,3k+5) k=1→935
840k+119 (1,2,3,4,5,0,7,3k+2) k=2→1799
840k+335 (1,2,3,0,5,6,7,3k+2) k=2→2015
840k+839 (1,2,3,4,5,6,7,3k+8) k=2→2519
A[9]=935
N=10
935 (1,2,3,0,5,4,7,8,5)不適
2015(1,2,3,0,5,6,7,8,5)不適
1799(1,2,3,4,5,0,7,8,9)OK
2519(1,2,3,4,5,6,7,8,9)OK
A[10]=1799
N=11
2520k+1799(1,2,3,4,5,0,7,8,9,k+6)k=0→1799、k=4→11879
2520k+2519(1,2,3,4,5,6,7,8,9,k)k=0→2519、k=10→27719
(0,1,2,3,4,5,6,7,8,10)は2518
A[11]=1799
N=12
上記４数、全て余り11でOK
A[11]=1799
N=13
27720k+1799(1,2,3,4,5,0,7,8,9,6,11,4k+5)k=5→140399、k=11→306719
27720k+2519(1,2,3,4,5,6,7,8,9,0,11,4k+10)k=0→2519、k=7→196559
27720k+11879(1,2,3,4,5,0,7,8,9,10,11,4k+10)k=7→205919、k=12→344519
27720k+27719(1,2,3,4,5,6,7,8,9,10,11,4k+3)k=9→277199、k=12→360359
(0,1,2,3,4,5,6,7,8,9,10,12)は277198
A[13]=2519
N=14
2519(1,2,3,4,5,6,7,8,9,0,11,10,13)OK
140399(1,2,3,4,5,0,7,8,9,6,11,12,7)不適
196559(13,1,2,3,4,5,6,7,8,9,0,11,12,13)OK
205919(1,2,3,4,5,0,7,8,9,10,11,12,7)不適
277199(1,2,3,4,5,6,7,8,9,10,11,0,13)OK
306719(1,2,3,4,5,0,7,8,9,6,11,10,7)不適
344519(1,2,3,4,5,0,7,8,9,10,11,6,7)不適
360359(1,2,3,4,5,6,7,8,9,10,11,12,13)OK
A[14]=2519
N=15
上記４数、全て余り14でOK
A[15]=2519
N=16
360360k+2519(1,2,3,4,5,6,7,8,9,0,11,10,13,14,8k+7)k=1→362879
360360k+196559(13,1,2,3,4,5,6,7,8,9,0,11,12,13,14,8k+15)k=0→196559
360360k+277199(1,2,3,4,5,6,7,8,9,10,11,0,13,14,8k+15)k=0→277199
360360k+360359(1,2,3,4,5,6,7,8,9,10,11,12,13,14,8k+7)k=1→720719
A[16]=196559
N=17
720720k+196559(0,11,12,13,14,15,5k+5)k=1→917279、k=9→6683039
720720k+277199(10,11,0,13,14,15,5k+14)k=3→2439359、k=14→10367279
720720k+362879(0,11,10,13,14,15,5k+14)k=3→2525039、k=14→10452959
720720k+720719(10,11,12,13,14,15,5k+4)k=6→5045039、k=16→12252239
(10,11,12,13,14,16)は5045038
A[17]=917279
N=18
上記8数全て余り17でOK
A[18]=917279
N=19
12252240k+n型
917279
k=0,917279(0,11,12,13,14,15,10,17,16)
k=11,135691919(0,11,12,13,14,15,10,17,18)
2439359
k=9,112709519(10,11,0,13,14,15,12,17,18)
k=17,210727439(10,11,0,13,14,15,12,17,16)
2525039
k=7,88290719(0,11,10,13,14,15,12,17,18)
k=15,186308639(0,11,10,13,14,15,12,17,16)
5045039
k=2,29549519(10,11,12,13,14,15,0,17,16)
k=13,164324159(10,11,12,13,14,15,0,17,18)
6683039
k=9,116953199(0,11,12,13,14,15,16,17,10)
k=15,190466639(0,11,12,13,14,15,16,17,18)
10367279
k=5,71628479(10,11,0,13,14,15,16,17,18)
k=10,132889679(10,11,0,13,14,15,16,17,12)
10452959
k=3,47209679(0,11,10,13,14,15,16,17,18)
k=8,108470879(0,11,10,13,14,15,16,17,12)
12252239
k=14,183783599(10,11,12,13,14,15,16,17,0)
k=18,232792559(10,11,12,13,14,15,16,17,18)
(10,11,12,13,14,15,16,18)は183783598
A[19]=917279
N=20
上記16数全て余り19でOK
A[20]=917279
N=21
上記16数全て余り20でOK
A[21]=917279
N=22
29549519
71628479
112709519
132889679
164324159
183783599
210727439
232792559
の8数が余り21で条件を満たす。残りは余り11で不適
A[22]=29549519
N=23
順にkとして
5,17 5,12 12,17 1,12
2,20 10,21 8,19 19,22がとれ、昇順に並べると
365682239
629909279
1193512319
1235591279
2073067919
2511709199
2865139199
2906220239
2926400399
3987023039
4070183039
4633786079
4655851199
4820175359
5072427359
5354228879
の16数
(10,11,12,13,14,15,16,17,18,19,20,22)は4655851198
A[23]=365682239
N=24
全てOK
A[24]=365682239
N=25
上から順にk=2,4,1,4,1,0,0,2,0,2,2,4,0,3,3,4で、昇順に並べると
2511709199
2865139199
2926400399
4655851199
6547741199
7427296799
11074139999
13614677999
14695480799
14778640799
20882861999
21135113999
22046824799
22652506799
26050701599
26771144399
の16数
A[25]=2511709199
N=26
2511709199
4655851199
6547741199
14695480799
20882861999
21135113999
22046824799
26771144399
の8数がOK 残りは余り13で不適
A[26]=2511709199
N=27
k=2,1,1,2,1,0,2,2がとれ、昇順に並べると
21135113999
31426995599
33318885599
47654006399
56053997999
68237769599
75589113599
80313433199
A[27]=21135113999
N=28
全て適
A[28]=21135113999
飽きた。以上まとめ
1,2,3,27,35,95,95,935,1799,
1799,1799,2519,2519,2519,196559,917279,917279,917279,917279,
917279,29549519,365682239,365682239,2511709199,
2511709199,21135113999,21135113999,…
コメント
コメントの投稿
トラックバック
