数字乘积

无心人

如果进行二次筛选， 得到的结果应该更少

mathe

其实现在有个问题，就是是否存在12阶以上的整数。 当然通常我们回想当然认为应该存在。

无心人

我想，筛选后 512位内的结果能保存成一个2^32长的位数组 n = 2^p * 3^q * 7^r 然后对上面的数据置为 对应(p << (11 + 10)) + (q << 10) + r位置的bit = 1 只要对任何的n查找 其数位乘积prod(n)对应的bit是否是1 不是，则清位 这么做，能大大缩小候选 再测试每个的阶

无心人

是可以存在的 现在证明了11阶的存在 假设有数字n 则显然数位乘积prod(n) < n 而当n充分大时，我们可以证明一定能找到n, prod(n)可以大于任何指定的数字 或者说，应该存在任意阶的数字

无心人

至于为什么不好找11阶的仅有因子2，3，7的数字 是5，0在作怪 数字里有5， 0的比例太大了

无心人

比如， 对应2^26的在2^p * 3^q * 7^r的p, q, r 10^512内只有 26, 0, 2 26, 0, 4 26, 0, 5 26, 3, 0 26, 3, 6 26, 4, 7 26, 8, 9 26, 10, 30 26, 15, 0 26, 21, 1 26, 24, 16

无心人

2. #include <stdio.h>
3. #include <stdlib.h>
4. #include <gmp.h>
5. #include <math.h>
7. #define l2 1700
8. #define l3 1073
9. #define l7 605
11. mpz_t t2, t3, t7, tn;
12. mpz_t a, b, c;
13. char out[1024];
14. unsigned int d[10][3];
16. int filter(unsigned int i, unsigned int j, unsigned int k)
17. {
18. char * c = out;
19. int e = 0, f = 0;
20. int dc;
21. if ((i == 0) && (j == 0)) return 0;
22. if ((j == 0) && (k == 0)) return 0;
23. mpz_pow_ui(a, t2, i);
24. mpz_pow_ui(b, t3, j);
25. mpz_pow_ui(tn, t7, k);
26. mpz_mul(tn, tn, a);
27. mpz_mul(tn, tn, b);
28. mpz_get_str(out, 10, tn);
29. // printf("%s\n", out);
30. while (*c)
31. {
32. if (* c == '0')
33. return 0;
34. if (* c == '5') f = 1;
35. if ((unsigned)(*c) % 2 == 0) e = 1;
36. if ((f == 1) && (e == 1)) return 0;
37. c ++;
38. }
39. return 1;
40. }
42. int main(void)
43. {
44. unsigned int i, j, k;
45. int p = 0;
47. mpz_init(t2);
48. mpz_init(t3);
49. mpz_init(t7);
50. mpz_init(tn);
51. mpz_init(a);
52. mpz_init(b);
53. mpz_init(c);
54. mpz_set_ui(t2, 2);
55. mpz_set_ui(t3, 3);
56. mpz_set_ui(t7, 7);
57. for (i = 0; i <= l2; i ++)
58. for (j = 0; j <= l3; j ++)
59. for (k = 0; k <= l7; k ++)
60. if (log10(2.0) * i + log10(3.0) * j + log10(7.0) * k <= 512.0)
61. if (filter(i, j, k))
62. {
63. fprintf(stdout, "%u, %u, %u\n", i, j, k);
64. fflush(stdout);
65. p ++;
66. }
68. printf("Total: %u\n", p);
69. mpz_clear(c);
70. mpz_clear(b);
71. mpz_clear(a);
72. mpz_clear(tn);
73. mpz_clear(t2);
74. mpz_clear(t3);
75. mpz_clear(t7);
76. return 0;
77. }

复制代码

用了更准确的筛选方式 但100内需要补充带5的

mathe

原帖由 无心人 于 2009-3-3 16:37 发表 是可以存在的 现在证明了11阶的存在 假设有数字n 则显然数位乘积prod(n) < n 而当n充分大时，我们可以证明一定能找到n, prod(n)可以大于任何指定的数字 或者说，应该存在任意阶的数字

不一定。只要其中任何一次变换后任何位上出现5以及其它位中有一个是偶数，那么下一次变换就直接出现0，从而接着马上结束了.

无心人

那假设出现一步0的概率是99.999999% 连续12次都不出现一步0的概率在n充分大的情况下也是很大的啊 比如我设定的512位，连续12步不出现一步0的概率是1 / 10^96 通过的数字也不少了

无心人

不过 好像只有2，3，7的且数位不是一步0的数字组合 越来越少 我程序的输出慢了下来