题目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

249

'''10000以下有多少lychrel数'''
def isCycle(num):
    if num == reVerse(num):
        return True
    else:
            return False

def reVerse(num):
        str1 = str(num)
        str2 = str1[::-1]
        return int(str2)

def isLychrel(num):
        cal = 1
        num1 = num + reVerse(num)
        if isCycle(num1):
                pass
        else:
                num2 = num1
                while cal <= 50:
                        num3 = num2 + reVerse(num2)
                        cal += 1
                        if isCycle(num3):
                                break
                        else:
                                num2 = num3
        if cal <= 50:
                return 0
        else:
                return 1

count = 0
for i in range(10,10000):
        if isLychrel(i):
                count += 1
print(count)

愤怒的大头菇

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

def Rec(x):
    tmp = list(str(x))
    temp = tmp[:]
    temp.reverse()
    if tmp == temp:
        return True
    return False
count = 0
for i in range(1,10000):
    pmt = i
    for j in range(50):
        tmp = ''
        for n in range(1,len(str(pmt))+1):
            tmp += str(pmt)[-n]
        temp = pmt+int(tmp.lstrip('0'))
        if Rec(temp):
            count+=1
            break
        pmt = temp
        
print(9999-count)

结果：249

芒果加黄桃

# encoding:utf-8
# 寻找lychrel数
from time import time
def euler053(N=1000000):
    l_result = []
    for i in range(1, 10000):
        num = i
        flag = True
        for count in range(1, 51):
            num += int(str(num)[::-1])
            if int(str(num)[::-1]) == num:
                flag = False
                break
        if flag:
            l_result.append(i)
    print(len(l_result))
if __name__ == '__main__':
    start = time() 
    euler053()
    print('cost %.6f sec' % (time() - start))

249
cost 0.089009 sec

渡风

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

%% Problem55.m
% 最后编辑时间：17-06-16 10:03
% 问题：10000以下有多少个Lychrel数

% Problem55所用时间为： 3.7305秒
% Problem55的答案为： 249

function Output = Problem55()
tic

Total = 0;
for ii = 1:10000
    if Islychrel(ii) == 1
        Total = Total + 1;
    end
end
Output = Total;
                  
toc
disp('此代码使用matlab编程')
disp(['Problem55所用时间为： ',num2str(toc),'秒'])
disp(['Problem55的答案为： ',num2str(Output)])
end

%% Islychrel.m
% 输入一个数，判定其是否为Lychrel数
% 超过50次迭代，默认其不是Lychrel数
function Judge = Islychrel(n)
if nargin == 0
n = 196;
end
Limit = 50 - 1;
Time = 0;
Now = num2str(n) - '0';

Judge = 1;

% Loops
while (Time < Limit )
    Time = Time + 1;
    Next = Vector_Plus(Now,fliplr(Now));
    if sum(abs(Next - fliplr(Next))) == 0;
        Judge = 0;
        break
    else
        Now = Next;
    end
end
end

%此程序实现两个向量的加法
function Output=Vector_Plus(a,b)
if nargin==0
    a=[9 9 9 9 9 9 ];
    b=[2 0];
end
L1=length(a);
L2=length(b);
L=max(L1,L2);
if L1<L2
   Span=L2-L1;
   Newa=[zeros(1,Span),a];
   Newb=b;
elseif L1>L2
   Span=L1-L2;
   Newa=a; 
   Newb=[zeros(1,Span),b];
else
    Newa=a;
    Newb=b;
end
Rank=Newa+Newb;
for ii=L:-1:2
    if Rank(ii)>=10
        Rank(ii)=Rank(ii)-10;
        Rank(ii-1)=Rank(ii-1)+1;
    end
end
Biggest=0;
while (Rank(1)>=10)
    if Rank(1)>=10
       Rank(1)=Rank(1)-10;
       Biggest=Biggest+1;
    end
end
if Biggest>0
    Output=[Biggest,Rank];
else
    Output=Rank;
end
end
        
   
        

najin

用的matlab
结果是：
   249

时间已过 2.166115 秒。
>>

k往事如烟k

249

def reverse_add(num):
    str1 = str(num)
    numList = []
    for i in range(len(str1)):
        numList.append(int(str1[i]))
    numList.reverse()
    str2 = ""
    for each in numList:
        str2 += str(each)
    newNum = int(str2) + num
    return newNum

