数字乘积

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以内都不行

无心人

1. 
   
2. #include <stdio.h>
   
3. #include <stdlib.h>
   
4. #include <gmp.h>
   
5. #include <math.h>
   
6. 
   
7. #define l2 1700
   
8. #define l3 1073
   
9. #define l7 605
   
10. 
    
11. mpz_t t2, t3, t7, tn;
    
12. mpz_t a, b, c;
    
13. char out[1024];
    
14. 
    
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. }
    
35. 
    
36. int main(void)
    
37. {
    
38.   int i, j, k;
    
39.   int p = 0;
    
40. 
    
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.               }
    
60. 
    
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. }
    

复制代码