急速に大きくなる数の代表として階乗の数がよく登場する。

1! = 1
2! = 2
3! = 6
4! = 24
5! = 120
6! = 720
7! = 5040
8! = 40320
9! = 362880
10! = 3628800
11! = 39916800
12! = 479001600
13! = 6227020800
14! = 87178291200
15! = 1307674368000
16! = 20922789888000
17! = 355687428096000
18! = 6402373705728000
19! = 121645100408832000
20! = 2432902008176640000

　この様に、5!以降は最後には0がいくつも並んでしまうものとなっていく。

　そこで、最後に並ぶ0を取り除けば、

14!->871782912 の9個の数字が並び
15!->1307674368の10個の数が並ぶ

　そこで、この先一般に、n!において最後に並ぶ0は省いてその手前に並ぶことに成る10個
の並びをF(n)で表すことにすると、

F(16)=0922789888=>922789888
F(17)=5687428096
F(18)=2373705728
F(19)=5100408832
F(20)=200817664

なるものと記号を定義しておく。

　しかし、例え手元にコンピュータがあるにしても、F(100000000)、F(10^9)、F(10^10)辺りから
通常のメモリーの搭載ではもう受け付けなくなって来るし、その計算も想像以上に時間がか
かる。

　ところで、n!の値はこの先もずっと続くし定義はちゃんとされているので、その従来の探し方
に頼らない方法を編み出し、次の階乗での最後に並ぶであろう10個の数字を見つけてほしい。

(1)F(100)
(2)F(10^12)
(3)F(10^100)


　DD++ さんからのコメントです。（令和７年６月５日付け）

　とりあえず10億まで。合ってますかね？

　ここから先の戦略も頭の中にはありますが、ここまでを確認した後にしたいので。


　ＧＡＩ さんからのコメントです。（令和７年６月５日付け）

　完全に同じになっています。よかったら参考にしたいのでコードを掲載しておいてくれませんか？


　DD++ さんからのコメントです。（令和７年６月５日付け）

　よかったです。コードよりもアルゴリズムを日本語で書いといた方がいいと思いますので、
そっち置いときますね。

　16≦n≦数億の場合を想定します。整数nが素因数に5をm個もつとして、
g(n) = n*(4882813/5)^mとします。

　階乗の代わりにg(1)からg(n)までのすべての積をとって5^10で割った余りを求めると、
f(n)を5^10で割った余りが得られます。

　これは、積を計算するたびに余りを求めることで、限られた桁数内で計算できます。
（実際は4882813の累乗も後からまとめて計算しています）

　求めた値に1787109376を掛けて10^10で割った余りを取ると、f(n)の値がわかります。
（n≧16だとf(n)が必ず2^10の倍数であることを利用しているので、n≦15では誤った値が出ます）


　ＧＡＩ さんからのコメントです。（令和７年６月６日付け）

　DD++ さんのアイデアをプログラムしてみた。

gp > f(n)={r1=4882813;r2=1787109376;}lift(Mod(lift(Mod(prod(i=1,n,i*(r1/5)^valuation(i,5)),5^10))*r2,10^10))
gp > for(n=1,9,print("10^"n";"f(10^n)))

10^1;625036288
10^2;5210916864
10^3;27753472
10^4;8001579008
10^5;4957162496
10^6;5058412544

　これから先はとても時間が必要となっていきました。

　確かに、正確に0をトリムされた後の下10個の数が並ぶことができますね。

　ところで、不思議なのは、r1、r2 の値は何処から現れるのでしょうか？r1、r2 以外にもこの
ような性質を有する(r1,r2)の組は取れるのでしょうか？


　DD++ さんからのコメントです。（令和７年６月６日付け）

　C++ だと、10^9でもちょっと一服くらいの時間で出てきましたが、言語による速度差って意
外と大きいのですね。あるいは、(r1/5)の累乗のところで、mod5^10の結果だけわかればい
いのに律儀に累乗の結果を出してからmod取ってるせいで、一部数値で桁数が爆発している
影響かな？

　r1とr2は、