def isPalindrome(num):
    if len(str(num)) % 2 == 0:
        str1 = ""
        str2 = ""
        for i in range(len(str(num))//2):
            str1 += str(num)[i]
            str2 += str(num)[-1-i]
        if str1 == str2:
            return True
        else:
            return False
    else:
        str1 = ""
        str2 = ""
        for i in range(len(str(num))//2):
            str1 += str(num)[i]
            str2 += str(num)[-1-i]
        if str1 == str2:
            return True
        else:
            return False

def isLychrel(num):
    count = 1
    tempNum = reverse_add(num)
    while count <= 50:
        if isPalindrome(tempNum):
            return False
        else:
            tempNum = reverse_add(tempNum)
            if isPalindrome(tempNum):
                return False
            else:
                count += 1
    if count > 50:
        return True
    else:
        return False

Lychrel_count = 0
for i in range(1,10000):
    if isLychrel(i):
        Lychrel_count += 1

print(Lychrel_count)

王小召

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

import time

def cal_result(N_range):
    count = 0
    for num in range(1, N_range+1):
        for _ in range(50):
            str_num = str(num + int(str(num)[::-1]))

            if str_num == str_num[::-1]:
                count += 1
                break
            else:
                num = int(str_num)
    return count

print("共有：{} 个 Lychrel 数\n用时：{} 秒".format(10000 - cal_result(10000), time.process_time()))

永恒的蓝色梦想

Python:

def isLychrel(n):
    count=50
    n+=int(str(n)[::-1])

    while count:
        reversed=int(str(n)[::-1])

        if n==reversed:
            return False

        n+=reversed
        count-=1
        
    return True

print(sum(map(isLychrel,range(1,10000))))

永恒的蓝色梦想

C++ 11ms

//249 10ms
#include<iostream>
using namespace std;
using ull=unsigned long long;


ull numreverse(ull n) {
    ull res = 0;

    while (n) {
        res = res * 10 + n % 10;
        n /= 10;
    }

    return res;
}


int main() {
    unsigned short res = 0;
    unsigned char count;
    ull i = 9999, j, reversed;

    while (i) {
        j = i + numreverse(i);
        count = 50;

        while (count--) {
            reversed = numreverse(j);

            if (reversed == j) {
                goto next;
            }

            j += reversed;
        }

        ++res;

    next:
        --i;
    }

    cout << res << endl;
    return 0;
}

debuggerzh

249

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

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
const int M = 1e4;

typedef struct BigInt{
  vector<int> v;

  BigInt(vector<int> v):v(v){}
}BI;

void operator += (BI & a,const BI & x){
    vector<int> t1 = a.v;
    vector<int> t2 = x.v;
    if (a.v.size() < x.v.size())  swap(t1,t2);

    for (int i = 0;i < max(t1.size(),t2.size() );i++){
      if (i < t2.size())  t1[i] += t2[i];
      if (i > 0 && t1[i-1] > 9)  {t1[i]++;  t1[i-1] -= 10;}
    }

    if (t1[t2.size()-1] > 9)
      if (t1.size() == t2.size() )
        {t1.push_back(1);  t1[t1.size()-2] -= 10;}
      else  {
        t1[t2.size()]++;
        for (int i = t2.size();i < t1.size()-1;i++){
          if (t1[i] > 9) {t1[i] -= 10;  t1[i+1]++;}
          else break;
        }
        t1[t2.size()-1] -= 10;
      }

    a.v = t1;
}

void trans(int x,vector<int> & v,vector<int> & u){
  while(x){
    v.push_back(x%10);
    u.insert(u.begin(), x%10);
    x /= 10;
  }
}

bool pal(const vector<int> & v){
  vector<int> u = v;
  reverse(u.begin(),u.end());

  for (int i = 0;i < v.size();i++)
    if (u[i] != v[i]) return false;

  return true;
}

bool lych(BI & x,BI & y){
  for (int j = 1;j <= 50;j++){
    x += y;
    if (pal(x.v)) return false;

    y.v = x.v;
    reverse(y.v.begin(),y.v.end());
  }
  return true;
}

int main(){
  int ans = 0;

  for (int i = 1;i < M;i++){
    vector<int> v,u;
    trans(i,v,u);
    BI x(v),y(u);
    if (lych(x,y)) ans++;
  }

  cout << ans << endl;
  return 0;
}

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]

from time import time
def hw(n):#回文
    if str(n)==str(n)[::-1]:
        return True
def nz(n):#与逆转相加，不用判断前面是否有0
    return n + int(str(n)[::-1])

a = 1 #指针
n = 1
Ly = []
t = time()
while n <10000:
    tmp = nz(n)
    while a<51:
        if hw(tmp):
            break
        else:
            tmp = nz(tmp)
            a += 1
    if a >=51:
        Ly.append(n)
        a = 1
    else:
        a =1
    n += 1
l = []
for i in Ly:
    if hw(i):
        l.append(i)   
print('这个Lychrel数列表是：%s \n' % Ly)   
print('用时%.6f sec，长度为:%d，其中本身是回文数的有%s' % (time()-t, len(Ly), l))

guosl

应用大数库mpir。

/*
欧拉问题55
答案：249
耗时：0.0325379秒（单核）
     0.019746秒（4核）
*/
#include <iostream>
#include <string>
#include <mpirxx.h>
#include <algorithm>
#include <omp.h>
using namespace std;

int main(void)
{
  double t = omp_get_wtime();
  int nCount = 0;
#pragma omp parallel for reduction(+:nCount)
  for (int k = 1; k < 10000; ++k)
  {
    int nc = 0;
    mpz_class a = k;
    bool bFlag = true;
    while (nc < 50)
    {
      string s1 = a.get_str();
      string s2 = s1;
      reverse(s2.begin(), s2.end());
      if (nc > 0 && s1 == s2)
      {
        bFlag = false;
        break;
      }
      ++nc;
      a += mpz_class(s2, 10);
    }
    if (bFlag)
      ++nCount;
  }
  t = omp_get_wtime() - t;
  cout << nCount << endl << t << endl;
  return 0;
}