题目92：考察具有有趣性质的平方数链

欧拉计划 · 发表于 2016-8-11 23:14:50

马上注册，结交更多好友，享用更多功能^_^

您需要登录才可以下载或查看，没有账号？立即注册

x

本帖最后由永恒的蓝色梦想于 2020-6-5 14:24 编辑

Square digit chains

A number chain is created by continuously adding the square of the digits in a number to form a new number until it has been seen before.

For example,

44 → 32 → 13 → 10 → 1 → 1
85 → 89 → 145 → 42 → 20 → 4 → 16 → 37 → 58 → 89

Therefore any chain that arrives at 1 or 89 will become stuck in an endless loop. What is most amazing is that EVERY starting number will eventually arrive at 1 or 89.

How many starting numbers below ten million will arrive at 89?

题目：

通过将一个数各位的平方不断相加，直到遇到已经出现过的数字，可以形成一个数字链。

例如：
44 → 32 → 13 → 10 → 1 → 1
85 → 89 → 145 → 42 → 20 → 4 → 16 → 37 → 58 → 89

因此任何到达 1 或 89 的数字链都会陷入无限循环。令人惊奇的是，以任何数字开始，最终都会到达 1 或 89。

以一千万以下的数字 n 开始，有多少个 n 会到达 89？

迷雾少年 · 发表于 2016-8-31 16:48:19

结果12587445

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
/*
返回一个数字各位数平方相加后的数
*/
int get(int num)
{
int sum=0;
int t = num;
while(num)
{
sum+= (num%10)*(num%10);
num/=10;
}
return sum;
}
int main()
{
//限制从1KW
vector<int> result;
int j = 0;
int sum=0;//统计有89的数字
for (int i =1;i<=10000000;i++)
{
j=i;
int value = 0;
//获取这个数字各位数平方和
while(1)
{
value = get(j);
if(value==89) sum++;
if(result.end()==find(result.begin(),result.end(),value))
{
//没找到到了
result.push_back(value);
j=value;
}else
{
//找到退出
result.push_back(value);
break;
}
}
//输出结果
//std::cout<<i<<":";
for (int m=0;m<result.size();m++)
{
//std::cout<<result[m]<<" ";
}
//std::cout<<endl;
result.clear();
}
std::cout<<"结果"<<sum<<endl;
return 0;
}

复制代码

QingXin · 发表于 2016-9-18 23:31:59

10000000以下平方和最大的数是9999999，其平方和为81*7=567。所以，可以先建立一个600以下的字典，其他数在运行过程中一旦碰到字典中的数，马上将1或89作为结果反馈。这样，可以加速运算过程。代码如下，结果为8581146。

def get_sum(x):
number_list = []
while x:
x,temp = divmod(x,10)
number_list.insert(0,temp)
return sum([t*t for t in number_list])
num_dict = {}
for i in range(1,600):
s = i
while s != 1 and s != 89:
if num_dict.get(s,0):
s = num_dict[s]
break
s = get_sum(s)
num_dict[i] = s
count_89 = 0
for i in range(1,10000001):
s = get_sum(i)
if num_dict[s] == 89:
count_89+=1
print(count_89)

复制代码

jerryxjr1220 · 发表于 2016-10-18 11:51:14

QingXin 发表于 2016-9-18 23:31
10000000以下平方和最大的数是9999999，其平方和为81*7=567。所以，可以先建立一个600以下的字典，其他数在 ...

8581146
[Finished in 65.9s]
楼上的方法比我好，我只是暴力求解，花了1分多钟。

def chain(n):
i = n
while True:
s = 0
while True:
s += (i%10)**2
i = int(i/10)
if i == 0:
break
i = s
if i == 89:
return True
elif i == 1:
return False
else:
pass
count = 0
for i in range(2,10000000):
if chain(i):
count += 1
print count

复制代码

愤怒的大头菇 · 发表于 2016-11-23 10:17:51

def Loop(x,count=0):
while x!=1 and x!=89:
for each in str(x):
count += int(each)**2
x = count
count = 0
if x ==89:
return True
if x == 1:
return False
total = 0
for i in range(1,10000000):
if Loop(i,count=0):
total += 1
print(total)

复制代码

结果：8581146

芒果加黄桃 · 发表于 2017-3-6 16:53:04

