😊出会いの泉😊

以下合同式はすべてmod10
2^4=16≡6
3^4=81≡1
4^2=16≡6
5^n≡5
6^n≡6
7^4=2401≡1
8^4=4096≡6
9^2=81≡1
から
N≡1^100+2^100+3^100+4^100+5^100+6^100+7^100+8^100+9^100
=1+(2^4)^25+(3^4)^25+(4^2)^50+5^100+6^100+(7^4)^25+(8^4)^25+(9^2)^50
≡1+6+1+6+5+6+1+6+1=33≡3
なので、3。

与式≡1+0+1+0+1+0+1+0+1≡1 (mod2)

また、p=5 についてフェルマーの小定理を用いると、
与式≡1+1+1+1+0+1+1+1+1≡3 (mod5)

よって
与式≡3 (mod10)

お二人とも性質を熟知されていることがビンビン伝わってきます。
ひょんなことから5乗においては,a=1,2,3,･･･,9で
a^5≡a (mod 10)
が成立していることに気付いて、これを活用できる問題として作成しておりました。

特にDD++さんの最も簡潔な近道に感激しました。
なおこれがmod 100
となった場合はどの様に対処できるのですか？

> なおこれがmod 100となった場合はどの様に対処できるのですか？

以下合同式はすべてmod100
n^2≡nの解は0,1,25,76
(つまりこの4つは何乗してもmod100で不変)
2^20=1048576≡76
3^20=3486784401≡1
4^10=1048576≡76
5^2=25≡25
6^5=7776≡76
7^4=2401≡1
8^20=1152921504606846976≡76
9^10=3486784401≡1
11^10=25937424601≡1
なので
N=11^100+22^100+33^100+44^100+55^100+66^100+77^100+88^100+99^100
=11^100(1^100+2^100+3^100+4^100+5^100+6^100+7^100+8^100+9^100)
={(11^10)^10}{1+(2^20)^5+(3^20)^5+(4^10)^10+(5^2)^50+(6^5)^20+(7^4)^25+(8^20)^5+(9^10)^10}
≡1・(1+76+1+76+25+76+1+76+1)
=333≡33
となり、100で割った余りは33。

オイラーのトーシェント関数を使います。

オイラーの定理より、a が 5 の倍数でないとき
a^φ(25)=a^20≡1 (mod25)
なので、
与式≡1+1+1+1+0+1+1+1+1≡8 (mod25)

また、
与式≡1+0+1+0+1+0+1+0+1≡1 (mod4)

よって
与式≡33 (mod100)

ついでに 1000 で割る場合も。

オイラーの定理より、a が 5 の倍数でないとき
a^φ(125)=a^100≡1 (mod125)
なので、
与式≡1+1+1+1+0+1+1+1+1≡8 (mod125)

また、
与式≡1+0+1+0+1+0+1+0+1≡5 (mod8)

よって
与式≡133 (mod1000)


10000 で割るとなると手を変えないといけませんね。

303/320=3030/3200　という見方は、邪道ですかね？

問題文の表現が「分子から引く」「分母に足す」なわけですので、

問題：303/320 の分子は何か
解答：3030

を正解とするべきかどうかという話になりますね。
私は不正解とすべきだと思いますがどうでしょう？

また、その論を認める場合、303/320 を 6060/6400 とみなすことで 1966 など別の解も認められてしまいますね。
極端には 303/320 を (
303/98.3)/(320/98.3) と見做せば 1 も解になり、この問題の答えは「任意の整数」になるかと思います。

図での
AD=a,BC=b,CD=c,AB=xとおいて,この4つが整数となれる組合せ調べたら
(a,b,c)=(1,4,7)->x=9
=(2,5,7)->x=10
=(3,6,7)->x=11
=(4,7,7)->x=12
=(5,8,7)->x=13
=(6,9,7)->x=14
=(7,10,7)->x=15
　　　　･････････････
一般に(a,b,c)=(n,n+3,7)->x=n+8 (n=1,2,3,･･･)

または
(a,b,c)=(1,6,7)->x=9
=(2,7,7)->x=10
=(3,8,7)->x=11
=(4,9,7)->x=12
=(5,10,7)->x=13
=(6,11,7)->x=14
=(7,12,7)->x=15
　　　　･････････････
一般に(a,b,c)=(n,n+5,7)->x=n+8 (n=1,2,3,･･･)

c=7と設定しておくことがポイントになりそうです。

c=13 や c=19 でも可能なのでは。
おそらく 6n+1 型素因数を少なくとも 1 つ持っていることが条件じゃないでしょうか。

確かに6*n+1型の数は

7^2=3^2+8^2-3*8
=5^2+8^2-5*8

13^2=7^2+15^2-7*15 =>(a,b,c)=(n,n+8,13)->x=n+15 (n=1,2,3,･･)
=8^2+15^2-8*15 =>(a,b,c)=(n,n+7,13)->x=n+15 (n,1,2,3,･･)が構成できる。

19^2= 5^2+21^2- 5*21 =>(a,b,c)=(n,n+16,19)->x=n+21 (n=1,2,3,･･)
=16^2+21^2-16*21 =>(a,b,c)=(n,n+5,19)->x=n+21 (n=1,2,3,･･)

