题目55：10000以下有多少Lychrel数？

欧拉计划

Lychrel numbers

If we take 47, reverse and add, 47 + 74 = 121, which is palindromic.

Not all numbers produce palindromes so quickly. For example,

349 + 943 = 1292,
1292 + 2921 = 4213
4213 + 3124 = 7337

That is, 349 took three iterations to arrive at a palindrome.

Although no one has proved it yet, it is thought that some numbers, like 196, never produce a palindrome. A number that never forms a palindrome through the reverse and add process is called a Lychrel number. Due to the theoretical nature of these numbers, and for the purpose of this problem, we shall assume that a number is Lychrel until proven otherwise. In addition you are given that for every number below ten-thousand, it will either (i) become a palindrome in less than fifty iterations, or, (ii) no one, with all the computing power that exists, has managed so far to map it to a palindrome. In fact, 10677 is the first number to be shown to require over fifty iterations before producing a palindrome: 4668731596684224866951378664 (53 iterations, 28-digits).

Surprisingly, there are palindromic numbers that are themselves Lychrel numbers; the first example is 4994.

How many Lychrel numbers are there below ten-thousand?

NOTE: Wording was modified slightly on 24 April 2007 to emphasise the theoretical nature of Lychrel numbers.

题目：

我们将 47 与它的逆转相加，47 + 74 = 121 , 可以得到一个回文。

并不是所有数都能这么快产生回文，例如：

349 + 943 = 1292，
1292 + 2921 = 4213
4213 + 3124 = 7337

也就是说 349 需要三次迭代才能产生一个回文。

虽然还没有被证明，人们认为一些数字永远不会产生回文，例如 196 。那些永远不能通过上面的方法（逆转然后相加）产生回文的数字叫做 Lychrel 数。因为这些数字的理论本质，同时也为了这道题，我们认为一个数如果不能被证明的不是 Lychrel 数的话，那么它就是 Lychre 数。此外，对于每个一万以下的数字，你还有以下已知条件：这个数如果不能在 50 次迭代以内得到一个回文，那么就算用尽现有的所有运算能力也永远不会得到。10677 是第一个需要 50 次以上迭代得到回文的数，它可以通过 53 次迭代得到一个 28 位的回文：4668731596684224866951378664。

令人惊奇的是，有一些回文数本身也是 Lychrel 数，第一个例子是 4994。

10000 以下一共有多少个 Lychrel 数？

jerryxjr1220

1. 249
   
2. 
   
3. '''10000以下有多少lychrel数'''
   
4. def isCycle(num):
   
5.     if num == reVerse(num):
   
6.         return True
   
7.     else:
   
8.             return False
   
9. 
   
10. def reVerse(num):
    
11.         str1 = str(num)
    
12.         str2 = str1[::-1]
    
13.         return int(str2)
    
14. 
    
15. def isLychrel(num):
    
16.         cal = 1
    
17.         num1 = num + reVerse(num)
    
18.         if isCycle(num1):
    
19.                 pass
    
20.         else:
    
21.                 num2 = num1
    
22.                 while cal <= 50:
    
23.                         num3 = num2 + reVerse(num2)
    
24.                         cal += 1
    
25.                         if isCycle(num3):
    
26.                                 break
    
27.                         else:
    
28.                                 num2 = num3
    
29.         if cal <= 50:
    
30.                 return 0
    
31.         else:
    
32.                 return 1
    
33. 
    
34. count = 0
    
35. for i in range(10,10000):
    
36.         if isLychrel(i):
    
37.                 count += 1
    
38. print(count)

复制代码

愤怒的大头菇

先算出非Lychrel数，再用9999-count

1. def Rec(x):
   
2.     tmp = list(str(x))
   
3.     temp = tmp[:]
   
4.     temp.reverse()
   
5.     if tmp == temp:
   
6.         return True
   
7.     return False
   
8. count = 0
   
9. for i in range(1,10000):
   
10.     pmt = i
    
11.     for j in range(50):
    
12.         tmp = ''
    
13.         for n in range(1,len(str(pmt))+1):
    
14.             tmp += str(pmt)[-n]
    
15.         temp = pmt+int(tmp.lstrip('0'))
    