r1 = (5^10+1)/2
r2 = 183*5^10+1 = 1745224*2^10

です。つまり、mod5^10においてr1を掛ける行為は実質2で割る操作に相当します。

　また、r2は、x≡k (mod5^10)　、x≡0 (mod2^10)　を連立した結果が、x≡r2*k (mod10^10)
であることに由来します。


　らすかるさんからのコメントです。（令和７年６月６日付け）

　あまり自信がありませんが、F(10^100)=3738735616　ですか？


　ＧＡＩ さんからのコメントです。（令和７年６月６日付け）

　凄い！ピッタリ同じ値です。どれほどの時間がかかりましたか？プログラムの概要を解説
お願いします。


　らすかるさんからのコメントです。（令和７年６月６日付け）

　約2分です。→後に高速化して約16秒になりました。

　(10^100)!から素因数2と5を除いたものをmod10^10で計算し、2^(75*10^98-87)をmod10^10
で計算して掛け合わせた下位10桁です。

　後者は簡単ですね。前者は、

　1〜10^100を2^m×5^n×N（Nは2でも5でも割り切れない数）の m、n で24002通りに分類し、
それぞれをmod10^10で計算してmod10^10で掛けます。

　とりあえず10^10までを計算したら、

　1×3×7×9×11×13×…×9999999999≡1 (mod10^10)

ということがわかりましたので、例えば、

　1×3×7×9×…×3141592653589793238462643383279 (mod10^10)

を計算したいときは、終値は下位10桁だけとって

　1×3×7×9×…×2643383279 (mod10^10)

を計算すれば十分です。これを使って、

(m,n)=(0,0): 1×3×7×9×…×(10^100-1) ≡ 1×3×7×9×…×9999999999 ≡ 1
(m,n)=(1,0): 1×3×7×9×…×(10^50-1) ≡ 同様に1
・・・
(m,n)=(191,44): 終値(10^100/2^191/5^44余り切り捨て)の下位10桁をとって、

　 1×3×…×519385729 ≡ 9917681069
↑これは単なる例です
・・・

そして、これら24002個の数をmod10^10で掛け合わせると5385817123で、
2^(75*10^98-87)≡6813576192を掛けて3738735616を算出しました。

　1×3×7×9×…×9999999999 のmod10^10での計算が2分弱で、24002通りの計算を高
速化するために途中計算で得られた

1×3×7×9×…×9999
1×3×7×9×…×19999
1×3×7×9×…×29999
・・・
1×3×7×9×…×9999999999
（全てmod10^10）を要素数1000000の配列に保持し、24002通りそれぞれを最大約4000回の
乗算で済むようにした結果、1×3×7×9×…×9999999999の計算以外は誤差程度の時間
になりました。

＃1×3×7×9×11×…(mod 10^10)の計算で10^10未満の数の積を求めるのに、64ビット
では足りず128ビット演算していたのですが、128ビットのmod演算がやたら遅かったので
mod 2^10とmod 5^10を別々に求めて、n≡a (mod 2^10)、n≡b (mod 5^10) のとき、
n≡8212890625a+1787109376b (mod 10^10)
で求めるようにしたところ、実行時間は約2分→約16秒になりました。


　DD++ さんからのコメントです。（令和７年６月７日付け）

　高速化により、O(n)だったのをO(logn)に改善。10^18に対してpaiza.io環境で0.08sで求まる
ようになりました。
（結果自体はらすかるさんに劣るものですが、今後の自分のデバッグ用も兼ねて）

f(10^2) = 5210916864
f(10^3) = 27753472
f(10^4) = 8001579008
f(10^5) = 4957162496
f(10^6) = 5058412544
f(10^7) = 2574194688
f(10^8) = 2840754176
f(10^9) = 933638144
f(10^10) = 6441946112
f(10^11) = 1378167808
f(10^12) = 283416576
f(10^13) = 9067109376
f(10^14) = 4534834176
f(10^15) = 2576510976
f(10^16) = 9755143168
f(10^17) = 3894653952
f(10^18) = 5407435776

