Brain Storm

无心人

以最后一次才是SET做测试
10亿内的结果，0次到7次的数字的个数
bs.txt (900 Bytes, 下载次数: 0)

2010-11-2 08:37 上传

点击文件名下载附件

无心人

1. 
   
2. #include <stdio.h>
   
3. #include <stdlib.h>
   
4. #include <gmp.h>
   
5. 
   
6. char buf[2048] = "\0";
   
7. int b[10] = {1, 2, 4, 8, 16, 32, 64, 128, 256, 512};
   
8. int count[8] = {0, 0, 0, 0, 0, 0, 0};
   
9. 
   
10. int check(mpz_t n)
    
11. {
    
12.   int i, s = 0;
    
13.   char * BF = buf;
    
14.   mpz_get_str(BF, 10, n);
    
15.   for (i = 0; BF[i] != '\0'; i ++)
    
16.   {
    
17.       s |= b[BF[i] - '0'];      
    
18.       if (s == 1023)
    
19.          return (1);
    
20.   }
    
21.   return (0);
    
22. }
    
23. 
    
24. void main(void)
    
25. {
    
26.   unsigned long i, j, c, pow10 = 10;
    
27.   mpz_t n;
    
28.   mpz_init(n);
    
29.   
    
30.   for (i = 2; i <= 1000000000; i ++)
    
31.   {
    
32.     if (i == pow10)
    
33.     {
    
34.       printf("%10d:", pow10);
    
35.       for (j = 0; j <= 7; j ++)
    
36.         printf("%10d ", count[j]);
    
37.       printf("\n");
    
38.       pow10 *= 10;
    
39.     }
    
40. 
    
41.     if (i % 10 != 0)
    
42.     {
    
43.       c = 0;
    
44.       mpz_set_ui(n, i);
    
45.       while (check(n) == 0)
    
46.       {
    
47.         mpz_pow_ui(n, n, 2);
    
48.         c++;
    
49.       }
    
50.       count[c] ++;
    
51.     }
    
52.   }
    
53.   mpz_clear(n);
    
54. }
    

复制代码

无心人

稍微修改下就能测试，所有幂是SET 的情况

无心人

如果是全部幂
则10亿内测试结果是
只有2需要6次平方
还有个别数字需要5次（仅12个），绝大部分最多4次
2次的最多，其次1次的，其次3次，其次4次

无心人

估计5次那些都是10^n + 1, 10^n - 1的

chyanog

1. 
   
2. f[n_] := NestWhile[# + 1 &, 2,
   
3.   Union@IntegerDigits@Nest[#^2 &, n, #] != Range[0, 9] &]
   
4. 
   
5. Module[{k = 5, data, arr, min, max},
   
6.   data = Complement[Range[10^k], 10^Range[0, k]];
   
7.   arr = f /@ data;
   
8.   {
   
9.     {min, max} = {Min[arr], Max[arr]},
   
10.     {Count[arr, min], Count[arr, max]},
    
11.     Extract[data, Position[arr, min]],
    
12.     Extract[data, Position[arr, max]],
    
13.     Tally[arr]
    
14.     } // Column
    
15.   ] // Timing
    

复制代码

mathe

这个题目的确有些歧义，可以理解为某一个平方数出现所有0-9的数字，也可以理解为0-9中任意数字只要出现在某一个平方数中就可以。不过从链接中题目给出的例子来看，原题是采用第二种方案。
显然，从计算角度来看，前面一个更加难处理。我们可以只讨论第二种方案。

mathe

首先，末尾数为0的数字可以全部不讨论。末尾数为5的数字可以分开独立考虑。
从经验数据来看，对于所有的数字，应该6次足够了。但是证明应该很难，那我们是否可以适当降低难度，比如证明对于所有的数字，10次足够了，或者证明20次足够了？

mathe

比如我们为了证明20次以内可以对所有数据成立，
我们将所有数据可以分成3类:
i)5结尾的数
ii)末尾数非0的偶数
iii)末尾数非5的奇数。
现在以第3类为例子讨论，
如果我们能够证明对于某个h,($1<=h<20$),对于所有X,$X^{2^h}$到$ X^{2^20}$的最后k位可以覆盖0~9就可以了。
首先，我们知道对于第三类数,$X^{2^h}-=1(mod 2^{h+2})$,所以穷举这批数的最后k位，我们需要穷举
${10^k}/{2^{h+2}}$种不同的情况，我们希望这个数值不会太大。
其次，我们知道对于所有这些平方数，最末尾数总是1，所以实际贡献不同数字的有效位数只有$(21-h)*(k-1)$位，我们希望这个数字尽量大，那么最后余下的数字会更少）。
比如如果我们要求穷举空间不超过$10^10$个数据，那么可以选择k=13,h=8
也就是我们需要穷举所有类型iii)的整数的$2^8,2^9,...,2^19,2^20$次方的最后13位。
而我们知道这些数据的$2^8$的必然模$2^10$为1,同样它们模5为1，也就是模5120为1
所以我们可以选择穷举最后13为模5120为1的所有整数（把这个数看成一个数的$2^8$次方的最后13位）
然后再一次平方12次并只保留最后13位，得到所有13个数的末13位
然后我们查看这所有169位，如果覆盖0~9,那么我们证明了对于这种类型的数，最多平方到20次，必然完全覆盖0~9.而对于余下的数，我们还需要特殊处理。现在我们估计余下的数大概还有多少个:
由于我们知道这13个数最后一位必然是1，我们现在只考虑其余12*13=156位，它们不完全覆盖0~9的概率可以估算为$7*10^-7$,由于共穷举${10^13}/5120$个数，估计还留下1367总情况

mathe

接下去，我们需要再次分析这留下的一千多种情况：
这时，我们可以对着一千多种情况扩充位长，比如穷举这些情况的最末20位数的情况等等（也就是给定末13位，前面再任意添加7位数),然后再次得出新的7*13=91位，在利用它们进行淘汰；
如果还有数据剩余，可以继续这个过程。。。