# encoding:utf-8
# 具有有趣性质的平方数链
from time import time
N = 10000000
flag = [0] * (N + 1)
def getNums(n):
while (n != 1 and n != 89):
if flag[n] == 1:
return 1
elif flag[n] == 89:
return 89
sums = 0
for x in str(n):
sums += (int(x)) ** 2
n = sums
return n
def euler092(N):
for n in range(1, N):
t = getNums(n)
# print(n,t)
if t == 1:
flag[n] = 1
else:
flag[n] = 89
print(len([k for (k, v) in enumerate(flag) if v == 89]))
if __name__ == '__main__':
start = time()
euler092(N)
print('cost %.6f sec' % (time() - start))

复制代码

永恒的蓝色梦想 · 发表于 2019-7-22 11:07:04

本帖最后由永恒的蓝色梦想于 2021-2-12 20:49 编辑

借鉴3L思路
C++ 265ms

#include<iostream>
constexpr unsigned char arrive_at(unsigned int x)noexcept {
constexpr unsigned char squares[] = { 0, 1, 4, 9, 16, 25, 36, 49, 64, 81 };
static unsigned char cache[7 * squares[9] + 1] = {[1] = 1, [89] = 89};
unsigned int temp;
unsigned short res = 0;
while (x) {
temp = x;
x /= 10;
res += squares[temp - x * 10];
}
if (cache[res]) {
return cache[res];
}
return cache[res] = arrive_at(res);
}
int main() {
using namespace std;
ios::sync_with_stdio(false);
unsigned int count = 0, num;
for (num = 1; num < 10000000; num++) {
count += arrive_at(num) == 89;
}
cout << count << endl;
return 0;
}

复制代码

永恒的蓝色梦想 · 发表于 2020-6-19 15:41:00

本帖最后由永恒的蓝色梦想于 2020-6-25 19:57 编辑

QingXin 发表于 2016-9-18 23:31
10000000以下平方和最大的数是9999999，其平方和为81*7=567。所以，可以先建立一个600以下的字典，其他数在 ...

把 get_sum 函数改为

def get_sum(x):
result = 0
while x:
x,temp = divmod(x,10)
result += temp * temp
return result

复制代码

会更好。

QingXin · 发表于 2020-6-25 13:00:04

永恒的蓝色梦想发表于 2020-6-19 15:41
把 get_sum 函数改为会更好。

嗯嗯，谢谢指正！确实，建一个列表占用了时间，这个列表没必要建立的。版主的代码里面应该写 result += temp**2 ？太匆忙忘记了吧

永恒的蓝色梦想 · 发表于 2020-6-25 19:57:22

QingXin 发表于 2020-6-25 13:00
嗯嗯，谢谢指正！确实，建一个列表占用了时间，这个列表没必要建立的。版主的代码里面应该写 result ...

确实是

写错了

debuggerzh · 发表于 2020-8-21 10:15:21

8581146

Process returned 0 (0x0) execution time : 0.514 s
Press any key to continue.
递归+记忆化搜索

#include<iostream>
using namespace std;
const int M = 1e7;
int e[M] = {0};
int square_sum(int x){
int res = 0;
int x0 = x;
if (e[x0]) return e[x0];
while(x){
int t = x % 10;
res += t*t;
x /= 10;
}
if (res == 1 || res == 89) return e[x0] = res;
return e[x0] = square_sum(res);
}
int main(){
int cnt = 0;
for (int i = 1;i < M;i++){
square_sum(i);
if (e[i] == 89) cnt++;
}
cout << cnt << endl;
return 0;
}

复制代码

guosl · 发表于 2022-1-17 13:56:20

/*
答案：8581146
耗时：0.314319秒（八核）
*/
#include <iostream>
#include <algorithm>
#include <omp.h>
using namespace std;
int v1[5] = { 1,10,13,32,44 };
int v89[9] = { 4,16,20,37,42,58,85,89,145 };
int S[10] = { 0,1,4,9,16,25,36,49,64,81 };
int main(void)
{
double t = omp_get_wtime();
int nCount = 0;
#pragma omp parallel for shared(v1,v89,S) reduction(+:nCount)
for (int n = 1; n <= 10000000; ++n)
{
int k = n;
bool bFind = false;
while (true)
{
int nSum = 0;
while (k != 0)
{
nSum += S[k % 10];
k /= 10;
}
if (binary_search(v1, v1 + 5, nSum))
break;
if (binary_search(v89, v89 + 9, nSum))
{
bFind = true;
break;
}
k = nSum;
}
if (bFind)
++nCount;
}
t = omp_get_wtime() - t;
cout << nCount << endl << t << endl;
return 0;
}

复制代码

账号		自动登录	找回密码
密码			立即注册

题目92：考察具有有趣性质的平方数链

马上注册，结交更多好友，享用更多功能^_^

浏览过的版块