あとは多倍長整数を使えば10^100でも一瞬だと思いますが、それじゃ美しくないので、2^63
以内の計算だけでなんとかならないか試行錯誤中。


　らすかるさんからのコメントです。（令和７年６月７日付け）

　せっかくプログラムを作ったので大きい方も。

F(10^100) = 3738735616
F(10^200) = 6923037696
F(10^300) = 9519908864
F(10^400) = 2065393664
F(10^500) = 6678018048
F(10^600) = 9989215232
F(10^700) = 6221698048
F(10^800) = 3924201472
F(10^900) = 1886432256
F(10^1000) = 1896479744
F(10^2000) = 4883249152
F(10^3000) = 6688616448
F(10^4000) = 8291796992

　でも合っているかどうかはわかりません。(10^4000)!とか、巨大すぎて想像しにくいですね。
(10^100)!でも十分大きいですが。


　DD++ さんからのコメントです。（令和７年６月７日付け）

　どうやら一致してそうです。

f(10^10000) = 4592166912
f(10^20000) = 310350848
f(10^30000) = 8320806912
f(10^40000) = 1363283968
f(10^50000) = 7217645568
f(10^60000) = 5054093312
f(10^70000) = 7207071744
f(10^80000) = 6996748288
f(10^90000) = 3016684544

f(10^100000) = 9734950912 (0.46sec)
f(10^150000) = 4346172416 (0.83sec)
f(10^200000) = 9418829824 (1.32sec)
f(10^250000) = 7569364992 (1.94sec)

　この辺がpaiza.io環境（実行時間2秒制限）での限界でした。

　以下、自前環境

f(10^300000) = 5518877696
f(10^400000) = 6031537152
f(10^500000) = 7823699968
f(10^600000) = 4702614528
f(10^700000) = 5214944256
f(10^800000) = 6104402944
f(10^900000) = 7742903296
f(10^1000000) = 8226093056

　10^nに対して、主要部分の計算はO(n)で済んでるのに、前計算の「2^nを五進数で求める」
という部分でO(n^2)かかってる残念さ。

　巨大な累乗数の基数変換をO(n*logn)くらいでやる実装が簡単なアルゴリズムないですかね？
カラツバ法を使えばO(n^1.59)くらいまでは改善するけど書くのが面倒……。


　ＧＡＩ さんからのコメントです。（令和７年６月７日付け）

　f(10^100) = 3738735616 と同じ値「3738735616」を取る他の f(s) ｓ<10^100 の値は存在す
るのですか?


　DD++ さんからのコメントです。（令和７年６月７日付け）

　コード書いてる途中で気づいたんですが、　f(4*5^20*n) = f(4*5^19*n)　が成り立つので、
2*10^99や4*10^98、以下、2^81*10^19 までの81個は同じ値になりますね。

　2^82*10^18 が一致するかどうかは……9*10^18以上は10の累乗特化のやつしか手元に
ないのでわかりません。


　らすかるさんからのコメントです。（令和７年６月７日付け）

　f(s)=3738735616 となるsは、

16257603, 19004367, 20867632, 21217365, 33069263,42564599, 42631627, 45460609,
52492698, 53300341, …

のように、たくさんあるようです。最小のsは 16257603 です。


　ＧＡＩ さんからのコメントです。（令和７年６月７日付け）

　f(n)　10≦n≦10000　の中で、同じ値へ至る組合せを探してみたら、

[484,8121]==>395157504　、[600,3734]==>3891178496　、[724,3900]==>8483543424
[1091,7460]==>608149504　、[1260,5976]==>3417107456　、[1899,2110]==>4827099136
[1928,2625]==>9962140672　、[4152,7094]==>9036347392　、[4177,9681]==>7609266176
[5051,5145]==>8307800064　、[5763,8822]==>5245555712　、[6674,9771]==>6639161344

の12組がいました。[99,100]、[999,1000]、[9999,10000]は除いています。

　何か法則が見えてこないかな〜、前もって、f(10^100)=f(16257603)を判断できればもっと短
時間で手に入るのに･･･。

