回归数续集---自阶乘

chyanog

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

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

复制代码

wayne

11# chyanog J语言的确非常之简洁，不过，与此同时，其可读性也是非常之差的。 即便是J语言的编程人员，还得动不动去查看手册，查阅 函数对应的符号，麻烦。

chyanog

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

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. }
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. }
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. }
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. }
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. }
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. }

复制代码