100位平方数和立方数

mathe

的确，看来在边界上的概率远远小于平均概率。
假设fans给出的平方根的下界为X，那么对于$(X+x)^2$,实际在$x<10^29$都会有平方数最高40位不变，于是要求找到一个这样的数是的$(X+x)^2$最末60位数都是4~9,这个概率应该是
${60!}/{10!^6*10^60}~=3.6e-18$,所以我们还是随机找一个满足条件的而不是去找最大和最小的更加现实一些。
而如果我们先任意取定高60位数，使得前面60位中0~9都平均6个，得到一个近似平方根Y,然后随机选择比较小的数字y,计算$(Y+y)^2$，使得后40位中0~9都正好出现4次，这个成功的概率在
${40!}/{4!^10*10^40}~=1.3e-6$,这个相对还是比较容易的。
而前面我给出的1/500000不知道是如何计算的，远远偏大了

你的概率估算不正确，把人家给误导了。

要找最小的平方数，那么要从这个数的

1000000000011111111122222222223333333333444444444455555555556666666666777777777788888888889999999999

平方根开始 ...
KeyTo9_Fans 发表于 2010-1-21 01:45

mathe

而wayne的方法在23#处理边界数据的时候非常有用。
由于最小的那些平方数用光了大部分的0～3,我们根据wayne的方法，列出所有平方数的最低若干位，那么如果这些最低位中出现过0~3的就可以淘汰，通过这个方法，可以批量淘汰大部分平方数。
我们先可以计算出平方数最低4位都不含0~3的那些，然后再对它们进行扩展，计算出平方数最低8位甚至于更多位都不含0~3的那些平方数列表，这个谁来计算以下，看看能够列到多少位

mathe

按照概率分析，可能只需要考虑最高50位不变的情况，由此，我们可以完全淘汰那些最底50位包含0~4的平方数。(还可以先分析高60位不变，都不含0~5的平方数的情况，如果无解，再考虑这边的情况）

mathe

我们如果仅仅分析那些平方最高60位都不变的数，总数目大于$10^19$个，但是小于$10^20$个。
对于这么多数，它们平方的最低14位数都是6,7,8,9的数总共可能性正好有$4^14$种，其中对于每个数，我们还需要检查中间30位是否都在6和9之间，并且6和9的数目之和是否都相等。我估计用这个方法找到最小解的可能性已经非常之大了。总共需要判断最多2.68*10^14个。而如果我们设计的更加好一些，可以只搜索那些平方末20位必然是6~9的数，总共$4^20$个约为1.1*10^12个数，这个工作量应该能够在数小时内完成。

mathe

发现问题了，前面50位都不变的平方数（10000000000111111111222222222233333333334444444444）总共只有一个为
$31622776601859475412395706160319096581770547004140^2$,不符合要求
而前面40位平方数都不变的范围在上面那个和
$31622776601859475412395706160319096581779331108751^2$之间，总共才
8784104612个平方数，如果采用上面方法再次过滤，计算量很小，当然找到解的可能性也很小。
看来候选结果可能在平方数前面30位不变的范围内。
候选平方数有105409255334846728914个，但是如果过滤平方数尾数不能为0,1,2估计计算量在$7^20~=8*10^16$有点大。

KeyTo9_Fans

最小的立方数比较好找。

挂了一个通宵就出来了。

大概运行了6小时。

$1000000000003703703727510779070842^3$

$=1000000000011111111182573489476429582522942294366248549984335795733539926798566367346762855747387688$

#####

从$1000000000003703703707393689986627^3$开始逐个检查。

一旦发现数字个数符合要求，这个数就是答案了。

因为只需检查3的倍数，所以每次把底数加3。

根据$a^3$的值计算$(a+3)^3$是很方便的，只需维护三阶差，用加法即可。

从$1000000000003703703707393689986627^3$跑到$1000000000003703703727510779070842^3$，共有$20117089084216$个立方数。

其中，$3$的倍数有$6705696361405$个。

使用上述算法每秒可检查$6000000$个左右。

对于$6705696361405$的计算量来说，需要$13$天。

采取一些加速措施后，速度快了$50$倍，所以大概$6$小时就跑出来了。

理论上检查$20117089084216$个立方数能得到答案的概率是39%。

说明我们的运气比较好。

如果检查到

$1000000000011111111199999999998888888888777777777766666666665555555555444444444433333333332222222222$

还没找到答案，我就要另写一个程序了。

因为这时候可以动用$1$了。

而我的程序是没有考虑在后$80$位动用$1$的。

如果真的把$1$用起来了，那么出答案就会变得更轻松，计算量比之前会少很多。

经检查，前面说的

$1000000000003703703727510779070842^3$

$=1000000000011111111182573489476429582522942294366248549984335795733539926798566367346762855747387688$

是一个合法的解。

如果程序代码没写错的话，这个应该就是最终答案了。

如果写错了，那么就可以以上面这个数为上界，在这个范围内重新检查一遍即可。

056254628

楼上是穷举法吗？n从小到大，观察n^3的结果是否满足题意？
若是，有没有利用n是3的倍数这个条件？可以缩短3倍的时间。