　なお、この疑問はEuler Projectでのproblem 160から発生していて、そこでは10桁ではなく
5桁での問題であり(5桁の数字を探す関数をf5としています。）、解決の一つの方法として、

if n%2500==0 なら、任意の正整数xに対し、f5(n)=f5(n*5^x) が成立することを利用し、
f5(10^12)=f5(256000*5^8) で、256000%2500==0 を満たすので
　　　　=f5(256000)
を調査することで
　　　　=16576
で解決できるやり方があるという。（随分桁数を節約できる)

　この方法は5桁に限って成立するようで、10桁ではズレてしまいます。これに代わる方法
（法則）は無いものか？


　DD++ さんからのコメントです。（令和７年６月７日付け）

　まさに私が言った　f(4*5^20*n) = f(4*5^19*n)　じゃないですかね。

　5桁だと、f(4*5^5*n) = f(4*5^4*n)　で成立するんですね。

　ということは、10桁だと、f(4*5^10*n) = f(4*5^9*n)　で成り立つのかな？

　あと、Project Eulerは問題101以降は解法言及禁止なので、少なくとも表向きは「Project Euler
とは無関係に思いついた問題です」にしとかないとまずい気が．．．。


　ＧＡＩ さんからのコメントです。（令和７年６月７日付け）

　f(4*5^20*n) = f(4*5^19*n)の等式は、f(4*5^19*n) = f(4*5^18*n) = f(4*5^17*n)=･･･= f(4*5^9*n)
まで伸ばせませんかね？(上方へは5^xの部分はどこまでもOK)

　従って、

f(10^100)=f(4*5^100*2^98)=f(4*2^98*5^9)
=f(2^100*5^9)=f(2475880078570760549798248448000000000)

まで桁を下げて調査でき(101桁を37桁に縮小化)、これを計算させて、%=3738735616　が手
に入る。


　DD++ さんからのコメントです。（令和７年６月７日付け）

　さあ、どうなんでしょうね。思いつくことはありますが、Project Eulerの101以降の問題である
と名言されてしまった以上、解法につながることが迂闊に言えなくなってしまいましたので。


　ＧＡＩ さんからのコメントです。（令和７年６月７日付け）

　Project Eulerの101以降の問題であると名言されてしまった以上、解法につながることが
迂闊に言えなく・・・

　こんな規則があったとは思ってもいませんでした。

　でも、OEIS「A347105」などでは、Project Euler, Digital root sums of factorisations, Problem 159.
の様にリンクと共に解決に直接結びつく結果がいろいろなコードでのプログラムとともに数値が
並び公開されています。

　この様に解決するのに大いに参考になる情報はいろいろな所にアクセス可能の状態にあり
ます。またこのごろはAI（ChatGTPやGemminiやCopilotなどなど)にプログラムを好きなコード
で作ってもらうように頼めば難なく示していきます。ただこれが余り頼りにはなりませんが・・・

　でも考える方向性などは窺い知ることはできます。

　DD++さんがためらわれているのはこの解決に参考になることは一切表には出してはいけ
ないものだというお考えをお持ちだからなのですか？


　DD++ さんからのコメントです。（令和７年６月７日付け）

　ためらってなどいません。ためらうまでもなく、この場では絶対に明かさない判断をしました
ので。

　問題番号と答えをセットで載せるのは、ミステリ小説の犯人をネタバレするのと同じです。
ダメなのは当たり前でしょう。ましてProject Eulerは「教育のためなら解法（直接の答えでは
ない）をネタバレしていい問題」「ネタバレ厳禁な問題」を厳密に区分して、利用上の注意とし
て明記しています。運営のその意向を尊重できないなら、GAIさんはProject Eulerを利用すべ
きではないと思います。


　ＧＡＩ さんからのコメントです。（令和７年６月１０日付け）

　改めて、Project Euler.netのabout部分の長い英文で書かれたものを日本語に翻訳させた
上で読んでみました。
（通常電化製品等の取扱い説明書など日本語で書かれている場合でも、隅々まで読むこと
などほとんどなく、ましてや英文で書かれていれば尚更の習慣から全く目にも留めませんで
した。)

