求最小正整数 k，使得 5^k 起始9位数为12！=479001600

mathe · 发表于 2025-9-15 17:58:46

前面代码里有点bug,修复了一下，另外将X/q用它的平方根来替换，这样相当于假设下一轮连分数计算的复杂度是低于穷举法的，同样里面放了一个调节因子RR
在n不超过17时，使用RR=0.01速度还是比较快的，经验是使用越大的n,需要的RR越小，这表明实际复杂度应该大于sqrt(X/q), 倒是比X/q小。

#include <gmpxx.h>
#include <iostream>
#ifndef N
#define N 10
#endif
#define PREC 300
#if N==10
mpf_class lgNfac("0.5597630328767937511747612399600555908932271418594001136856622817018191866832707151595484631470708116273899442969485014350620900263856693662453264103027331671177926665919099403914095284940514926910190038154483975520500476678019753243237638601809284996882257656525282203638995000349747345868231323035409926787747523076550826236151137832855580203281034749161818795132939859815213483271758017382846906260428003724227082312295982498627429482231923562145809314578884266948456955425575151223348285543101296610017182622467743146323189318357758827168396998081811369036806837543875120253218217950902097453860936609562706516413101610406306032824675179298025117697243828023871529437211881090000134242485533909791004821407786459813112778974700758110724783487012193394826852717625256134653300428714888746662799516304918143451336441941097801424292472369570765450275724395583098555691235046595365459031065068100081118324693217085246233632885174190388990055960853540334624097213749793093543555133809798468884685371002",PREC,10);
mpf_class lgNa1fac("0.5597631525566940111241786939544799467484747745028933440989937595315976904390877869792913678149940658639563780233135458496085838538867596497996492452805059675370107543531774119982840893409927092665680560488344871416125071286159968924372725815610297539717991318596071753747897880133927606701531700223278208492917279643346559011621406447304101952660661034232112959696393925223494547623725925612695410807375205592293008292619168888826853181722537658449214837495411314701009829451354075244431048323597459612753405388901524365372634129476015584173732335666816138143502093177725484063131657110986664492470835170934602414831746072663353972364086434857470203486954791550406639889613725556775900748837146559905640327739532770141278823149469329865834263494577972489809710643439244913986354857263803099261158738371578551210062211447791872798922459473384067091969993242986110657858150491948394933385676154884871479026599459821640883508715006047530987996752936228350555461675745864089624124185159496815690306991175",PREC,10);
#elif N==11
mpf_class lgNfac("0.6011557180350187919249612112030798325999293323258532082822013003815722189165200627308432495328019906308647572891646830292346685461006768020139157535245259462375327971604393772289963575065535432058725893980165601104069556492804409649896091901048435268183468516139102955794532845373104557119770980883941136350522388102716123605334334721762009454980187580147625189581659453737407766135561994238024117948052508909395040720986700699315605512216152988290765447700321069271183775129315138343581146521187869763012701992114603629057098215496963652371643167939769558826294545711990686297356125280073813118322374502262192478038358106054408992069992524498290961758463823386793038645203065070281652829853264745796653636762147112027067721889709257247793249150031156803422021657763024705770074706212228207303978134185592810519711003502902887860714752436345679124113611700267478347458848102172260955864466364938900866680671575769051738544618993319757509965601023809298421679203894949619411650720597411737319377178737",PREC,10);
mpf_class lgNa1fac("0.6011557289150110874811105665359089961351038515110119290833738457560862941418995834309068620055602929887426537237758034453323420148189637580570031477337836227346736961530354098923189190060786776492012362675660636536945314560720992161843647745963546887933405141944445688919585518488047865731600066042934275808724434625860811765383811618580575006175860471455385013224198556226610842704968915924678216820189585670336575341409564344101554593553718544506737398309441171767597644610848493364940539215076587624149856776564022367256352590147850856678877266892641607737067343647250403213469082768394819162353238322682767882768484131385259529601549006461994799922473170917046062330591416251922230150182695950291598959772833504102404332488207039863642345210268128082566220942356697122472791387788258585104758155683388806470084827751740176974282744567818328201485331836623850107980872645435377681964838956335412982189903091611948770251479347352801790957312671246923454819763780407847338604077991237194465003548780",PREC,10);
#endif
#include "powpref.h"
mpf_class lg5("0.6989700043360188047862611052755069732318101185378914586895725388728918107255754905130727478818138279593155228085690046209052321188664764940003076662953044249354970357458065973381802656883970564988160971018214173828455604681380709536461153004797606891503875374595997366874053785211541526817173273160176738034572064923686824516490728610350530822142310819492099924004519121845402854149680351223738775077091708818090485010028283801395223234999321794820874426713713316579995970794901629154277751045057024378502927553402913863103907780905172387856085034717648321735076851959722537567558366884612617406961169606193667838697609481194178680843145383070946984948680730146215115812816799342464305316070282578679890941031091494143753590127816031233514601437648387226973610721217391501633189696915685844391860563823254511433365754618762660675775304056509397879554957031725393115214538843152315893562020499534030082254342459135981535920543470455658922591706000254599262782983198051109445143089305996245883100365842",PREC,10);
mpf_class one("1.0",PREC,10);
#define RR 0.005
#define LOW lgNfac
#define UPP lgNa1fac
#define M lg5
#define ONE one
mpz_class bestGK=-1;
#define CHECK_COUNT 50000
mpz_class orgUB=1;
#define NO_ENUM 0
#define ALL_ENUM 2
#define INSIDE_ENUM 1
#define OUTSIDE_ENUM (-1)
bool getKrange(int sgn, const mpf_class& L, const mpf_class& U, const mpf_class& xp, const mpz_class& q1, int& uk_infty, mpz_class& LK, mpz_class& UK, mpz_class& LC, mpz_class &UC, mpf_class& LX, mpf_class& UX, mpf_class& LX2, mpf_class& UX2, int& retz, int& enum_result, int &search_count)
{
retz=0;
mpz_class X=orgUB;
if(bestGK>0&&bestGK<X)X=bestGK;//estimate no more than X
bool has_root = true;
mpf_class rL=L;
if(sgn<0){
rL=-U;
}
mpf_class dd=rL/RR*sqrt((mpf_class)X/q1);
if(dd<0)dd=-dd;
dd=(4.0*xp*dd);
mpz_class r1,r2;
dd+=rL*rL;
if(dd<0){
has_root=false;
}else{
dd=sqrt(dd);
r1=(mpz_class)floor((-rL-dd)/(2.0*xp));
r2=(mpz_class)ceil((-rL+dd)/(2.0*xp));
if(r1>r2){
mpz_class t=r1;r1=r2;r2=t;
}
}
if(sgn>0){
if(xp>=ONE){
return false;
}else if(0<xp&&xp<ONE){
uk_infty=1;
LK=(mpz_class)ceil(L/(ONE-xp));
if(bestGK>0){
mpz_class UB=bestGK/q1;
UK=UB;
uk_infty=0;
if(UK<LK)return false;
}
if(has_root){
mpz_class fL,fU;
if(LK<=r1){LC=r1;}else LC=LK;
if(uk_infty||UK>=r2){UC=r2;}else UC=UK;
enum_result = INSIDE_ENUM;//enumerate from LC to UC
}else{
enum_result = NO_ENUM;
}
if(has_root&&LK<LC){//need check left range
LX=xp+L/LC;
UX=xp+U/LK;
if(LX<0)LX=0;
if(UX>ONE)UX=ONE;
search_count=2;
if(uk_infty||UK>UC){
if(uk_infty)LX2=xp;
else LX2=xp+L/UK;
UX2=xp+U/UC;
if(LX2<0)LX2=0;
if(UX2>ONE)UX2=ONE;
}else{
LX2=ONE;UX2=0;//no search for second region required
}
}else if(has_root&&(uk_infty||UK>UC)){
search_count=2;
if(uk_infty)LX2=xp;
else LX2=xp+L/UK;
UX2=xp+U/UC;
if(LX2<0)LX2=0;
if(UX2>ONE)UX2=ONE;
LX=ONE;UX=0;//no search for first region required
}else if(has_root) {
search_count=0;
}else{//no enum
search_count=1;
if(uk_infty)LX=xp;
else LX=xp+L/UK;
UX=xp+U/LK;
}
}else{
uk_infty=0;
enum_result = OUTSIDE_ENUM;
LK=(mpz_class)ceil(L/(ONE-xp));
UK=(mpz_class)floor(-U/xp);
if(bestGK>0){
mpz_class UB=bestGK/q1;
if(UK>UB)UK=UB;
}
if(UK<LK)return false;
if(r1>=LK){
LC=r1;
if(r1>UK)LC=UK;//all in left check
}else{
LC=LK-1;
}
if(r2<=UK){
UC=r2;
if(r2<LK)UC=LK;//all in right check
}else{
UC=UK+1;
}
if(r1<UK&&r2>LK){
search_count=1;
if(r1<LK)r1=LK;
if(r2>UK)r2=UK;
LX=xp+L/r2;
UX=xp+U/r1;
if(LX<0)LX=0;
if(UX>ONE)UX=ONE;
}else{
search_count=0;
}
}
}else{
if(xp<=0){
return false;
}else if(xp<=ONE){
uk_infty=1;
enum_result = INSIDE_ENUM;
search_count=2;
LK=(mpz_class)ceil(L/xp);
if(bestGK>0){
mpz_class UB=bestGK/q1;
if(UK>UB)UK=UB;
uk_infty=0;
if(UK<LK)return false;
}
}else{
uk_infty=0;
search_count=2;
enum_result = INSIDE_ENUM;
LK=(mpz_class)ceil(L/xp);
UK=(mpz_class)floor(U/(xp-ONE));
if(bestGK>0){
mpz_class UB=bestGK/q1;
if(UK>UB)UK=UB;
}
if(UK<LK)return false;
}
if(r1>=LK){//need search for data before r1
LX=xp-U/LK;
if(!uk_infty&&r1>=UK){
UX=xp-L/UK;
}else{
UX=xp-L/r1;
}
}else{
LX=ONE;
UX=0;
}
if(uk_infty||r2<=UK){
if(r2<=LK){
LX2=xp-U/LK;
}else{
LX2=xp-U/r2;
}
if(uk_infty){
UX2=xp;
}else{
UX2=xp-L/UK;
}
}
if(r1>LK){
LC=r1;
}else{
LC=LK;
}
if(r2<UK){
UC=r2;
}else{
UC=UK;
}
}
return true;
}
bool check_range(int sgn, const mpz_class& f, const mpz_class& t, const mpf_class& L, const mpf_class& U, const mpf_class& xp, mpz_class& RU, mpz_class& RD)
{
mpz_class i;
mpf_class LL, LU;
if(sgn>0){
LL=L;LU=U;
}else{
LL=-U;LU=-L;
}
for(i=f;i<=t;i++){
mpf_class a=LL+i*xp;
mpf_class b=LU+i*xp;
mpz_class ai=(mpz_class)floor(a);
mpz_class bi=(mpz_class)floor(b);
if(bi>ai){
RU=ai+1;RD=i;
#ifdef DUMP
std::cout<<"Found RU="<<RU<<", RD="<<RD<<std::endl;
#endif
return true;
}
}
return false;
}
#ifdef DUMP
int level;
#define UPLEVEL (level++)
#define DOWNLEVEL (level--)
#else
#define UPLEVEL
#define DOWNLEVEL
#endif
bool search_to_next_level(const mpz_class& p0, const mpz_class& q0,const mpz_class& p1, const mpz_class& q1, const mpf_class& LX, const mpf_class& UX);
bool search(const mpz_class& p0, const mpz_class& q0, const mpz_class& p1, const mpz_class& q1)
{
mpf_class xp=(q1*M-p1)/(p0-q0*M);
mpf_class mul = q0*xp+q1;
int sgn = mul<0?-1:1;
if(mul<0)mul=-mul;
mpf_class L = LOW*mul;
mpf_class R = UPP*mul;
sgn*=(p1*q0>q1*p0)?1:-1;
mpz_class LK,UK,LC,UC;
mpf_class LX,UX,LX2,UX2;
int uk_infty,retz;
int enum_result, search_count;
UPLEVEL;
if(!getKrange(sgn, L, R, xp, q1, uk_infty, LK, UK, LC,UC, LX, UX, LX2,UX2, retz,enum_result,search_count)){
DOWNLEVEL;
return false;
}
if(retz){//solution p1/q1 found
if(bestGK<0||q1<bestGK){
std::cout<<q1<<std::endl;
bestGK=q1;
DOWNLEVEL;
return true;
}
}
#ifdef DUMP
int j;
for(j=0;j<level;j++)std::cout<<" ";
if(enum_result==INSIDE_ENUM||enum_result==NO_ENUM){
std::cout<<"Inside:"<<search_count;
}else{
std::cout<<"Outside:"<<search_count;
}
std::cout<<L<<","<<R<<","<<xp<<","<<q1;
std::cout<<"{"<<LK<<","<<LC<<","<<UC<<",";
if(uk_infty){
std::cout<<"oo";
}else{
std::cout<<UK;
}
std::cout<<"}{"<<LX<<","<<UX;
if(search_count>=2){
std::cout<<","<<LX2<<","<<UX2;
}
std::cout<<"}\n";
#endif
if(enum_result == INSIDE_ENUM||enum_result == NO_ENUM){
if(search_count>=1&&enum_result==INSIDE_ENUM){
if(search_to_next_level(p0,q0, p1,q1,LX,UX)){
DOWNLEVEL;
return true;
}
}
mpz_class i;
mpz_class RU,RT;
if(UC>=LC && check_range(sgn, LC,UC, L, R, xp, RU, RT)){
mpz_class nv=q0*RU+q1*RT;
if(bestGK<0||nv<bestGK){
bestGK=nv;
std::cout<<nv<<"\n";
}
DOWNLEVEL;
return true;
}
if(search_count>=2&&enum_result==INSIDE_ENUM){
if(search_to_next_level(p0,q0, p1,q1,LX2,UX2)){
DOWNLEVEL;
return true;
}
}
}else if(enum_result == OUTSIDE_ENUM){
mpz_class RU,RT;
if(LK<=LC && check_range(sgn, LK,LC, L, R, xp, RU, RT)){
mpz_class nv=q0*RU+q1*RT;
if(bestGK<0||nv<bestGK){
bestGK=nv;
std::cout<<nv<<"\n";
}
return true;
}
if(search_to_next_level(p0,q0,p1,q1,LX,UX)){
return true;
}
if(UC<=UK&&check_range(sgn, UC,UK, L, R, xp, RU, RT)){
mpz_class nv =q0*RU+q1*RT;
if(bestGK<0||nv<bestGK){
bestGK=nv;
std::cout<<nv<<"\n";
}
return true;
}
}
DOWNLEVEL;
return false;
}
bool search_to_next_level(const mpz_class& p0, const mpz_class& q0,const mpz_class& p1, const mpz_class& q1, const mpf_class& LX, const mpf_class& UX)
{
int sr=0;
if(LX<UX){
mpz_class lowN = (mpz_class)floor(ONE/UX);
mpz_class uppN = (mpz_class)floor(ONE/LX);
mpz_class i;
for(i=lowN;i<=uppN;i++){
mpz_class p2=p0+p1*i,q2=q0+q1*i;
#ifdef DUMP
int j;
for(j=0;j<level;j++)std::cout<<" ";
std::cout<<"a["<<level<<"]="<<i<<"("<<p1<<"/"<<q1<<","<<p2<<"/"<<q2<<")"<<std::endl;
#endif
if(search(p1,q1,p2,q2))sr=1;
}
if(sr){
return true;
}
}
return false;
}
int main()
{
int sgn=1;
int ii;
for(ii=0;ii<N;ii++)orgUB*=10;//set an original upper bound for search
mpf_set_default_prec(1000);
mpf_class xp=M;
mpf_class L=LOW, R=UPP;
int uk_infty, retz;
mpz_class LK, UK;
mpf_class LX, UX, LX2,UX2;
mpz_class p0=0,q0=1;
mpz_class LC, UC;
int enum_result, search_count;
if(!getKrange(sgn, L, R, xp,q0, uk_infty, LK,UK,LC,UC, LX, UX,LX2,UX2, retz, enum_result, search_count)){
std::cerr<<"Fail to search\n";
return -1;
}
if(retz){//finished search;
std::cout<<"Best result is 0\n";
return 0;
}
if(enum_result == INSIDE_ENUM||enum_result == NO_ENUM){
if(search_to_next_level(1,0, p0,q0,LX,UX)){
std::cout<<"Best result is "<<bestGK<<std::endl;
return 0;
}
mpz_class i;
mpz_class RU,RT;
if(UC>=LC && check_range(sgn, LC,UC, L, R, xp, RU, RT)){
if(bestGK<0||RT<bestGK){
bestGK=RT;
std::cout<<RT<<"\n";
}
std::cout<<"Best result is "<<bestGK<<std::endl;
return 0;
}
if(search_count>=2&&enum_result==INSIDE_ENUM){
if(search_to_next_level(1,0, p0,q0,LX2,UX2)){
std::cout<<"Best result is "<<bestGK<<std::endl;
return 0;
}
}
}else if(enum_result == OUTSIDE_ENUM){
mpz_class RU,RT;
if(LK<=LC && check_range(sgn, LK,LC, L, R, xp, RU, RT)){
if(bestGK<0||RT<bestGK){
bestGK=RT;
std::cout<<RT<<"\n";
}
std::cout<<"Best result is "<<bestGK<<std::endl;
return 0;
}
if(search_to_next_level(1,0,p0,q0,LX,UX)){
std::cout<<"Best result is "<<bestGK<<std::endl;
return 0;
}
if(UC<=UK&&check_range(sgn, UC,UK, L, R, xp, RU, RT)){
if(bestGK<0||RT<bestGK){
bestGK=RT;
std::cout<<RT<<"\n";
}
std::cout<<"Best result is "<<bestGK<<std::endl;
return 0;
}
}
std::cout<<"Final:\n";
std::cout<<bestGK<<std::endl;
return 0;
}

