求最小正整数 k，使得 5^k 起始9位数为12！=479001600
A386547NAME
a(n) is the least integer k such that 5^k begins with n!.
DATA
0, 0, 2, 4, 12, 116, 2080, 6017, 149704, 2436360, 10819405, 19295517
OFFSET
0,3
FORMULA
a(n) = A018862(n!).
EXAMPLE
a(4) = 12 because 5^12 = 244140625 is the smallest power of 5 beginning with 4! = 24.
MATHEMATICA
a := Module[{target = IntegerDigits, k = 0}, While, Length@target], target], k++]; k];
Table, {n, 0, 8}]
CROSSREFS
Cf. A000142, A018862, A374922, A374923. 原来是计算精度的问题，a(12) = 1664457026 这个需要借用以前分析\(2^k\)和\(5^k\)中前n位相同相同的方案
https://zhuanlan.zhihu.com/p/634499178
我们的目标时寻找k使得\(5^k\)的前h位和n!相同，其中h是n!的位数，于是我们要求寻找k使得存在整数m使得
\(\lg(n!)-h+1\le \{k\lg(5)\}\lt\lg(n!+1)-h+1\)
我们记\(a=\lg(n!)-h+1,b=\lg(n!+1)-h+1\),其中a,b是两个非常接近的(0,1)上的数， 并且记\(c=\frac{a+b}2, e=\frac{b-a}2\), c为区间中心，e很小，是区间长度一半。
假设我们现在已经找到某个\(k_1\)使得\(k_1\lg(5)\)再区间\((a,b)\)附近比较接近的地方，但是还没有落在区间中间，也就是\(h=|{k_1\lg(5)}-c|\)不大，但是大于e,
于是我们后面搜索的目标就是需要找到下一个更好的k_2,使得\(|{k_2\lg(5)}-c|<h\), 所以必然要求\(-2h<{(k_2-k_1)\log(5)}<2h\)
也就是要求找到整数m, k使得\(-2h<m-k \lg(5) < 2h\).
利用链接中知识，我们知道需要寻找和\(\lg(5)\)的连分数前s位相同，然后第s+1位不同的分数\(\frac{m}k\)使得\(|2h(q_s+q_{s-1}x^*)|\lt x^*\) mathe 发表于 2025-8-21 08:44
这个需要借用以前分析\(2^k\)和\(5^k\)中前n位相同相同的方案
https://zhuanlan.zhihu.com/p/634499178
我 ...
老师们看答案的！
没看到答案！
你要先看到答案，再看过程 我试了连分数逼近，发现计算出来a(5)=1767，a(6)=106352,但穷举可发现a(5)=116,a(6)=2080.
116,2080似乎也不在连分数的分母序列中 计算7^k 以n!起始也是如此：
我试了连分数逼近，发现计算出来a(5)=871,但穷举可发现a(5)=361.
361似乎也不在lg7 连分数的分母序列中：{1, 1, 6, 13, 71, 439, 510, 2455069, 2455579, 4910648, 12276875, 29464398, 71205671, 100670069, 171875740, 272545809, 1807150594, 9308298779, 11115449373, 931890596738...} 连分数方法计算a(30)=47234075712191144824088070110423078120407355467583563587299954934.显然比实际数值大了许多 直接连分数逼近不能取到最优值是正常的。我前面的想法是对于比较接近的一个分数，差值再使用3#的方案枚举。但是有一个问题是两个分母都比较小的分数，它们的和的分母不一定很小，可能会增大很多。
以a(8)=149704为例，代表使用分数104639/149704，对应连分数
和lg(5)的连分数 的前面部分是相同的。
所以关键就在于我们需要判断有多大部分是相同的，这样就可以减少搜索空间了。
一个可以利用的信息，应该随着n增加，连分数相同的长度应该会越来越多。
那么按这个标准，由于104639/149704 重叠连分数为, 对应连分数展开6项为
于是我们后面可以仅搜索分数\(\frac{65u+137v}{93u+196v}, 0\lt u\lt v\)，比如下一项对应u=4492,v=10299.
页:
[1]