阶乘和开平方

mathe

从整数3出发，经过若干次阶乘或开平方并取整操作，可以达到哪些整数呢？这些整数各自最少需要多少次操作来达到呢？
比如
3本身0次操作。
1只需要一次开平方
2需要阶乘在开平方两次操作。

lsr314

任意正整数都可以通过一个整数的阶乘和若干次开平方得到（从而可以建立数据库，从$3$经过若干次迭代得到目标值）。
假设$a^(2^k)<n!<(a+1)^(2^k)$,那么$[n!^(1/(2^k))]=a$
$lna<1/2^klnn!<ln(a+1)$
对于确定的$a$，只要增大$k$，就可以使中间的增量$1/2^klnn$足够小,从而介于$lna$和$ln(a+1)$之间，这个区间长度是$ln(1+1/a)≈1/a$.
大致估计$nlnn-n+1/2ln(2pin)≈2^kln(a+1/2)$,
$n≈(2^klna)/(kln2),lnn/2^k≈(kln2)/2^k<1/a,2^k>kaln2$.
当然这个估计很粗糙，只是用来大概估计$k$的大小，$n$的大小要用其他方式求解。
比如$a=100$,取$k=10$.从图像中得到$n≈825$，检验$825!^(1/2^10)=100.369$,满足条件。

.·.·.

先把几个简单的东西算出来好了
首先,0次阶乘，得到3
1次阶乘，得到6,(2)
2次阶乘，新得到720,26,5
3次阶乘,(720!~...6636426 2576 50 7 (2)) (26!~4481307 2116 46 (6)) 120 10 (3)
---
10以内： 1 2 3 5 6 7
4次阶乘：7:5040 70 8 (2)
10:3628800 1904 43 (6)
那些大数的阶乘实在不敢碰瓷，就这样好了……

mathe

不知道有没有算错
C[3]=0,from start
C[1]=1,from start
C[6]=1,from 3!
C[2]=2,from 3!
C[26]=3,from 6!
C[5]=4,from 6!
C[10]=6,from 5!
C[46]=8,from 20082117944246!
C[43]=9,from 10!
C[35]=13,from 10!
C[50]=13,from 2117!
C[7]=14,from 2117!
C[63]=14,from 46!
C[44]=15,from 43!
C[70]=16,from 7!
C[8]=17,from 7!
C[17]=19,from 101652092779175702171!
C[4]=20,from 101652092779175702171!
C[14]=20,from 8!
C[31]=20,from 954331!
C[24]=21,from 4!
C[23]=21,from 285810!
C[21]=21,from 1524875271235439076315!
C[65]=23,from 17!
C[36]=23,from 10461675836172505677753392!
C[74]=25,from 829459657340921965209631!
C[30]=26,from 24!
C[25]=26,from 23!
C[11]=26,from 301130983!
C[19]=27,from 63!
C[37]=27,from 10720!
C[29]=28,from 18859677!
C[79]=29,from 11!
C[84]=30,from 10720!
C[9]=31,from 10720!
C[15]=31,from 10461675836172505677753392!
C[45]=31,from 3959527!
C[16]=31,from 272359434134765!
C[47]=32,from 5247735!
C[85]=33,from 29!
C[22]=33,from 246798!
C[56]=33,from 21!
C[67]=33,from 613051585639!
C[58]=34,from 31!
C[32]=35,from 1143536!
C[13]=35,from 13205921705294205!
C[49]=36,from 291!
C[34]=36,from 31845!
C[94]=37,from 4574144!
C[18]=37,from 1408!
C[20]=38,from 22!
C[71]=38,from 47!
C[28]=38,from 63258!
C[73]=38,from 396456!
C[68]=39,from 54529900!
C[12]=39,from 6229207!
C[87]=39,from 7954595733146159116169!
C[42]=40,from 3938427356615!
C[91]=42,from 70471434!
C[69]=43,from 28!
C[33]=43,from 218!
C[39]=45,from 30367975900570699949054263!
C[83]=48,from 23756255408!
C[59]=49,from 713127013002609!
C[40]=50,from 1879!
C[66]=52,from 543934966!
C[80]=53,from 789601361368458493843521408503!
C[99]=53,from 55530!
C[41]=53,from 127841!
C[62]=54,from 117!
C[55]=54,from 128!
C[98]=54,from 239746665881036229693480449219!
C[86]=54,from 110605661!
C[88]=55,from 83!
C[92]=55,from 6532027380665612!
C[48]=55,from 1384703!
C[27]=55,from 3052!
C[61]=56,from 4010005!
C[89]=56,from 201!
C[54]=57,from 3476996840!
C[97]=57,from 7147792818!
C[96]=57,from 153!
C[95]=58,from 410554433466463042!
C[76]=58,from 3476996840!
C[51]=58,from 301130983!
C[78]=60,from 17182339742875652406!
C[57]=60,from 395!
C[81]=61,from 48!
C[100]=61,from 22914738!
C[38]=61,from 230!
C[52]=62,from 243!
C[64]=63,from 49008!
C[72]=63,from 6318!
C[60]=64,from 405081!
C[53]=65,from 372!
C[77]=67,from 27564!
C[75]=68,from 16343219991!
C[93]=70,from 163535604025!
C[82]=75,from 114659752566747097777!
C[90]=86,from 3649!