复制代码

mathe · 发表于 2025-9-16 08:06:46

N=18
6082009149849843

王守恩 · 发表于 2025-9-16 08:35:45

本帖最后由王守恩于 2025-9-16 08:40 编辑

mathe 发表于 2025-9-12 16:13
N=17
51727020012214
(使用CHECK_COUNT=50000,共5分钟左右）

整理整理。

11#——0, 0, 2, 4, 12, 116, 2080, 6017, 149704, 2436360, 10819405, 19295517, 1664457026, 55459990176, 223913486556, 700785493886——A386547

17#——现在代码比较粗糙，验证了N=10~15和wolves相同，另外得出N=16——700785493882——应该是700785493886。

18#——N=17=51727020012214——这个应该是——N18——就这点, 我们可能被卡住了。

Floor[10^FractionalPart[700785493886*N[Log10[5], 20]]*10^12]——1307674368000=15！

1307674368000=15！ 20922789888000=16！ 355687428096000=17！

Floor[10^FractionalPart[51727020012214*N[Log10[5], 20]]*10^14]——355687428096000=17！

Floor[10^FractionalPart[6082009149849843*N[Log10[5], 20]]*10^15]——6402373705728000——18！

mathe · 发表于 2025-9-16 09:10:53

https://bbs.emath.ac.cn/thread-19684-1-1.html
找到旧贴了，去年的方法更好

northwolves · 发表于 2025-9-16 16:46:34

本帖最后由 northwolves 于 2025-9-16 17:20 编辑

我提交了2,3,5,7的序列，已发布。

昨天提交11 和13，编辑评论：

Don't we already have enough of these? More doesn't seem better. People are more likely to search for A374923, A386547, A387304.

For me this is already covered by A180694 and the other sequences. The point of A374922 and A374923 was to show that it could be done efficiently with large n. But this does not need to be shown again repeatedly.

其实我这里17,19也顺带一起计算过了，{11,13,17,19}最高计算到 n=16 or 17

northwolves · 发表于 2025-9-16 16:48:45

本帖最后由 northwolves 于 2025-9-16 17:17 编辑

重新编辑了该序列：
A387013

a(n) is the least integer k such that n^k begins with n! or -1 if no solution exists.

DATA
0, 1, 8, 92, 116, 88277, 588458, 58481, 260426, -1, 78697156, 747607554, 10952402703, 254230157940, 4409739261144, 38129989457749

OFFSET
1,3

COMMENTS
a(10) = -1 because 10^k begins with 10 for k > 0.

EXAMPLE
a(4) = 92 because 4^92 = 24519928653854221733733552434404946937899825954937634816 is the smallest power of 4 beginning with 4! = 24.

MATHEMATICA
a[n_]:= Module[{target = n!, r = IntegerLength[n!], logn = N[Log10[n], 100], k = 0},

While[Floor[10^(FractionalPart[k*logn] + r - 1)] != target, k++]; k];

Table[a[n], {n, 1, 9}]

CROSSREFS
Cf. A000142, A374923, A374922, A386547, A387304.

northwolves · 发表于 2025-9-17 08:17:19

求解a(18)=18^k 以18!开始的最小整数k

已解决：
a(15)=4409739261144
a(16)=38129989457749
a(17)= 73425462387019
a(18)=?
a(19)=27036908878375100
a(20)=1053338431686717460

mathe · 发表于 2025-9-17 09:51:07

好像3#中的方法还是不错的，也就是在已经得到\(\{k_1 \lg(5)\}\)和目标数比较接近的时候(不超过h)，我们需要找另一个尽量小的整数\(k_2-k_1\)使得
\(|\{(k_2-k_1)\lg(5)\}|<2h\), 然后就可能使得\(\{k_2\lg(5)\}\)离目标数更加接近。
于是计算过程我们需要不停的寻找新的\(k_t\)使得\(|\{(k_t-k_{t-1})\lg(5)\}|\)再一次递减。
于是这个可以使用stern-brocot树来非常高效的求出\(k_t-k_{t-1}\)。
而链接2的幂同pi的相遇中liangbch的算法高度类似于用了这种方法。

mathe · 发表于 2025-9-18 13:26:03

使用上面算法刚刚弄出了一个pair/gp代码,
但是代码还有点小bug,也就是如果输入数据正好是底数的幂或者比幂小1，再高精度也算不出。
比如算5^k以24开头，由于24=5*5-1,计算会报错。

调用格式为
findappr(base, target, digits, MOD)
其中MOD需要使用一个很大的整数，然后后面计算都会采用模MOD计算，MOD太小会导致计算精度不够报错。比如可以选择MOD=10^100,
而代码中会有一小部分前置浮点计算，需要有足够精度，所以使用前需要设置足够高浮点精度，比如MOD使用10^100,那么计算精度要至少略高于100位，比如可以使用
\p 150
表示使用150度浮点计算精度。
这个函数会返回最小的整数k,使得base^k的前digits位和target前digits位相同。

testinrange(s,s2,U,V,M)=
{
if(U<V,
if(s>=U+1&&s<=s2&&s2<=V,1,
if(s2<=U&&(s<=s2||s>=V+1)||s>=V+1&&(s<=s2||s2<=U),0,-1)),
if(s>=U+1&&(s2<=V||s2>=s)||s2<=V&&(s<=s2||s>=U+1),1,
if(s<=U&&(s2>=U||s2<s) || s2>=V&&(s<=V||s>=U),0,-1))
)
}
dist(s,s2,C,M)=
{
local(d,s3,e);
s3=(s+s2)/2; if(s2<s,s3+=M/2);
e=(s2-s)/2;if(s2<s,e+=M/2);
d=abs(s3-C); if(d>=M/2,d=M-d);
d+e
}
sgndist(s,s2,C,M)=
{
local(d,s3,e);
s3=(s+s2)/2; if(s2<s,s3+=M/2);
e=(s2-s)/2;if(s2<s,e+=M/2);
d=s3-C; if(d>=M/2,d-=M);
if(d<=-M/2,d+=M);
if(d<0,d-e,d+e)
}
findk2(U,M,t,s)=
{
local(lu,ld,ru,rd,mu,md,tL,tD,r1,r2,pass);
lu=0;ld=1;ru=1;rd=1;
mu=lu+ru;md=ld+rd;
tL=if(s<0,M-t,0);
tD=if(s<0,M,t);
while(1,
r1=(md*U)%M;r2=(md*(U+1))%M;
pass=testinrange(r1,r2,tL,tD,M);
if(pass!=0,break());
if(mu*M<md*U,ld=md;lu=mu, if(mu*M>=(U+1)*md,rd=md;ru=mu,pass=-1;break()));
mu=lu+ru;md=rd+ld;
);
if(pass<0, md=0);
md
}
findmink(U,V,R,M)=
{
local(t,C,s,s2,pass,d,t2,dt,dt2);
C=(V+R)/2;
t=2;pass=0;
while(1,
s=(t*U)%M;
s2=(t*(U+1))%M;
pass=testinrange(s,s2,V,R,M);
if(pass!=0,break());
d=dist(s,s2,C,M);
if(d<M/8-1,break());
t=t+1
);
dt2=0;
while(pass==0,
s=(t*U)%M;s2=(t*(U+1))%M;
pass=testinrange(s,s2,V,R,M);
if(pass!=0,break());
d=sgndist(s,s2, C, M);
t2=if(d>0, findk2(U,M,2*d,-1), findk2(U,M,-2*d,1));
if(t2==0, print("Out of precision");pass=-1;break());
dt=if(d>0, M-(t2*U)%M, (t2*(U+1))%M);
dt2=if(d>0, floor((d-R+C)/dt),floor((-d+V-C)/dt));
if(dt2<=0,dt2=1);
t=t+dt2*t2;
);
if(pass==-1, print("Precision not enough, need larger M");0,
t)
}
findappr(u,v,n,M)=
{
local(lu, lv, rv, t, U, V,R);
lu=log(u)/log(10);
lu-=floor(lu);
lv=log(v)/log(10);
t=floor(lv);
v=floor(v*10^(n-1-t));
lv=log(v)/log(10)-(n-1);
rv = log(v+1)/log(10)-(n-1);
U=floor(lu*M);
V=floor(lv*M);
R=floor(rv*M);
findmink(U,V,R,M)
}

复制代码

比如使用
\p 1000
for(u=5,100, s=u!;r=findappr(18, s, length(digits(s)), 10^500);print(u,",",r))
得到
5,63
6,1680
7,3642
8,14387
9,1696738
10,3998016
11,10947946
12,825514266
13,1821688762
14,197680918419
15,38981198865221
16,15023912390981
17,258918396056895
18,18553374137359214
19,149897101165929134
20,5337998514529961988
21,7957523787372878900
22,48885793990344288895
23,44142110555196810262850
24,578605659839921996371529
25,112783699177135451463259207
26,520754961861071375905926338
27,327864967267938420194303002269
28,137464934434774447528980538258
29,32519371460891860088818610758697
30,360763921805840529622482428966766
31,20399045306454851654826214649915206
32,1395130806326082837353193042296705650
33,1064638931316749760463561942911005277
34,1181657051954195954103216667655460729949
35,2190509075652518134534062095972756779758
36,354905161799969822808667538624939986888082
37,6221940206327830814751851889041152222871268
38,533838105191500155427303371577710575524399974
39,19047773280283685209020700170999048776339446246
40,2206338681742557865698306229856813923814833133780
41,740459273205894939640204120318661175921839689068662
42,2617068225891253087772769203038826284017857620091974
43,45093668414994481240471655185424120348236541757053456
44,2228074893681735129913146374325417488510975394162385176
45,2483565816826088747586892429548905862844976212722004781487
46,9543446793427689131150448190840824011346487795502921412743
47,787612393061307296052807988771781403034104422792132872300041
48,5740567549470619851258056631738062761148307204320654912761887
49,34661582247726859084814384362756574521636589109545298480753594
50,52170379843798184322766971281459512181129341689265295073044042359
51,4022057962132918240344054205288062180490393260439457462217680028009
52,44653284601058096160984785999423552771560818435411682769197307997155
53,4828189017124606116539571494688283230887687456761079401045806529144021
54,307002273867246981574968668480440961117680960416092740936067165010197831
55,5414075147786470809279420576334489995464619956425226222060492681823827039
56,1442230095340767886589041773607378383564517369148963196857585087185910109473
57,17797521219970685899750161058380736023235356579527335706359792369317311260919
58,9758968532745756119153517117502849160860317723107621325115970095657211568476106
59,712958597667451819156065551902607864662439399091027474715518998088714619149761763
60,53910589585359494086614544509902881978604850627952502573908038041823774354388121278
61,443000650692405870948190021958944226140448417448771731286615886823922168344460403277
62,40032166125381085209094078302970040195332847588092497067795628486128022027580773840292
63,10530369284983441260729679487822890757545907873895261889246609734155294752356063392740246
64,249180871957654731718506091741365827336362356020266210130615408917069371945497725773013753
65,2042290384357301242673044785192649442664290240096571703146569007144820692516202745983442280
66,2327404037988383368865409837980472081872947936330541753109541588627147009684035106777623023766
67,68431695519980734068154069027582980371920117753223643528209729141198797714291437412835087830146
68,8214151422728267235745545424161455011130292332926308834995015364539861497641947052703917405765741
69,104248553808740001097835222540744404410923075914212457887416832860788613954661928129826580233667847
70,3585198975382389799054693641162767056212371186035342945050902915173455818422622424811275360783777298
71,1323152352166533317560312955388886229240778344827991287499119514257177992404751625369852500473404454395
72,88417931980305887898400316774467547613640058968253357225342854789284884116263458248301676068786528229413
73,13683012506857002212063306337117729545358176772429135768448366663823858089110873102842753069715427318736983
74,32137917832999726935326841685387144045071975797938686043874716308993136939254916126935386913179954530476223
75,4374659841635175330367741933866944510404383372238198821287467838939007070456473005899169519368181050050405301
76,5937662002552857686021927085332125322275663144632588109976232839073687531689054702432083906040236294096287453903
77,121172222860532316962162865143200877053113843413904030935208908544249884906641401642807911390820851213799918525072
78,97248778733239690723159158376615079517366686059000553893695592886013663955971468090684553890225038683323948839874998
79,4447269259571380209794996557692844198979354573319469845771393290590741415452907585780548760727903483026858700625323868
80,86665995599721937049816666151044977776315566481720036246611387998534277779062465520374008650134141963813665582167815067
81,58193062395149795845715912553195151247374474129885240511229425784189608011302826161510000814779493822767226779817936804653
82,656671109657534638806325175521880315227564629407223615210670215571475571815420583126313830713602093341059329487705437076219
83,36516856169848310286682743527492075523725783974453817378841108134843472098969341824268600916978744744122235542476362654287506
84,16927382189046029646896532074071547135274179991067829685826632106167638388263959227986201025616157390295952501376464613095479036
85,83764139052087301285798285544474938687593865968665947524867349070835071785891002127483285590845886089114530731285830828886178393
86,43576396000362044816138671117964851379733989262897646483436911694862704815097637167007961948514526460555223255173819427762592755455
87,3644835550555795678900612873812501434739557986916738342160324377985875798499507575125487894814976430545670221702563898015753891586667
88,90040612337868602431764199610995212153297867828968775808974277258670057798174376336607697505391816032421862353063751147217192953346215
89,12969180943355325774828350298494384593201167512243444167341160800780118461064934898112137406102370900524502179852016284255629786399380174
90,1584845169218190463155746987199256235048768451788098873719084968425327000085600317670867584360829758481252247214136321411675625064218185562
91,379742512898420158507821638817141315039483409261291152717973380264550730464221141677937860532350260486439371044620795379171325600392659442236
92,18164310105427713000149354461060225889020899426423458119794029912199162382266408572018701593505471246065596486531277634541018937603824971821015
93,3193393236342603624613023695254161839651553017437888175593112866096963625918653075278791509089150343455792608903261211335307391867499904017428965
94,92475329450142826051366437267821699714166409997074849944607827301578152944194472408133787793662642267061643416042525503081123185304486141185815593
95,40408540662145922816967444482183318237414821791273956884749966647107557500172082406257513942943817554149412334630610164270812162191938440940554385066
96,885692151722805825889899968877889263519281541533369364842904839127053587180604799143305523695409238624115475056399001232903764930443537644980667343169
97,115700783207673269482459568194675841659797139016133115365966016270119881404391438034065380949535235789104793143281984816893981935044463991124654754156929
98,90330590414660647065397551980237659174887334302608803887479927424258646831323795701785878192011878120573402871099721290620342184510448284672735686959037
99,11337826467067076076629219480315647406573250353843966131702069365700797672831705805416672607396602145085179910242885910812066433782653931259297912219077423427
100,205434530482046557360596524990087979830518401961820077315640155576171813279107446192065776079720231337742869534959018105639656814524453726449505716744816269258

比如还可以
\p 1000
findappr(Pi,1/9,100,10^500)
得到
\(\pi^{3570227448978643820097344439027815950348875034718098681378739266626694283136290986408344492598865460}\)的前100位都是1

mathe · 发表于 2025-9-18 15:49:21

northwolves 发表于 2025-9-17 08:17
求解a(18)=18^k 以18!开始的最小整数k

已解决：

(15:48) gp > for(u=11,100, s=u!;r=findappr(u,s,length(digits(s)),10^500);print("a[",u,"]=",r))
a[11]=78697156
a[12]=747607554
a[13]=10952402703
a[14]=254230157940
a[15]=4409739261144
a[16]=38129989457749
a[17]=73425462387019
a[18]=18553374137359214
a[19]=27036908878375100
a[20]=1053338431686717460
a[21]=54689167234912149096
a[22]=678416028962620804329
a[23]=67506358514042349427267
a[24]=269813938614269935089647
a[25]=15692675077152583530475263
a[26]=3010377254733353623222176420
a[27]=134535058864917802155619756354
a[28]=235416761121826259799659838990
a[29]=16535663182019102188442276887157
a[30]=810415231911788111377651219003976
a[31]=10544557460581936579558067276668148
a[32]=866038552421593785432953313220852271
a[33]=18756484661617397618163820501601543428
a[34]=89727081800693450682690722049041240223
a[35]=13842247250774412463650168103284702138299
a[36]=58305768765108830229979905124396088982863
a[37]=13010173991967318000851078625487819595258380
a[38]=7708445821110548680843530155722198386343595181
a[39]=15054848214571617105833381916518378481787995783
a[40]=1158929801156829098826415013935506368282793479672
a[41]=46680665028336473122794711203577760045422869880728
a[42]=428450420952612691302699206399514331551965361296822
a[43]=167778955761411250915719558883238697946095372430905779
a[44]=26946054160824390021244490306161595227824877023944948807
a[45]=615987838267852806377869945005332500740855085197352246567
a[46]=11887264688468266957669772308358545256142007979677071359298
a[47]=33422371743681587412749482033742910252608665006480874508300
a[48]=33237148285958821037561271177217332979896721700610298546987688
a[49]=1412494610889451120919806012623681553193221464068972443527934655
a[50]=60575121015838796788805399838400388749291141976724601187457623241730
a[51]=4575444234911719997462476731631268615105218394180331379473928406989
a[52]=155964911263133157637137979149875176994986402940459385932841101487055
a[53]=13344506740235091360273132806965606676593848451639730216043096924091894
a[54]=507501516891355932039470966612309086886891655066651802016351591301876226
a[55]=829505215818588757376410693133323995247702101094033822273157533292325145
a[56]=17058079828557489931555040813264540394465634797728599860182232068487403550
a[57]=80719457604921524009988961803860466682182949957616213614435033146834095236922
a[58]=1620423970743904233684281535989872457511803524178693023831740433693487478356525
a[59]=571435737563225994689976887827890962104248958145567883648543110262379446195001666
a[60]=2053382547892756640072376274936319934188094570899939324543916890822572959549117540
a[61]=454712188102005362913768948863773795257591198769931632677998362555208684029675585672
a[62]=52311347057056664081500947059953681862403002788241497987332718296757409007175247182507
a[63]=1842333867688406429630236556410195965167208537078613182121803154543461074731074353265539
a[64]=2559194894613433164782916167977615945363351116940737824630704344614827350463039921022893441
a[65]=26786490141009392529408913298139092882473213394731139076983364292652040008912982197298050119
a[66]=364348349710870445494266433872891195272125273801560636899335484763755288630324712562440966336
a[67]=34876150923167290627997215892354616927502206911658943882784261492119241482423222556858281372825
a[68]=8177167019615424474174846289797656470864911557214322760485196546038226348105046739833873969862902
a[69]=76142949228580773786708896761842720022186025571326223371542117834678595658447445261537318896863753
a[70]=6669579395601370594230946535193423451695408204756182298532486180991933024051223486062484970734426483
a[71]=97307084409935119513341720658090288924567279732955995476528343446395462135068001185584766855865905216
a[72]=85795397820804232180406244045489066528971342562442540897439579460058075357132942948577831558654407747308
a[73]=1534827448069194645744935085259273284872197398552496680917141239826408104753546988761698172199427929855298
a[74]=290333764030664789648174521028175317130044732428316246888223988651678872352752967485024998621128196194608565
a[75]=14383265390392692697946816044017697750951043185905201697457091491156801544221689543022499855252615881088055379
a[76]=1063387197926080464365645728829601882581575529944361257548354305088044899278465455383337187113934418173947812132
a[77]=102217301410252548619240381183027514289969740594944652397840491591115310717385769765172709989209145530105868993052
a[78]=51526815168980908338128634668314226707663061447461947695317362863944347495993272306906697433607554099225573241144696
a[79]=1942866055627381703214103712592949182437086381644337595323255960535192799241911505252639796312311031050673244384859361
a[80]=53158015636995510655041794074559467715106176074301814835723585023653067112350755406262093262634484015264563426820479217
a[81]=13475414036201321766031716319092329897589788870277065438609742267322971900833008212255640015299828408342528473855643648674
a[82]=421875949760975312110047264468489215189333769238237114799215957545999552366493915149594430002819896662812822137059767535962
a[83]=183363536770928144022659507691257317555749886649023869672523293338967476217144583306905740750251947946782068040066421467923633
a[84]=9265505762715712253430434392413228886582266385278953008378669404970973114411182858587789927328720234915587049519124550065831413
a[85]=851333306961305541792414417396775519342672270601136455519798923210672215154989265713520059630618895952640449598480199939883227916
a[86]=37480588935968249505170895134433537774659904367625418007768338670213811403762226148927459947730485330599275627407906656551558961099
a[87]=5160670222097556575214254335380493148109322795633001100569705305673537737880642985618585759371056809609711229006843936934282811628533
a[88]=146442144137385049139290463840239205212705430787295176101245565850888586910739392047440270121463902586431365376146110185391136226623934
a[89]=376934579612437929756581324491682300721819015679053783716669946862403451392934131581232483844956304418045229488758412488404032820745133647
a[90]=2446479012525697123797681212294816733692164788029168279365970301139379950894392387266651076530176485351387830646021216173714444387227739277
a[91]=180595203651652609810247529683785115473213217557814220077528408157285984939750934356168764040353126256793135735197903241847903454677665997022
a[92]=4290679588651805107778719168798870697711044201192152429750891594751377907292597504747518360198014591727538139460528449495155275178428975287877
a[93]=13024171896671142121223253253833811487744533011462613328328303702132005023029856877894065353951236087851929940968353701534232341326425735497220885
a[94]=127952473656186906277693681889057556598174764880506308501268014127273227742286325959848846512370420497037576871317249673564516813596617625423072215
a[95]=1902579376329245315922706197715694679605956653425771641530820118856305012857692211594425724002948193889920466306221546586558372716832824732180535114
a[96]=2200922959152973184454944936397401507109501687060049982436201258312054188100808902724557290532507971086760567503228927990278988876394955946074579138434
a[97]=10704602097729260650271270639126448486791314345490452459968131279983629146892138538199070636454349773244246333545080961028036224695100466113302867430560246
a[98]=12466380040558566358237689552737671550839855021965336156651441357082309272226573498875591083495225030053972347643657863860654699418524454493126534413007074
a[99]=1031852675860545794050710812760298993279537259860731178980175085316445235076594570190097397618337793918772289761639736648470062618683203745433535049236117073

账号		自动登录	找回密码
密码			欢迎注册

[求助] 求最小正整数 k，使得 5^k 起始9位数为12！=479001600

点评

评分

点评

点评

点评

评分

点评