25^2=25^2+25^2-25*25(これは例外）

31^2=11^2+35^2-11*35=>(a,b,c)=(n,n+24,31)->x=n+35 (n=1,2,3,･･)
=24^2+35^2-24*35=>(a,b,c)=(n,n+11,31)->x=n+35 (n=1,2,3,･･)
以下同様
37^2= 7^2+40^2-7*40
=33^2+40^2-24*40

43^2=13^2+48^2-13*48
=35^2+48^2-35*48

49^2=16^2+55^2-16*55
=39^2+55^2-39*55

･･････････

と60°の角度を有する三角形の三辺を与えていく２組を
与えてくれますね。

理論的に計算する方法はわかりませんでしたので、
プログラムを作って調べました。その結果は
人数100,1000,10000,100000,1000000,10000000,100000000人に対して
(s,w)=(24, 97),(142, 997),(1015, 9997),(7986, 99997),
(66164, 999991),(565513, 9999985),(4944199, 99999967)
となりました。

管理人さんからのコメントで
単純にくじ引きで、２４人の当選者を決めてもらった方が、並ぶ人の感情としては納
得できると思うのだが．．．。

とありましたが、せっかく早く並んでいた1,2,3あたりの人が籤で当たらなかったら、それこそ不満が溜まりそうです。
これだと比較的早く並んだ方の人が選ばれやすい傾向を持てる気がしたので、このストーリーで表現していました。

20桁だと条件を満たすものが44個もあります。
桁数の最大は25桁で、値は
3608528850368400786036725
です。

44個の中に偶数の数だけのdigitsで構成されたものはありますか？

1つだけありました。
48000688208466084040です。

ちなみに、桁数別の個数は以下のようになります。
1桁: 9個
2桁: 45個
3桁: 150個
4桁: 375個
5桁: 750個
6桁: 1200個
7桁: 1713個
8桁: 2227個
9桁: 2492個
10桁: 2492個
11桁: 2225個
12桁: 2041個
13桁: 1575個
14桁: 1132個
15桁: 770個
16桁: 571個
17桁: 335個
18桁: 180個
19桁: 90個
20桁: 44個
21桁: 18個
22桁: 12個
23桁: 6個
24桁: 3個
25桁: 1個

この数列は↓こちらにありましたが、
http://oeis.org/A143671
こちらでは1桁の「0」も入れているようで、1桁が10個になっています。

もともとこの疑問に突き当たったのが
1～９の数字を一個ずつ含む9桁の数があり
「上k桁がkの倍数」(k=1～9)
を満たすものを探すと381654729である。

という記事でした。
何とかこれをプログラムを使って探し出そうと試みて
苦心惨憺の末5分ほどの運用時間で結果が手に入った。
実行させる前に9!の全順列を準備したり、上からk桁で
切り取る作業をやらせたりと、言ってみれば全検索を
掛けた上での作業でした。

これらについて更に調べてみると、別にプログラムに頼らずとも
論理的に導けている記事もありました。

そしてそこに話題が広がり
例の偶数{0,2,4,6,8}だけを使った20桁の整数（48000688208466084040)
が紹介されていました。

はて9桁でもあんだけ候補がありながら、これが20桁ともなると
5^20 = 95367431640625
ととても全検索を掛けようにも時間がいくらあっても無理だ！

そこで例の出題になったという経緯でした。


それに対し、らすかるさんのこの結果です。
これが如何に天文学的膨大な対象を処理されているか、想像しただけでも
腰が抜けそうです。
しかも半日もかからない時間で処理済みとなっている。

コンピュータさえあれば計算はあっという間に出来るだろうと思われるかも
知れませんが、そのオーダーが25桁などの桁になれば、とてもとても時間が
かかります。

以前コンピュータが高性能なのだろうと思っていたら、らすかるさんから
普通の使用のものを使っていますとの返事を頂いているので、これは正しく
プログラム力の成せる技でしかありません。（しかし神業としか思えません。）

もしかして、論理的に出せる数値なんですか？

論理的に出すのは候補が多すぎておそらく大変だと思います。
上から1桁ずつ増やして条件に当てはまるものだけその下の桁を
処理するようにすれば、時間は大してかかりません。
1桁目は1～9の9通り
2桁目は1桁目の9通りに対して各5通りなので2桁目までで45通り
3桁目はその45通りに対して3の倍数になるものなので150通り
（最初の2桁で合計が3の倍数である
　12,18,24,30,36,42,48,54,60,66,72,78,84,90,96
　の15個は3桁目が0,3,6,9の4通り、残りの30個は3通りずつなので
　15×4+30×3=150通り）
4桁目は3桁目が偶数なら0,4,8の3通り、奇数なら2,6の2通り→375通り
5桁目は0か5なので4桁までの2倍の750通り
・・・
ちなみに私が作ったプログラムの実行時間は
全桁数全通りで約0.13秒です。

らすかるさんの全桁数全通りで約0.13秒です。
のコメントを見て、改めてプログラムを見直してみたら
全体から選ぶんじゃなく、その条件を満たす数を小さい順に構成していけばいいんだ！
という決定的にお門違いの攻め方をしていたことに気付きました。
改めてプログラムを組んでみたら（３行程度）まさに1秒もかからない時間で
各桁の個数と具体的整数をすべて計算してくれますね。
25桁までは存在し、その後は構成できないとは初めて認識できました。

1桁: 最大1個 (2,3,5,7)
2桁: 最大2個 (13,17,37,79)
3桁: 最大4個 (149,179,379)
4桁: 最大11個 (1237,1279)
5桁: 最大39個 (13789)
6桁: 最大148個 (123479)
7桁: 最大731個 (1235789)
8桁: 最大4333個 (12345769)
9桁: 最大26519個 (102345697)
10桁: 最大152526個 (1123465789)
OEISにはこんな数列も載っているのですね。
↓
http://oeis.org/A065851
ここによると11桁は最大1251724個だそうですが、
11桁以上は時間がかかりそうなのでパス。

1桁: 2, 3, 5, 7
2桁: 11, 13, 17, 37, 79
3桁: 113, 197, 199, 337
4桁: 1193, 3779
5桁: 11939, 19937
6桁: 193939, 199933
7桁～18桁: なし
19桁: 1111111111111111111
20桁～22桁: なし
23桁: 11111111111111111111111