lsr314

mathe 发表于 2021-1-5 09:13
不知道有没有算错
C[3]=0,from start
C[1]=1,from start

建议用0表示阶乘，正整数表示开平方的次数，默认每一步都取整。比如26=(0,0,1),这样计算括号里的数字之和加上0的个数就是操作的步数。

mathe

C[3]=0 by [3]
C[1]=1 by [3, -1]
C[6]=1 by [3, 0]
C[2]=2 by [3, 0, -1]
C[26]=3 by [6, 0, -1]
C[5]=4 by [6, 0, -2]
C[10]=6 by [5, 0, -1]
C[46]=8 by [26, 0, -4]
C[43]=9 by [10, 0, -2]
C[35]=13 by [5, 0, 0, -7]
C[50]=13 by [6, 0, 0, -10]
C[7]=14 by [6, 0, 0, -11]
C[63]=14 by [46, 0, -5]
C[44]=15 by [43, 0, -5]
C[70]=16 by [7, 0, -1]
C[8]=17 by [7, 0, -2]
C[17]=19 by [35, 0, -5]
C[4]=20 by [35, 0, -6]
C[14]=20 by [8, 0, -2]
C[31]=20 by [26, 0, -3, 0, -12]
C[24]=21 by [4, 0]
C[23]=21 by [63, 0, -6]
C[21]=21 by [10, 0, -1, 0, -12]
C[65]=23 by [17, 0, -3]
C[36]=23 by [70, 0, -6]
C[74]=25 by [6, 0, 0, -9, 0, -12]
C[30]=26 by [24, 0, -4]
C[25]=26 by [23, 0, -4]
C[11]=26 by [31, 0, -5]
C[19]=27 by [50, 0, -5, 0, -7]
C[37]=27 by [46, 0, -4, 0, -13]
C[29]=28 by [8, 0, -1, 0, -8]
C[79]=29 by [11, 0, -2]
C[84]=30 by [10, 0, -1, 0, -11, 0, -9]
C[9]=31 by [10, 0, -1, 0, -11, 0, -10]
C[15]=31 by [63, 0, -5, 0, -10]
C[45]=31 by [26, 0, -2, 0, -24]
C[16]=31 by [26, 0, -3, 0, -11, 0, -11]
C[47]=32 by [74, 0, -6]
C[85]=33 by [29, 0, -4]
C[22]=33 by [37, 0, -5]
C[56]=33 by [31, 0, -4, 0, -7]
C[67]=33 by [44, 0, -4, 0, -12]
C[58]=34 by [70, 0, -5, 0, -11]
C[32]=35 by [15, 0, -3]
C[13]=35 by [5, 0, 0, -5, 0, -23]
C[49]=36 by [17, 0, -2, 0, -13]
C[34]=36 by [5, 0, 0, -6, 0, -10, 0, -12]
C[94]=37 by [84, 0, -6]
C[18]=37 by [6, 0, 0, -8, 0, -25]
C[20]=38 by [22, 0, -4]
C[71]=38 by [47, 0, -5]
C[28]=38 by [43, 0, -3, 0, -24]
C[73]=38 by [46, 0, -4, 0, -12, 0, -11]
C[68]=39 by [19, 0, -3, 0, -7]
C[12]=39 by [8, 0, -1, 0, -7, 0, -11]
C[87]=39 by [63, 0, -5, 0, -9, 0, -8]
C[42]=40 by [65, 0, -5, 0, -10]
C[91]=42 by [49, 0, -5]
C[69]=43 by [28, 0, -4]
C[33]=43 by [21, 0, -3, 0, -8, 0, -8]
C[39]=45 by [71, 0, -6]
C[83]=48 by [17, 0, -1, 0, -26]
C[59]=49 by [79, 0, -5, 0, -13]
C[40]=50 by [36, 0, -4, 0, -8, 0, -12]
C[66]=52 by [10, 0, -1, 0, -10, 0, -18, 0, -13]
C[80]=53 by [21, 0, -2, 0, -17, 0, -10]
C[99]=53 by [44, 0, -3, 0, -24, 0, -8]
C[41]=53 by [63, 0, -5, 0, -9, 0, -7, 0, -14]
C[62]=54 by [31, 0, -4, 0, -6, 0, -12, 0, -8]
C[55]=54 by [50, 0, -4, 0, -14, 0, -7, 0, -12]
C[98]=54 by [6, 0, 0, -8, 0, -23, 0, -18]
C[86]=54 by [6, 0, 0, -9, 0, -11, 0, -12, 0, -16]
C[88]=55 by [83, 0, -6]
C[92]=55 by [74, 0, -4, 0, -24]
C[48]=55 by [63, 0, -5, 0, -8, 0, -17, 0, -7]
C[27]=55 by [50, 0, -5, 0, -5, 0, -18, 0, -10]
C[61]=56 by [49, 0, -4, 0, -14]
C[89]=56 by [43, 0, -4, 0, -11, 0, -8, 0, -20]
C[54]=57 by [35, 0, -3, 0, -17, 0, -12, 0, -8]
C[97]=57 by [43, 0, -4, 0, -11, 0, -9, 0, -9, 0, -10]
C[96]=57 by [5, 0, 0, -6, 0, -10, 0, -10, 0, -22]
C[95]=58 by [65, 0, -4, 0, -20, 0, -8]
C[76]=58 by [35, 0, -4, 0, -8, 0, -7, 0, -22]
C[51]=58 by [5, 0, 0, -6, 0, -10, 0, -11, 0, -10, 0, -11]
C[78]=60 by [22, 0, -3, 0, -8, 0, -13]
C[57]=60 by [14, 0, -2, 0, -8, 0, -17, 0, -9]
C[81]=61 by [48, 0, -5]
C[100]=61 by [45, 0, -3, 0, -25]
C[38]=61 by [17, 0, -2, 0, -12, 0, -11, 0, -13]
C[52]=62 by [50, 0, -5, 0, -4, 0, -37]
C[64]=63 by [9, 0, -1, 0, -9, 0, -9, 0, -9]
C[72]=63 by [7, 0, 0, -13, 0, -5, 0, -18, 0, -8]
C[60]=64 by [34, 0, -4, 0, -7, 0, -14]
C[53]=65 by [35, 0, -3, 0, -17, 0, -11, 0, -17]
C[77]=67 by [44, 0, -2, 0, -48]
C[75]=68 by [26, 0, -3, 0, -11, 0, -9, 0, -17, 0, -8, 0, -11]
C[93]=70 by [98, 0, -6, 0, -8]
C[82]=75 by [23, 0, -3, 0, -9, 0, -10, 0, -5, 0, -22]
C[90]=86 by [33, 0, -4, 0, -7, 0, -10, 0, -8, 0, -9]

