数字乘积

无心人

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

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

无心人

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. unsigned int d[10][3];
    
15. 
    
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. }
    
41. 
    
42. int main(void)
    
43. {
    
44.   unsigned int i, j, k;
    
45.   int p = 0;
    
46.   
    
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.               }
    
67. 
    
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的数字组合
越来越少

我程序的输出慢了下来