题目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 于 2016-10-13 10:07 编辑
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=;
b=;
end
L1=length(a);
L2=length(b);
L=max(L1,L2);
if L1<L2
Span=L2-L1;
Newa=;
Newb=b;
elseif L1>L2
Span=L1-L2;
Newa=a;
Newb=;
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=;
else
Output=Rank;
end
end
用的matlab
结果是：
249
时间已过 2.166115 秒。
>> 249
def reverse_add(num):
str1 = str(num)
numList = []
for i in range(len(str1)):
numList.append(int(str1))
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)
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)
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())) 本帖最后由 永恒的蓝色梦想 于 2020-4-18 12:25 编辑
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)))) 本帖最后由 永恒的蓝色梦想 于 2020-6-27 09:37 编辑
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;
} 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 += t2;
if (i > 0 && t1 > 9){t1++;t1 -= 10;}
}
if (t1 > 9)
if (t1.size() == t2.size() )
{t1.push_back(1);t1 -= 10;}
else{
t1++;
for (int i = t2.size();i < t1.size()-1;i++){
if (t1 > 9) {t1 -= 10;t1++;}
else break;
}
t1 -= 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 != v) 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;
}
这个Lychrel数列表是：
用时0.423738 sec，长度为:249，其中本身是回文数的有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)) 应用大数库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;
}
页:
[1]