ProjEuler[52]:Find the smallest positive integer, x, such that 2x, ...

jimogsh

It can be seen that the number, 125874, and its double, 251748, contain exactly the same digits, but in a different order.

Find the smallest positive integer, x, such that 2x, 3x, 4x, 5x, and 6x, contain the same digits.

找出最小的一个数x，要求它的2倍，3位直到6倍各数字都与原数的数位组成是相同的，只能是顺序不同。

jimogsh

1. In[18]:= Timing[x = 1;
   
2. While[SameQ @@ (Sort@IntegerDigits[x #] & /@ Range[6]) == False,
   
3.   x++]; x]
   
4. 
   
5. Out[18]= {6.349, 142857}

复制代码

这个方法似乎比较慢，如何提高速度？

FreddyMusic

1. 
   
2. k = 0;
   
3. x = 1;
   
4. 
   
5. Timing@Catch[Do[
   
6.    list = Sort@IntegerDigits[x];
   
7.    If[list == Sort@IntegerDigits[2*x] &&
   
8.      list == Sort@IntegerDigits[3*x] &&
   
9.      list == Sort@IntegerDigits[4*x] &&
   
10.      list == Sort@IntegerDigits[5*x] &&
    
11.      list == Sort@IntegerDigits[6*x], Throw[x]], {x, 1, 1000000}]]
    

复制代码

{1.5, 142857}

chyanog

有点儿冷清啦，来凑个热闹
In[65]:=

1. 
   
2. Module[{n},
   
3.   For[n = 123456, n < 999999/6, n++,
   
4.    If[Sort[IntegerDigits[n]] == Sort[IntegerDigits[2 n]] ==
   
5.      Sort[IntegerDigits[3 n]] == Sort[IntegerDigits[4 n]] ==
   
6.      Sort[IntegerDigits[5 n]] == Sort[IntegerDigits[6 n]],
   
7.       Break[]]];
   
8.   n] // Timing
   

复制代码

Out[65]= {0.593, 142857}
经测试这个效率较高 ，简洁点儿写成

1. Module[{n},
   
2.   For[n = 123456, n < 999999/6, n++,
   
3.    If[SameQ @@ (Sort /@ IntegerDigits[n*Range[6]]) == True, Break[]]];
   
4.    n] // Timing

复制代码

不过效率稍低了点儿，其实用Select也不错，不过效率更低一些

1. Select[Range[10^5, (10^6 - 1)/6],
   
2.   Sort[IntegerDigits[#]] == Sort[IntegerDigits[2 #]] ==
   
3.     Sort[IntegerDigits[3 #]] == Sort[IntegerDigits[4 #]] ==
   
4.     Sort[IntegerDigits[5 #]] == Sort[IntegerDigits[6 #]] &] // Timing

复制代码

FreddyMusic

chyanog

下次在论坛中 贴出 Mathematica 的代码时候，可以加上 论坛的格式。

格式如下：
[ code ]  中间你的代码 [ /code ]

效果如下：

1.   Thinking In Mathematica

复制代码

这样比较清晰，便于广大会员阅读和拷贝。

chyanog

呵呵，已经改过来了，以后会记得的。 5# FreddyMusic

FreddyMusic

chyanog，

Your Mathematica skill are good.

Keep post your whatever thread in our forum.

Inspired us !

ggggwhw

我向来不认为代码越短运行越快.看看下面的代码,虽然看起来很长,至少它运行的时间比上面的都短.
中间变量有时候也会节约很多时间的.

1. In[1]:= Timing[
   
2. arr = Permutations[Range[2, 9], {5}];
   
3. lena = Length@arr;
   
4. brr = Table[FromDigits[arr[[k]]], {k, 1, lena}] + 10^5;
   
5. Select[brr,
   
6.   Sort[IntegerDigits[#]] == Sort[IntegerDigits[2 #]] ==
   
7.     Sort[IntegerDigits[3 #]] == Sort[IntegerDigits[4 #]] ==
   
8.     Sort[IntegerDigits[5 #]] == Sort[IntegerDigits[6 #]] &]
   
9. ]
   
10. 
    
11. Out[1]= {0.25, {142857}}

复制代码

chyanog

实际上，我和ggggwhw已经缩小了所筛选的的范围，在汲取诸位经验的基础上再来一个更快的吧。代价就是代码有些冗长，个人感觉Select往往不如Catch、Throw搭档快(借鉴了版主和ggggwhw的思路）
In[1]:=

1. arr = Permutations[Range[2, 9], {5}];
   
2. lena = Length@arr;
   
3. brr = Table[FromDigits[arr[[k]]], {k, 1, lena}] + 10^5;
   
4. Catch[If[Sort[IntegerDigits[2 #]] == Sort[IntegerDigits[#]] &&
   
5.       Sort[IntegerDigits[3 #]] == Sort[IntegerDigits[#]] &&
   
6.       Sort[IntegerDigits[4 #]] == Sort[IntegerDigits[#]] &&
   
7.       Sort[IntegerDigits[5 #]] == Sort[IntegerDigits[#]] &&
   
8.       Sort[IntegerDigits[6 #]] == Sort[IntegerDigits[#]],
   
9.      Throw[#]] & /@ brr] // Timing
   
10. Out[1]= {0.031, 142857}

复制代码

希望大家能继续给出更好更快的方法

ggggwhw

1. In[197]:= arr = Permutations[Range[2, 9], {5}];
   
2. lena = Length@arr;
   
3. brr = Table[FromDigits[arr[[k]]], {k, 1, lena}] + 10^5;
   
4. For[j = 1, j <= lena, j++,
   
5.   If[Sort[IntegerDigits[2 brr[[j]]]] ==
   
6.      Sort[IntegerDigits[ brr[[j]]]] &&
   
7.     Sort[IntegerDigits[3  brr[[j]]]] ==
   
8.      Sort[IntegerDigits[ brr[[j]]]] &&
   
9.     Sort[IntegerDigits[4  brr[[j]]]] ==
   
10.      Sort[IntegerDigits[ brr[[j]]]] &&
    
11.     Sort[IntegerDigits[5  brr[[j]]]] ==
    
12.      Sort[IntegerDigits[ brr[[j]]]] &&
    
13.     Sort[IntegerDigits[6  brr[[j]]]] ==
    
14.      Sort[IntegerDigits[ brr[[j]]]], Print[ brr[[j]]];
    
15.    Break[]]] // Timing
    
16. 
    
17. During evaluation of In[197]:= 142857
    
18. 
    
19. Out[200]= {0.032, Null}

复制代码

看起来Catch和For的速度差不多啊.但是For有一个好处是,如果还有其它解,不用Break[]就能找的所有解了.而Catch只能找到1个解就跳出来了.这也是它比Select快的原因.Select是先找到所有满足条件的结果,再比较大小的.
下面通过找所有满足条件的解,比较For和Select的速度可知,两者的速度是在同一数量级呢,但是Select比较占内存的.

1. In[221]:= arr = Permutations[Range[2, 9], {5}];
   
2. lena = Length@arr;
   
3. brr = Table[FromDigits[arr[[k]]], {k, 1, lena}] + 10^5;
   
4. Timing[Select[brr,
   
5.   Sort[IntegerDigits[#]] == Sort[IntegerDigits[2 #]] ==
   
6.     Sort[IntegerDigits[3 #]] == Sort[IntegerDigits[4 #]] ==
   
7.     Sort[IntegerDigits[5 #]] == Sort[IntegerDigits[6 #]] &]]
   
8. Timing[For[j = 1, j <= lena, j++,
   
9.   If[Sort[IntegerDigits[2 brr[[j]]]] ==
   
10.      Sort[IntegerDigits[ brr[[j]]]] &&
    
11.     Sort[IntegerDigits[3  brr[[j]]]] ==
    
12.      Sort[IntegerDigits[ brr[[j]]]] &&
    
13.     Sort[IntegerDigits[4  brr[[j]]]] ==
    
14.      Sort[IntegerDigits[ brr[[j]]]] &&
    
15.     Sort[IntegerDigits[5  brr[[j]]]] ==
    
16.      Sort[IntegerDigits[ brr[[j]]]] &&
    
17.     Sort[IntegerDigits[6  brr[[j]]]] ==
    
18.      Sort[IntegerDigits[ brr[[j]]]], Print[ brr[[j]]]]]]
    
19. 
    
20. Out[224]= {0.235, {142857}}
    
21. 
    
22. During evaluation of In[221]:= 142857
    
23. 
    
24. Out[225]= {0.109, Null}

复制代码

chyanog

10# ggggwhw
后来不经意间注意到其实"brr"可以来得更简洁：

1. 
   
2. brr=10^5 + FromDigits /@ Permutations[Range[2, 9], {5}];
   

复制代码

guocong89

也许是偷工减料，但我记得这种数必定是素数的循环结

1. Module[
   
2.    {i, j, num, lst},
   
3.    For[i = 1, i < 100, i++,
   
4.     lst = RealDigits@(1/Prime[i]);
   
5.     If[Depth[lst] > 3,
   
6.      num = FromDigits@lst[[1, 1]];
   
7.      For[j = 2, j < 8, j++,
   
8.       If[j == 7, Return[num]];
   
9.       If[Sort@IntegerDigits[num] != Sort@IntegerDigits[num*j],
   
10.        Break[]
    
11.        ];
    
12.       ]
    
13.      ]
    
14.     ]
    
15.    ]; // Timing
    

复制代码

时间： {0., Return[142857]}