mathe

弄错了一点，舍去弄成四舍五入了
C[3]=0 by [3]
C[1]=1 by [3, -1]
C[6]=1 by [3, 0]
C[2]=2 by [3, 0, -1]
C[26]=3 by [6, 0, -1]
C[5]=4 by [6, 0, -2]
C[10]=6 by [5, 0, -1]
C[46]=8 by [26, 0, -4]
C[43]=9 by [10, 0, -2]
C[35]=13 by [5, 0, 0, -7]
C[50]=13 by [6, 0, 0, -10]
C[7]=14 by [6, 0, 0, -11]
C[63]=14 by [46, 0, -5]
C[44]=15 by [43, 0, -5]
C[70]=16 by [7, 0, -1]
C[8]=17 by [7, 0, -2]
C[17]=19 by [35, 0, -5]
C[4]=20 by [35, 0, -6]
C[14]=20 by [8, 0, -2]
C[31]=20 by [26, 0, -3, 0, -12]
C[24]=21 by [4, 0]
C[23]=21 by [63, 0, -6]
C[21]=21 by [10, 0, -1, 0, -12]
C[65]=23 by [17, 0, -3]
C[36]=23 by [70, 0, -6]
C[74]=25 by [6, 0, 0, -9, 0, -12]
C[30]=26 by [24, 0, -4]
C[25]=26 by [23, 0, -4]
C[11]=26 by [31, 0, -5]
C[19]=27 by [50, 0, -5, 0, -7]
C[37]=27 by [46, 0, -4, 0, -13]
C[29]=28 by [8, 0, -1, 0, -8]
C[18]=28 by [35, 0, -4, 0, -9]
C[79]=29 by [11, 0, -2]
C[81]=30 by [10, 0, -1, 0, -11, 0, -9]
C[9]=31 by [10, 0, -1, 0, -11, 0, -10]
C[15]=31 by [63, 0, -5, 0, -10]
C[45]=31 by [26, 0, -2, 0, -24]
C[16]=31 by [26, 0, -3, 0, -11, 0, -11]
C[94]=32 by [18, 0, -3]
C[47]=32 by [74, 0, -6]
C[85]=33 by [29, 0, -4]
C[22]=33 by [37, 0, -5]
C[54]=33 by [31, 0, -4, 0, -7]
C[66]=33 by [44, 0, -4, 0, -12]
C[58]=34 by [70, 0, -5, 0, -11]
C[32]=35 by [15, 0, -3]
C[13]=35 by [5, 0, 0, -5, 0, -23]
C[67]=36 by [79, 0, -6]
C[49]=36 by [17, 0, -2, 0, -13]
C[56]=36 by [35, 0, -3, 0, -18]
C[33]=36 by [50, 0, -5, 0, -6, 0, -9]
C[34]=36 by [5, 0, 0, -6, 0, -10, 0, -12]
C[77]=37 by [81, 0, -6]
C[20]=38 by [22, 0, -4]
C[71]=38 by [47, 0, -5]
C[28]=38 by [43, 0, -3, 0, -24]
C[73]=38 by [46, 0, -4, 0, -12, 0, -11]
C[80]=39 by [63, 0, -5, 0, -9, 0, -8]
C[42]=40 by [65, 0, -5, 0, -10]
C[12]=41 by [32, 0, -5]
C[91]=42 by [49, 0, -5]
C[69]=43 by [28, 0, -4]
C[39]=45 by [71, 0, -6]
C[41]=45 by [24, 0, -3, 0, -10, 0, -8]
C[83]=46 by [18, 0, -2, 0, -14]
C[57]=46 by [44, 0, -4, 0, -11, 0, -13]
C[68]=47 by [22, 0, -3, 0, -9]
C[59]=49 by [79, 0, -5, 0, -13]
C[89]=50 by [34, 0, -4, 0, -8]
C[40]=50 by [36, 0, -4, 0, -8, 0, -12]
C[27]=51 by [20, 0, -3, 0, -8]
C[100]=52 by [12, 0, -2, 0, -7]
C[48]=52 by [10, 0, -1, 0, -10, 0, -18, 0, -13]
C[88]=53 by [83, 0, -6]
C[99]=53 by [44, 0, -3, 0, -24, 0, -8]
C[55]=54 by [50, 0, -4, 0, -14, 0, -7, 0, -12]
C[98]=54 by [6, 0, 0, -8, 0, -23, 0, -18]
C[86]=54 by [6, 0, 0, -9, 0, -11, 0, -12, 0, -16]
C[92]=55 by [74, 0, -4, 0, -24]
C[61]=56 by [49, 0, -4, 0, -14]
C[53]=57 by [35, 0, -3, 0, -17, 0, -12, 0, -8]
C[82]=58 by [45, 0, -4, 0, -12, 0, -8]
C[93]=58 by [65, 0, -4, 0, -20, 0, -8]
C[84]=59 by [23, 0, -2, 0, -19, 0, -14]
C[78]=61 by [57, 0, -5, 0, -8]
C[76]=61 by [39, 0, -4, 0, -10]
C[75]=61 by [20, 0, -3, 0, -7, 0, -10]
C[38]=62 by [5, 0, 0, -5, 0, -22, 0, -7, 0, -8, 0, -10]
C[60]=63 by [9, 0, -1, 0, -9, 0, -9, 0, -9]
C[64]=63 by [10, 0, -1, 0, -11, 0, -8, 0, -13, 0, -9, 0, -9]
C[97]=66 by [35, 0, -4, 0, -8, 0, -7, 0, -21, 0, -8]
C[72]=66 by [26, 0, -1, 0, -46, 0, -13]
C[62]=68 by [78, 0, -6]
C[51]=68 by [75, 0, -6]
C[52]=69 by [54, 0, -5, 0, -7, 0, -7, 0, -13]
C[87]=69 by [6, 0, 0, -9, 0, -11, 0, -11, 0, -32]
C[95]=74 by [71, 0, -5, 0, -11, 0, -6, 0, -10]
C[90]=74 by [8, 0, -1, 0, -7, 0, -9, 0, -13, 0, -22]
C[96]=75 by [19, 0, -3, 0, -6, 0, -11, 0, -24]

lsr314

一点想法：随意选取一个比较大的整数，每次开平方以后长度减半（或加一位后减半），最后总会落到个位数，反过来是两位数、四位数（或三位数）等等，假设一个充分大的数$n$，其阶乘一直开平方以后必然经过10到99之间的一个数$a$，由于$n$充分大，可以认为$a$在10到99之间的分布是随机的（甚至是均匀的），这样只要选取的n足够多，总会铺满所有10到99之间的两位数。同理，三位数、四位数也可以铺满。
所以我有一个想当然的猜想：任何正整数$a$都可以表示成[3,0,0,0,……,0,-k]的形式。

mathe

竟然有人已经算过了:
https://oeis.org/A139003

wayne

这么冷僻的操作都有人计算出来，