16.         if Rec(temp):
    
17.             count+=1
    
18.             break
    
19.         pmt = temp
    
20.         
    
21. print(9999-count)

复制代码

结果：249

芒果加黄桃

1. # encoding:utf-8
   
2. # 寻找lychrel数
   
3. from time import time
   
4. def euler053(N=1000000):
   
5.     l_result = []
   
6.     for i in range(1, 10000):
   
7.         num = i
   
8.         flag = True
   
9.         for count in range(1, 51):
   
10.             num += int(str(num)[::-1])
    
11.             if int(str(num)[::-1]) == num:
    
12.                 flag = False
    
13.                 break
    
14.         if flag:
    
15.             l_result.append(i)
    
16.     print(len(l_result))
    
17. if __name__ == '__main__':
    
18.     start = time()
    
19.     euler053()
    
20.     print('cost %.6f sec' % (time() - start))
    

复制代码

249
cost 0.089009 sec

渡风

此代码使用matlab编程
Problem55所用时间为： 3.7305秒
Problem55的答案为： 249

1. %% Problem55.m
   
2. % 最后编辑时间：17-06-16 10:03
   
3. % 问题：10000以下有多少个Lychrel数
   
4. 
   
5. % Problem55所用时间为： 3.7305秒
   
6. % Problem55的答案为： 249
   
7. 
   
8. function Output = Problem55()
   
9. tic
   
10. 
    
11. Total = 0;
    
12. for ii = 1:10000
    
13.     if Islychrel(ii) == 1
    
14.         Total = Total + 1;
    
15.     end
    
16. end
    
17. Output = Total;
    
18.                   
    
19. toc
    
20. disp('此代码使用matlab编程')
    
21. disp(['Problem55所用时间为： ',num2str(toc),'秒'])
    
22. disp(['Problem55的答案为： ',num2str(Output)])
    
23. end
    
24. 
    
25. %% Islychrel.m
    
26. % 输入一个数，判定其是否为Lychrel数
    
27. % 超过50次迭代，默认其不是Lychrel数
    
28. function Judge = Islychrel(n)
    
29. if nargin == 0
    
30. n = 196;
    
31. end
    
32. Limit = 50 - 1;
    
33. Time = 0;
    
34. Now = num2str(n) - '0';
    
35. 
    
36. Judge = 1;
    
37. 
    
38. % Loops
    
39. while (Time < Limit )
    
40.     Time = Time + 1;
    
41.     Next = Vector_Plus(Now,fliplr(Now));
    
42.     if sum(abs(Next - fliplr(Next))) == 0;
    
43.         Judge = 0;
    
44.         break
    
45.     else
    
46.         Now = Next;
    
47.     end
    
48. end
    
49. end
    
50. 
    
51. %此程序实现两个向量的加法
    
52. function Output=Vector_Plus(a,b)
    
53. if nargin==0
    
54.     a=[9 9 9 9 9 9 ];
    
55.     b=[2 0];
    
56. end
    
57. L1=length(a);
    
58. L2=length(b);
    
59. L=max(L1,L2);
    
60. if L1<L2
    
61.    Span=L2-L1;
    
62.    Newa=[zeros(1,Span),a];
    
63.    Newb=b;
    
64. elseif L1>L2
    
65.    Span=L1-L2;
    
66.    Newa=a;
    
67.    Newb=[zeros(1,Span),b];
    
68. else
    
69.     Newa=a;
    
70.     Newb=b;
    
71. end
    
72. Rank=Newa+Newb;
    
73. for ii=L:-1:2
    
74.     if Rank(ii)>=10
    
75.         Rank(ii)=Rank(ii)-10;
    
76.         Rank(ii-1)=Rank(ii-1)+1;
    
77.     end
    
78. end
    
79. Biggest=0;
    
80. while (Rank(1)>=10)
    
81.     if Rank(1)>=10
    
82.        Rank(1)=Rank(1)-10;
    
83.        Biggest=Biggest+1;
    
84.     end
    
85. end
    
86. if Biggest>0
    
87.     Output=[Biggest,Rank];
    
88. else
    
89.     Output=Rank;
    
90. end
    
91. end
    
92.         
    
93.    
    
94.         

