😊出会いの泉😊

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

f(20) = 200817664
f(30) = 5863630848
f(40) = 6115894272
f(50) = 1568960512
f(60) = 2776964096
f(70) = 8984531968
f(80) = 6728081408
f(90) = 4469978112
f(100) = 5210916864

f(200) = 389737472
f(300) = 8808170496
f(400) = 5032491008
f(500) = 5547812864
f(600) = 3891178496
f(700) = 2517264384
f(800) = 8969450496
f(900) = 2530962432
f(1000) = 27753472

f(2000) = 807339008
f(3000) = 4872042496
f(4000) = 5802602496
f(5000) = 937833472
f(6000) = 8127287296
f(7000) = 993752064
f(8000) = 4026732544
f(9000) = 9915703296
f(10000) = 8001579008

f(100000) = 4957162496
f(1000000) = 5058412544
f(10000000) = 2574194688
f(100000000) = 2840754176
f(1000000000) = 933638144

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

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

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

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)の組は取れるのでしょうか？

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の計算以外は誤差程度の時間になりました。

(22:28追記)
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秒になりました。

高速化により、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)!でも十分大きいですが。

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

f(10^10) = 6441946112
f(10^20) = 8474436608
f(10^30) = 6117305344
f(10^40) = 6605049856
f(10^50) = 5791409152
f(10^60) = 1279752192
f(10^70) = 8388129792
f(10^80) = 2060969984
f(10^90) = 6590068736

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
f(10^5000) = 5123908608
f(10^6000) = 2555037696
f(10^7000) = 5540568064
f(10^8000) = 9098052608
f(10^9000) = 4882372608

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の値は存在するのですか?

コード書いてる途中で気づいたんですが、
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桁ではズレてしまいます。
これに代わる方法（法則）は無いものか？

まさに私が言った
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
が手に入る。

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

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

こんな規則があったとは思ってもいませんでした。
でもOEISでは
A347105などでは
Project Euler, Digital root sums of factorisations, Problem 159.
の様にリンクと共に解決に直接結びつく結果がいろいろなコードでのプログラムとともに
数値が並び公開されています。
この様に解決するのに大いに参考になる情報はいろいろな所にアクセス可能の状態にあります。
またこのごろはAI（ChatGTPやGemminiやCopilotなどなど)にプログラムを好きなコードで作ってもらうように
頼めば難なく示していきます。
ただこれが余り頼りにはなりませんが・・・
でも考える方向性などは窺い知ることはできます。
DD++さんがためらわれているのはこの解決に参考になることは一切表には出してはいけないものだという
お考えをお持ちだからなのですか？