回归数续集---自阶乘

chyanog

8# Frankenstein
Mathematica编程可选风格中函数式写法更简洁，本身又自带大量函数，很多时候代码可以写的很精简。相比之下，其实J语言（http://www.jsoftware.com/）更为简洁，可谓异常简洁！求解代码如下，可惜我最近没时间学。

1. 
   
2. I.(=+/@(!@"."0@":)"0)i.1e5
   

复制代码

wayne

11# chyanog
J语言的确非常之简洁，不过，与此同时，其可读性也是非常之差的。

即便是J语言的编程人员，还得动不动去查看手册，查阅 函数对应的符号，麻烦。

chyanog

我把阶乘改成双阶乘，发现这样的数也不多，也是4个，物以稀为贵嘛。到在线序列百科上验证了一下，的确如此
（http://www.research.att.com/~nja ... mp;language=english）。
My Mathematica Code：

1. 
   
2. Module[{N, n},
   
3.   N = n /. {ToRules@Reduce[9!!*n > 10^n, n, Integers]} // Max;
   
4.   Do[
   
5.    If[Tr[IntegerDigits[i]!!] == i,
   
6.     Print[i]]
   
7.    , {i, 10^(N + 1)}]
   
8.   ] // Timing
   

复制代码

1
2
3
107

有些奇怪的是Mathematica中，更专业的数组求和函数"Total"往往不如"Tr"效率高，也不如"Plus@@"。

wayne

13# chyanog
没这个理吧：

mathe

16进制结果好像有
1=1!
2=2!
260f3b66bf9=2!+6!+0!+f!+3!+b!+6!+6!+b!+f!+9!

chyanog

14# wayne
这个我也不清楚了，你的测试没有问题。不过我13楼的代码把Tr换为Total的话，速度是稍有下降的，你可以多试几次。

chyanog

mathe的结果不错！
我顺藤摸瓜找到了相关链接有，上面统计的比较全面，包括了各种进制。
http://en.wikipedia.org/wiki/Factorion

wayne

16# chyanog
仅根据你的代码的那么一丁点差距，就断定Tr逊于 Total，我感觉是不妥的。
1、Mathematica是模块化的函数式的语言，不同于C语言那种命令式的，这就意味着，同样的命令在不同的语句环境下执行效率有可能是不一样的。
2、存在即合理。Total的操作对象是线性表，List，Tr的操作对象是矩阵，List的List ，我感觉二者还是各自擅长各自的领域。

chyanog

18# wayne
分析的不错，打错了吧 ，我说的是Tr胜于Total。之所以这么说是因为有好几次用Tr效率都不在Total之下,而且Tr更短，功能上几乎可以完全取代Total，我便有些偏爱它了。
      另外现在注意到Mathematica的确有些慢，尽管用函数式编程，如果用For（或While）的话速度就更慢了，Do或Select或Cases等速度相对还算可以接受。不少人往往抱怨Java慢，最近通过几个小测试我发现和C的运行时间差不多都是一个数量级的，个别时候甚至胜过C（当然与编译器优化有关）。

mathe

给个代码，重新定义宏B就可以得到不同进制的结果。
但是B太大可能long long的数据要溢出。
另外，对于比较大的B可能速度会有点慢，如果能够在搜索过程中添加一些剪枝措施应该会快很多

1. #include <stdio.h>
   
2. #ifndef B
   
3. #define B 16
   
4. #endif
   
5. #define MAXDIGITS 100
   
6. long long facs[B];
   
7. long long dsum[B];
   
8. int counts[B];
   
9. long long cursum;
   
10. long long lowerbound;
    
11. int maxH;
    
12. void init()
    
13. {
    
14.     int i;
    
15.     facs[0]=1LL;
    
16.     dsum[0]=1LL;
    
17.     for(i=1;i<B;i++){
    
18.         facs[i]=facs[i-1]*i;
    
19.         dsum[i]=dsum[i-1]*B;
    
20.     }
    
21. }
    
22. 
    
23. int find_max_digits()
    
24. {
    
25.     long long d=facs[B-1];
    
26.     long long Bh=1LL;
    
27.     int h;
    
28.     for(h=2;;h++){
    
29.       d+=facs[B-1];Bh*=B;
    
30.       if(d<Bh)return h-1;
    
31.     }
    
32. }
    
33. 
    
34. void checkresult()
    
35. {
    
36.     int lcount[B];
    
37.     char dstr[MAXDIGITS];
    
38.     int i,first=1;
    
39.     for(i=0;i<B;i++)lcount[i]=0;
    
40.     long long u=cursum;
    
41.     int len=0;
    
42.     if(cursum==0)return;
    
43.     while(u>0){
    
44.         lcount[u%B]++;
    
45.         u/=B;
    
46.         len++;
    
47.     }
    
48.     for(i=0;i<B;i++)if(lcount[i]!=counts[i])return;
    
49.     u=cursum;
    
50.     dstr[len]='\0';
    
51.     while(u>0){
    
52.         len--;
    
53.         char d=u%B;
    
54.         if(d<=9)d+='0';
    
55.         else d+='A'-10;
    
56.         dstr[len]=d;
    
57.         u/=B;
    
58.     }
    
59.     printf("%s=",dstr);
    
60.     for(i=0;i<dstr[i]!='\0';i++){
    
61.          if(i>0)printf("+");
    
62.          printf("%c!",dstr[i]);
    
63.     }
    
64.     printf("\n");
    
65. }
    
66. 
    
67. void searchfor(int digit, int leftcount)
    
68. {
    
69.     int i,j;
    
70.     long long nsum;
    
71.     if(leftcount==0||digit<0){
    
72.        checkresult();
    
73.        return;
    
74.     }
    
75.     for(i=leftcount;i>=0;i--){
    
76.         counts[digit]=i;
    
77.         cursum+=facs[digit]*i;
    
78.         searchfor(digit-1,leftcount-i);
    
79.         cursum-=facs[digit]*i;
    
80.     }
    
81. }
    
82. 
    
83. void searchdigits(int digits)
    
84. {
    
85.     int i;
    
86.     for(i=0;i<B;i++)counts[i]=0;
    
87.     cursum=0LL;
    
88.     lowerbound=0LL;
    
89.     searchfor(B-1,digits);
    
90. }
    
91. 
    
92. int main()
    
93. {
    
94.     int h;
    
95.     init();
    
96.     maxH=find_max_digits();
    
97.     if(maxH>=MAXDIGITS){
    
98.       fprintf(stderr,"Too large digits\n");
    
99.       return -1;
    
100.     }
     
101.     searchdigits(maxH);
     
102. }
     

复制代码