复制代码

najin

用的matlab
结果是：
   249

时间已过 2.166115 秒。
>>

k往事如烟k

249

1. def reverse_add(num):
   
2.     str1 = str(num)
   
3.     numList = []
   
4.     for i in range(len(str1)):
   
5.         numList.append(int(str1[i]))
   
6.     numList.reverse()
   
7.     str2 = ""
   
8.     for each in numList:
   
9.         str2 += str(each)
   
10.     newNum = int(str2) + num
    
11.     return newNum
    
12. 
    
13. def isPalindrome(num):
    
14.     if len(str(num)) % 2 == 0:
    
15.         str1 = ""
    
16.         str2 = ""
    
17.         for i in range(len(str(num))//2):
    
18.             str1 += str(num)[i]
    
19.             str2 += str(num)[-1-i]
    
20.         if str1 == str2:
    
21.             return True
    
22.         else:
    
23.             return False
    
24.     else:
    
25.         str1 = ""
    
26.         str2 = ""
    
27.         for i in range(len(str(num))//2):
    
28.             str1 += str(num)[i]
    
29.             str2 += str(num)[-1-i]
    
30.         if str1 == str2:
    
31.             return True
    
32.         else:
    
33.             return False
    
34. 
    
35. def isLychrel(num):
    
36.     count = 1
    
37.     tempNum = reverse_add(num)
    
38.     while count <= 50:
    
39.         if isPalindrome(tempNum):
    
40.             return False
    
41.         else:
    
42.             tempNum = reverse_add(tempNum)
    
43.             if isPalindrome(tempNum):
    
44.                 return False
    
45.             else:
    
46.                 count += 1
    
47.     if count > 50:
    
48.         return True
    
49.     else:
    
50.         return False
    
51. 
    
52. Lychrel_count = 0
    
53. for i in range(1,10000):
    
54.     if isLychrel(i):
    
55.         Lychrel_count += 1
    
56. 
    
57. print(Lychrel_count)

复制代码

王小召

共有：249 个 Lychrel 数
用时：0.156001 秒

1. import time
   
2. 
   
3. def cal_result(N_range):
   
4.     count = 0
   
5.     for num in range(1, N_range+1):
   
6.         for _ in range(50):
   
7.             str_num = str(num + int(str(num)[::-1]))
   
8. 
   
9.             if str_num == str_num[::-1]:
   
10.                 count += 1
    
11.                 break
    
12.             else:
    
13.                 num = int(str_num)
    
14.     return count
    
15. 
    
16. print("共有：{} 个 Lychrel 数\n用时：{} 秒".format(10000 - cal_result(10000), time.process_time()))

复制代码

永恒的蓝色梦想

Python:

1. def isLychrel(n):
   
2.     count=50
   
3.     n+=int(str(n)[::-1])
   
4. 
   
5.     while count:
   
6.         reversed=int(str(n)[::-1])
   
7. 
   
8.         if n==reversed:
   
9.             return False
   
10. 
    
11.         n+=reversed
    
12.         count-=1
    
13.         
    
14.     return True
    
15. 
    
16. print(sum(map(isLychrel,range(1,10000))))

复制代码

永恒的蓝色梦想

C++ 11ms

1. //249 10ms
   
2. #include<iostream>
   
3. using namespace std;
   
4. using ull=unsigned long long;
   
5. 
   
6. 
   
7. ull numreverse(ull n) {
   
8.     ull res = 0;
   
9. 
   
10.     while (n) {
    
11.         res = res * 10 + n % 10;
    
12.         n /= 10;
    
13.     }
    
14. 
    
15.     return res;
    
16. }
    
17. 
    
18. 
    
19. int main() {
    
20.     unsigned short res = 0;
    
21.     unsigned char count;
    
22.     ull i = 9999, j, reversed;
    
23. 
    
24.     while (i) {
    
25.         j = i + numreverse(i);
    
26.         count = 50;
    
27. 
    
28.         while (count--) {
    
29.             reversed = numreverse(j);
    
30. 
    
31.             if (reversed == j) {
    
32.                 goto next;
    
33.             }
    
34. 
    
35.             j += reversed;
    
36.         }
    
37. 
    
38.         ++res;
    
39. 
    
40.     next:
    
41.         --i;
    
42.     }
    
43. 
    
44.     cout << res << endl;
    
45.     return 0;
    
46. }

复制代码

debuggerzh

249

Process returned 0 (0x0)   execution time : 0.167 s
Press any key to continue.
从25题搬来高精度，略作修改

1. #include<iostream>
   
2. #include<algorithm>
   
3. #include<vector>
   
4. using namespace std;
   
5. const int M = 1e4;
   
6. 
   
7. typedef struct BigInt{
   
8.   vector<int> v;
   
9. 
   
10.   BigInt(vector<int> v):v(v){}
    
11. }BI;
    
12. 
    
13. void operator += (BI & a,const BI & x){
    
14.     vector<int> t1 = a.v;
    
15.     vector<int> t2 = x.v;
    
16.     if (a.v.size() < x.v.size())  swap(t1,t2);
    
17. 
    
18.     for (int i = 0;i < max(t1.size(),t2.size() );i++){
    
19.       if (i < t2.size())  t1[i] += t2[i];
    
20.       if (i > 0 && t1[i-1] > 9)  {t1[i]++;  t1[i-1] -= 10;}
    
21.     }
    
22. 
    
23.     if (t1[t2.size()-1] > 9)
    
24.       if (t1.size() == t2.size() )
    
25.         {t1.push_back(1);  t1[t1.size()-2] -= 10;}
    
26.       else  {
    
27.         t1[t2.size()]++;
    
28.         for (int i = t2.size();i < t1.size()-1;i++){
    
29.           if (t1[i] > 9) {t1[i] -= 10;  t1[i+1]++;}
    
30.           else break;
    
31.         }
    
32.         t1[t2.size()-1] -= 10;
    
33.       }
    
34. 
    
35.     a.v = t1;
    
36. }
    
37. 
    
38. void trans(int x,vector<int> & v,vector<int> & u){
    
39.   while(x){
    
40.     v.push_back(x%10);
    
41.     u.insert(u.begin(), x%10);
    
42.     x /= 10;
    
43.   }
    
44. }
    
45. 
    
46. bool pal(const vector<int> & v){
    
47.   vector<int> u = v;
    
48.   reverse(u.begin(),u.end());
    
49. 
    
50.   for (int i = 0;i < v.size();i++)
    
51.     if (u[i] != v[i]) return false;
    
52. 
    
53.   return true;
    
54. }
    
55. 
    
56. bool lych(BI & x,BI & y){
    
57.   for (int j = 1;j <= 50;j++){
    
58.     x += y;
    
59.     if (pal(x.v)) return false;
    
60. 
    
61.     y.v = x.v;
    
62.     reverse(y.v.begin(),y.v.end());
    
63.   }
    
64.   return true;
    
65. }
    
66. 
    
67. int main(){
    
68.   int ans = 0;
    
69. 
    
70.   for (int i = 1;i < M;i++){
    
71.     vector<int> v,u;
    
72.     trans(i,v,u);
    
73.     BI x(v),y(u);
    
74.     if (lych(x,y)) ans++;
    
75.   }
    
76. 
    
77.   cout << ans << endl;
    
78.   return 0;
    
79. }
    

复制代码

4444567

这个Lychrel数列表是：[196, 295, 394, 493, 592, 689, 691, 788, 790, 879, 887, 978, 986, 1495, 1497, 1585, 1587, 1675, 1677, 1765, 1767, 1855, 1857, 1945, 1947, 1997, 2494, 2496, 2584, 2586, 2674, 2676, 2764, 2766, 2854, 2856, 2944, 2946, 2996, 3493, 3495, 3583, 3585, 3673, 3675, 3763, 3765, 3853, 3855, 3943, 3945, 3995, 4079, 4169, 4259, 4349, 4439, 4492, 4494, 4529, 4582, 4584, 4619, 4672, 4674, 4709, 4762, 4764, 4799, 4852, 4854, 4889, 4942, 4944, 4979, 4994, 5078, 5168, 5258, 5348, 5438, 5491, 5493, 5528, 5581, 5583, 5618, 5671, 5673, 5708, 5761, 5763, 5798, 5851, 5853, 5888, 5941, 5943, 5978, 5993, 6077, 6167, 6257, 6347, 6437, 6490, 6492, 6527, 6580, 6582, 6617, 6670, 6672, 6707, 6760, 6762, 6797, 6850, 6852, 6887, 6940, 6942, 6977, 6992, 7059, 7076, 7149, 7166, 7239, 7256, 7329, 7346, 7419, 7436, 7491, 7509, 7526, 7581, 7599, 7616, 7671, 7689, 7706, 7761, 7779, 7796, 7851, 7869, 7886, 7941, 7959, 7976, 7991, 8058, 8075, 8079, 8089, 8148, 8165, 8169, 8179, 8238, 8255, 8259, 8269, 8328, 8345, 8349, 8359, 8418, 8435, 8439, 8449, 8490, 8508, 8525, 8529, 8539, 8580, 8598, 8615, 8619, 8629, 8670, 8688, 8705, 8709, 8719, 8760, 8778, 8795, 8799, 8809, 8850, 8868, 8885, 8889, 8899, 8940, 8958, 8975, 8979, 8989, 8990, 9057, 9074, 9078, 9088, 9147, 9164, 9168, 9178, 9237, 9254, 9258, 9268, 9327, 9344, 9348, 9358, 9417, 9434, 9438, 9448, 9507, 9524, 9528, 9538, 9597, 9614, 9618, 9628, 9687, 9704, 9708, 9718, 9777, 9794, 9798, 9808, 9867, 9884, 9888, 9898, 9957, 9974, 9978, 9988, 9999]

用时0.423738 sec，长度为:249，其中本身是回文数的有[4994, 8778, 9999]

1. from time import time
   
2. def hw(n):#回文
   
3.     if str(n)==str(n)[::-1]:
   
4.         return True
   
5. def nz(n):#与逆转相加，不用判断前面是否有0
   
6.     return n + int(str(n)[::-1])
   
7. 
   
8. a = 1 #指针
   
9. n = 1
   
10. Ly = []
    
11. t = time()
    
12. while n <10000:
    
13.     tmp = nz(n)
    
14.     while a<51:
    
15.         if hw(tmp):
    
16.             break
    
17.         else:
    
18.             tmp = nz(tmp)
    
19.             a += 1
    
20.     if a >=51:
    
21.         Ly.append(n)
    
22.         a = 1
    
23.     else:
    
24.         a =1
    
25.     n += 1
    
26. l = []
    
27. for i in Ly:
    
28.     if hw(i):
    
29.         l.append(i)   
    
30. print('这个Lychrel数列表是：%s \n' % Ly)   
    
31. print('用时%.6f sec，长度为:%d，其中本身是回文数的有%s' % (time()-t, len(Ly), l))

复制代码

guosl

应用大数库mpir。

1. /*
   
2. 欧拉问题55
   
3. 答案：249
   
4. 耗时：0.0325379秒（单核）
   
5.      0.019746秒（4核）
   
6. */
   
7. #include <iostream>
   
8. #include <string>
   
9. #include <mpirxx.h>
   
10. #include <algorithm>
    
11. #include <omp.h>
    
12. using namespace std;
    
13. 
    
14. int main(void)
    
15. {
    
16.   double t = omp_get_wtime();
    
17.   int nCount = 0;
    
18. #pragma omp parallel for reduction(+:nCount)
    
19.   for (int k = 1; k < 10000; ++k)
    
20.   {
    
21.     int nc = 0;
    
22.     mpz_class a = k;
    
23.     bool bFlag = true;
    
24.     while (nc < 50)
    
25.     {
    
26.       string s1 = a.get_str();
    
27.       string s2 = s1;
    
28.       reverse(s2.begin(), s2.end());
    
29.       if (nc > 0 && s1 == s2)
    
30.       {
    
31.         bFlag = false;
    
32.         break;
    
33.       }
    
34.       ++nc;
    
35.       a += mpz_class(s2, 10);
    
36.     }
    
37.     if (bFlag)
    
38.       ++nCount;
    
39.   }
    
40.   t = omp_get_wtime() - t;
    
41.   cout << nCount << endl << t << endl;
    
42.   return 0;
    
43. }

复制代码