Brain Storm

无心人

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

2010-11-2 08:37 上传

点击文件名下载附件

无心人

2. #include <stdio.h>
3. #include <stdlib.h>
4. #include <gmp.h>
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};
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. }
24. void main(void)
25. {
26. unsigned long i, j, c, pow10 = 10;
27. mpz_t n;
28. mpz_init(n);
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. }
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

2. f[n_] := NestWhile[# + 1 &, 2,
3. Union@IntegerDigits@Nest[#^2 &, n, #] != Range[0, 9] &]
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位，在利用它们进行淘汰； 如果还有数据剩余，可以继续这个过程。。。