100位平方数和立方数

kofeffect

呵呵，无心人是想确认我在8#说的，然后就顺便用Haskell来show一下而已

无心人

是的

不叫show

就让haskell和PARI一样的待遇吧

kofeffect

楼上说的PARI是否这个？
PARI/GP is a widely used computer algebra system designed for fast computations in number theory (factorizations, algebraic number theory, elliptic curves...), but also contains a large number of other useful functions to compute with mathematical entities such as matrices, polynomials, power series, algebraic numbers etc., and a lot of transcendental functions. PARI is also available as a C library to allow for faster computations.
http://pari.math.u-bordeaux.fr/

无心人

是的

数学几大工具之一

northwolves

试了试pari，确实很爽

KeyTo9_Fans

这个问题其实不难，因为只要求求最大和最小的。
我估算了一下，每个在范围的平方数或立方数，大概$1/{500,000}$的概率符合条件，所以穷举不难
mathe 发表于 2009-1-13 15:33

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

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

1000000000011111111122222222223333333333444444444455555555556666666666777777777788888888889999999999

平方根开始枚举。

你要想想，这个数的平方根有50位，设为$x$，取上整。

我们要从$x$开始，依次检查

$x^2$、$(x+1)^2$、$(x+2)^2$、$(x+3)^2$、……

是否符合条件。

可是即使检查了10亿个完全平方数，

这些完全平方数的前40位仍旧雷打不动，动的只是后60位。

也就是说，前40位是

1000000000011111111122222222223333333333......

恒定不变。

于是前40位把0、1、2、3的配额全花光了，

导致后面60位全都不允许出现0、1、2、3。

且不论4~9的数字个数问题，就光凭上面那条限制，就已经使得符合条件的概率不大于

$0.6^60=4.888e-14$

了。

也就是说，我们至少要往后检查20万亿个完全平方数，才能期望有1个完全平方数符合条件。

求最大的也是一样囧况。

哪有你说的那么轻松

056254628

mathe就经常犯这种错误。我这个外来人就见到他很多次。

056254628

我觉得这道题可以这么做：
设所求的最小平方数数为n^2,那么  sqrt(10)*10^49<n<10^50
且 n为3的倍数。可以从最小的n开始穷举，每次检查n^2是不是符合要求，若符合由10个0-9构成就大功告成。
求最大的平方数，则从最大的n开始往下搜索。
-------------------------------------------
而求立方数，搜索的范围更小。

liangbch

必须找出更多的约束条件，否则穷举不可行，期望mathe找出更多的约束条件。

liangbch

如果单纯采取构造法，包含10个不同的数字，每个数字出现10次的排列数是 $(100!)/((10!)^10)=2.35xx10^92$,显然计算机无法穷举。

我们考察一下下面的方法的复杂度。

预备知识：
若x是一个n位数，则$x^2$是一个2n位数或者2n-1位数，2n-1位数看做首位为0的2n位数。在x很大的情况下，$x^2$和$(x+1)^2$的前n位数不相同概率接近100%，当x比较小的时候，这个概率稍低。2n位首位为0的平方数且前n位数相同者，最多只有5个，2n位首位不为0的平方数且前n位数相同者最多只有2个。

对于此题，可按照下列算法去搜索。
  1. 构造一个100位数p，使得在前50个数字中，每个数字最多出现10次，后50位数字为0，求p的平方根并向上取整得x.
  2. 若$x^2$满足条件，即包含0到9各10次，程序结束。若$x^2$前50个数字与p的前50个数字不同，转4
  3. x++,并 转2
  4. 构造另一个100位数字p,求其平方根并向上取整得x，并转2

  复杂度分析，50个数字的所有排列为$10^50$，若加上限制条件，前50位数中，每个数字最多出现10次，则实际排列数可大大降低，我不知道这个数是多少，请高手给出答案。假设这个排列数c比较小，则枚举所有符合条件的数是可行的,实际运算次数正比于c。