　確かに、最初の100題はそれらの問題とその解決策を他の場所で議論することを許可しま
す。

の内容が示してありました。

と言うことは、101からは他では議論するなとなるわけなのか。

　その目的をDD++さんは推理小説になぞらえて解説されていたので、私もその筋で説明しま
すと、犯人は誰なのか？実は小説を最後まで読めば、自ずと判明され、またそれが最後まで
読んでみたい強い動機ともなれます。

　ところが、数学的問題（特に101番以降など）では、途中まではおのれの足を一歩ずつ前に
踏み出して行けば、ある地点までは辿り着けるのですが、如何せん一歩も前に進めなくなる
ことがしばしば発生するのです。

　すると、サイトをいろいろ検索しだしたり、あるいはAIを頼りに質問したり、図書館に本を借
りに行ったり、他人様のお知恵が利用できないかともがきます。

　考えてみると、自分独自で何か発見できてきたかと思うと殆んどの事項が先人の知恵や道
具に頼っていることに改めて気付かされます。

　一週間考え作業し問題のAnswer欄に自分なりの答えを入力しても×の判定を何度も受け、
こうなると心が折れ、フラストレーションが溜まるばかりの状態が続きます。

　逆に正解を得ると、それを解決した世界中の人たちからのアイデアや方法論を参考に見れ
る仕組みがされていて、苦労した後にはなんて素晴らしい方法が隠れていたんだとか、プログ
ラムの仕方が言語によりこうも違えるんだとか、ほんとに心に染みわたります。

　ところが、時々この問題に非常に関連する情報が多く含まれるサイトに出会うことが起こる
のです。

　例のOEISにもそれが登場していることもしばしばなのです。あるいはDD++さんには信じられ
ないかも知れませんが、各問題の正解だけを載せている人もいるのです。

　Euler 防衛軍の方には、目くじらものでしょうが、何処にもこれを解決する情報もなく、手も足
もでないままでは、裏に潜んでいるダイアモンドの輝きを見ることが叶いません。

　こんな時、人の口には戸を立てられぬとはよく言ったもので、私のような者にはそんな情報
はとても有難いのです。

　私も独力で何日もかけて考え続け自分の力でこじ開けたいのですが、でも限界があります。

　それとは知らず、この場で色々質問していたことをお詫びします。


　DD++ さんからのコメントです。（令和７年６月１０日付け）

　まあ、そもそも最初からPEの解答を求めている人しか来ないような場所で話すのであれば、
ある程度やむを得ない話なのかなとも思います。

　ミステリの犯人についての話でも、「ミステリのネタバレありきで楽しむ場所」と各所でしつこ
いほど断りを入れた上でなら、まあ許されるだろうなと。

　でも、ここは数学全般を扱う場所です。ただ「階乗の数の並びに法則性ってあるのかな？」
と気になっただけの人も来る場所です。そこに解答を書くのは、本屋さんで「何か面白い本な
いかな」と思ってるだけの人にいきなりネタバレするようなものではないですか？

　というか、実際に私は160は未挑戦というか問題読んでもいませんでした。たまたま160の
ネタバレだと言われる前に自力で解いたので、私はぎりぎりセーフでしたが、私以外の人
（例えば、記事を読みに来るだけの人とか）にはネタバレ被害を受けた方もいるかもしれま
せん。

　さらに重ねて、159に関しては、私は突然ネタバレのURLだけ押しつけられました。もし私が
本文を先まで読まずにOEISのURLを開いていたら100%自力正解の権利をGAIさんによって勝
手に剥奪されるところでした。まだ問題すら読んでいない段階でですよ。これは許せません、
はっきりと怒りを覚えます。

　アクセスしたければ可能であることと、アクセスしようと思っていない人の目にまで入れさせ
ることは全く違うというのを理解してください。よろしくお願いします。……自戒も込めて。

（訂正）　押し付けられたのはURLじゃなくてOEISの番号だけでしたね、失礼しました。文意
　　　は通じると思いますので……。



　　以下、工事中！