数字乘积

medie2005

今天抽空实现一下,应该能找到12的.

mathe

原帖由 无心人 于 2009-3-2 17:43 发表
粗略估计在10^60内你说的数字就是
小于199 * 125 * 85 * 70个

不知道每个数字的对应数字是多少候选？？
应该是一对多啊

数目应该约等于$1/{4}!log^4(10^60)/{log(2)log(3)log(5)log(7)}~=6364870.77$

无心人

我穷搜10的
竟然发现Cache 10^8以下的最高是4
不知道错在哪里？？

无心人

最新测试，似乎10对应的素数大于10^9

无心人

1. 
   
2. char pl[100000000];
   
3. unsigned int pd[10000];
   
4. 
   
5. unsigned int prodd(unsigned int n)
   
6. {
   
7.         unsigned int r = 1;
   
8.     if (n < 10000) return pd[n];
   
9.         while (n >= 10000)
   
10.         {
    
11.        r *= pd[n % 10000];
    
12.            n /= 10000;
    
13.         }
    
14.         if (n != 0) r *= pd[n % 10000];
    
15.         return r;
    
16. }
    
17. 
    
18. void init(void)
    
19. {
    
20.         unsigned int i, j, k, l, n;
    
21. 
    
22.         for (i = 0; i <= 9; i ++)
    
23.                 for (j = 0; j <= 9; j ++)
    
24.                         for (k = 0; k <= 9; k ++)
    
25.                                 for (l = 0; l <= 9; l ++)
    
26.                                 {
    
27.                     if (i == 0)
    
28.                                         {
    
29.                                                 if (j == 0)
    
30.                                                 {
    
31.                                                         if (k == 0)
    
32.                                                                 n = l;
    
33.                                                         else
    
34.                                                                 n = k * l;
    
35.                                                 }
    
36.                                                 else n = j * k * l;
    
37.                                         }
    
38.                                         else n = i * j * k * l;
    
39. 
    
40.                                         pd[1000*i + 100*j + 10*k + l] = n;
    
41.                                 }
    
42. 
    
43. 
    
44.         for (i = 0; i <= 9; i ++)
    
45.                 pl[i] = 0;
    
46. 
    
47.         for (i = 10; i < 100000000; i ++)
    
48.         {
    
49.                 k = prodd(i);
    
50.         pl[i] = pl[k] + 1;        
    
51.         }
    
52. }       
    
53. 
    
54. int isprime(unsigned int n)
    
55. {
    
56.         if (n % 2 == 0) return 0;
    
57.         if (n % 3 == 0)        return 0;
    
58.         if (n % 5 == 0) return 0;
    
59.         if (n % 7 == 0) return 0;
    
60.         if (n % 11 == 0) return 0;
    
61.         if (n % 13 == 0) return 0;
    
62.         if (n % 17 == 0) return 0;
    
63.         if (n % 19 == 0) return 0;
    
64.         if (n % 23 == 0) return 0;
    
65.         if (n % 29 == 0) return 0;
    
66.         if (n % 31 == 0) return 0;
    
67.     return 1;
    
68. }
    
69. 
    
70. int _tmain(int argc, _TCHAR* argv[])
    
71. {
    
72.         unsigned int i, k = 1, n, p;
    
73.         init();
    
74.         printf("init finished.\n");
    
75. 
    
76.         unsigned int max = 0;
    
77.         for (i = 0; i < 100000000; i ++)
    
78.       if (max < (unsigned int)pl[i]) max = (unsigned int)pl[i];
    
79. 
    
80.         printf("MAX Product of digits level: %u\n", max);
    
81. 
    
82.     for (i = 100000001; i <= 4099999999; i ++)
    
83.         {
    
84.             if (isprime(i))
    
85.                 {
    
86.                   n = prodd(i);
    
87.                   p = 0;
    
88.                   while (n >= 100000000)
    
89.                   {
    
90.                           p ++;
    
91.                           n = prodd(n);
    
92.           }
    
93.                   
    
94.                   p += pl[n] + 1;
    
95.                   if (p >= 10)
    
96.                           printf("%u:  %u\n", i, p);
    
97.                 }
    
98.         k ++;
    
99.                 if (k % 100000000 == 0)
    
100.                 {
     
101.                         printf("\n%u\n", k);
     
102.                 }
     
103.         }
     
104.         return 0;
     
105. }
     

复制代码

无心人

P(3777888899) = 10

无心人

11的大于10^10

mathe

因子都是2,3,5,7的最小10阶数为$4996238671872=2^19*3^4*7^6$
其次为$937638166841712=2^4*3^20*7^5$

而通过第一个数字，可以构造出一个素数277777788888989。11阶的基本应该不能比这个更加小了。
应该只需要穷举第一个数字的所有可能组合就可以了

medie2005

呵呵,为了保险,还是得找10^15内的10阶数,然后,看其中有没有更优者.
不过,mathe给的结果确实是使p(n)=11的最小素数n.

[ 本帖最后由 medie2005 于 2009-3-3 13:21 编辑 ]

medie2005

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