数字乘积

medie2005

p(n)=12要困难很多. 我目前正在找10^100内的11阶数, 但目前未发现一个.

mathe

不需要，我上面给出的信息已经可以用来证明这个数是11阶的最小素数了。 假设还有更小的素数，那么它最多15位，所以所有位数字的乘积不超过$9^15<937638166841712$ 也就是证明了只能使用第一个数字来构造这个素数。 而第一个数字构造出的所有数中，这个应该已经是第二小的了（这个可能需要一些比较好的证明方法 ） 不过对于12阶以上的数字，要超过long long表示范围，需要用大数运算才行了。

无心人

汗 这么大 幸亏我终止了搜索 否则还不搜索10年啊 中午想明白了 大于100的各阶有效数字（能向上逆推的）不能有因子5 而只有因子2， 3， 7的数字是很少的 假设以个位数字做根 则，每个有效数字链接到这个上面 组成一个树 如果成功构造这个树 应该能加速筛选过程

无心人

假设求取 512位内的数字 2^p * 3^q * 7^r p <= 1700, q <= 1073, r <= 605 但总可能是很少的

无心人

512位整数仅还有2，3，7因子的共 185172417个 而这里的数字位中不能有5 这可以筛掉一大部分了

mathe

这个结论应该成立，但是证明不容易。 主要是在于因子2的数目应该越多越好（而最终结果素数里面应该含有不少8）

无心人

可以先把符合条件的筛出来 有没有某种更好的限制 比如能否求出每个数字对10^n的一个模 以简化筛选？？？？

无心人

10^8内的数字有多少数位有5的？

mathe

原帖由 medie2005 于 2009-3-3 13:37 发表 p(n)=12要困难很多. 我目前正在找10^100内的11阶数, 但目前未发现一个.

我只穷举因子2,3,7.看来10^200以内都不行

无心人

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];
15. int filter(unsigned int i, unsigned int j, unsigned int k)
16. {
17. char * c = out;
18. if ((i == 0) && (j == 0)) return 0;
19. if ((j == 0) && (k == 0)) return 0;
20. mpz_pow_ui(a, t2, i);
21. mpz_pow_ui(b, t3, j);
22. mpz_pow_ui(tn, t7, k);
23. mpz_mul(tn, tn, a);
24. mpz_mul(tn, tn, b);
25. mpz_get_str(out, 10, tn);
26. // printf("%s\n", out);
27. while (*c)
28. {
29. if (*c == '5')
30. return 0;
31. c ++;
32. }
33. return 1;
34. }
36. int main(void)
37. {
38. int i, j, k;
39. int p = 0;
41. mpz_init(t2);
42. mpz_init(t3);
43. mpz_init(t7);
44. mpz_init(tn);
45. mpz_init(a);
46. mpz_init(b);
47. mpz_init(c);
48. mpz_set_ui(t2, 2);
49. mpz_set_ui(t3, 3);
50. mpz_set_ui(t7, 7);
51. for (i = 0; i <= l2; i ++)
52. for (j = 0; j <= l3; j ++)
53. for (k = 0; k <= l7; k ++)
54. if (log10(2.0) * i + log10(3.0) * j + log10(7.0) * k <= 512.0)
55. if (filter(i, j, k))
56. {
57. printf("%u, %u, %u\n", i, j, k);
58. p ++;
59. }
61. printf("Total: %u\n", p);
62. mpz_clear(c);
63. mpz_clear(b);
64. mpz_clear(a);
65. mpz_clear(tn);
66. mpz_clear(t2);
67. mpz_clear(t3);
68. mpz_clear(t7);
69. return 0;
70. }

复制代码