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

欧拉计划

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？

迷雾少年

结果12587445

1. #include <iostream>
   
2. #include <vector>
   
3. #include <algorithm>
   
4. using namespace  std;
   
5. /*
   
6. 返回一个数字各位数平方相加后的数
   
7. */
   
8. int get(int num)
   
9. {
   
10.         int sum=0;
    
11.         int t = num;
    
12.         while(num)
    
13.         {
    
14.                 sum+= (num%10)*(num%10);
    
15.                 num/=10;
    
16.         }
    
17.         return sum;
    
18. }
    
19. int main()
    
20. {
    
21.         //限制从1KW
    
22.         vector<int> result;
    
23.         int j = 0;
    
24.         int sum=0;//统计有89的数字
    
25.         for (int i =1;i<=10000000;i++)
    
26.         {
    
27.                 j=i;
    
28.                 int value = 0;
    
29.                
    
30.        
    
31.                         //获取这个数字各位数平方和
    
32.                         while(1)
    
33.                         {
    
34. 
    
35.                        
    
36.                                 value = get(j);
    
37.                                 if(value==89) sum++;
    
38.                                 if(result.end()==find(result.begin(),result.end(),value))
    
39.                                 {
    
40.                                         //没找到到了
    
41.                                         result.push_back(value);
    
42.                                         j=value;
    
43.                                        
    
44.                                 }else
    
45.                                 {
    
46.                                         //找到 退出
    
47.                                         result.push_back(value);
    
48.                                         break;
    
49.                                           
    
50.                                 }
    
51. 
    
52.                         }
    
53.                         //输出结果
    
54.                        
    
55.                         //std::cout<<i<<":";
    
56.                         for (int m=0;m<result.size();m++)
    
57.                         {
    
58.                                 //std::cout<<result[m]<<" ";
    
59.                         }
    
60.                         //std::cout<<endl;
    
61.                         result.clear();
    
62.        
    
63.         }
    
64.         std::cout<<"结果"<<sum<<endl;
    
65.         return 0;
    
66. }

复制代码

QingXin

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

1. def get_sum(x):
   
2.     number_list = []
   
3.     while x:
   
4.         x,temp = divmod(x,10)
   
5.         number_list.insert(0,temp)
   
6.     return sum([t*t for t in number_list])
   
7. 
   
8. num_dict = {}
   
9. 
   
10. for i in range(1,600):
    
11.     s = i
    
12.     while s != 1 and s != 89:
    
13.         if num_dict.get(s,0):
    
14.             s = num_dict[s]
    
15.             break
    
16.         s = get_sum(s)
    
17.     num_dict[i] = s
    
18. 
    
19. count_89 = 0
    
20. for i in range(1,10000001):
    
21.     s = get_sum(i)
    
22.     if num_dict[s] == 89:
    
23.         count_89+=1
    
24.         
    
25. print(count_89)

复制代码

jerryxjr1220

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

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

1. def chain(n):
   
2.         i = n
   
3.         while True:
   
4.                 s = 0
   
5.                 while True:
   
6.                         s += (i%10)**2
   
7.                         i = int(i/10)
   
8.                         if i == 0:
   
9.                                 break
   
10.                 i = s
    
11.                 if i == 89:
    
12.                         return True
    
13.                 elif i == 1:
    
14.                         return False
    
15.                 else:
    
16.                         pass
    
17. 
    
18. count = 0
    
19. for i in range(2,10000000):
    
20.         if chain(i):
    
21.                 count += 1
    
22. print count

复制代码

愤怒的大头菇

1. def Loop(x,count=0):
   
2.     while x!=1 and x!=89:
   
3.         for each in str(x):
   
4.             count += int(each)**2
   
5.         x = count
   
6.         count = 0
   
7.     if x ==89:
   
8.         return True
   
9.     if x == 1:
   
10.         return False
    
11. total = 0
    
12. for i in range(1,10000000):
    
13.     if Loop(i,count=0):
    
14.         total += 1
    
15. print(total)

复制代码

结果：8581146

芒果加黄桃

1. # encoding:utf-8
   
2. # 具有有趣性质的平方数链
   
3. from time import time
   
4. N = 10000000
   
5. flag = [0] * (N + 1)
   
6. def getNums(n):
   
7.     while (n != 1 and n != 89):
   
8.         if flag[n] == 1:
   
9.             return 1
   
10.         elif flag[n] == 89:
    
11.             return 89
    
12.         sums = 0
    
13.         for x in str(n):
    
14.             sums += (int(x)) ** 2
    
15.         n = sums
    
16.     return n
    
17. 
    
18. def euler092(N):
    
19.     for n in range(1, N):
    
20.         t = getNums(n)
    
21.         # print(n,t)
    
22.         if t == 1:
    
23.             flag[n] = 1
    
24.         else:
    
25.             flag[n] = 89
    
26.     print(len([k for (k, v) in enumerate(flag) if v == 89]))      
    
27. 
    
28. if __name__ == '__main__':
    
29.     start = time()
    
30.     euler092(N)
    
31.     print('cost %.6f sec' % (time() - start))
    

复制代码

永恒的蓝色梦想

借鉴3L思路
C++ 265ms

1. #include<iostream>
   
2. 
   
3. 
   
4. 
   
5. constexpr unsigned char arrive_at(unsigned int x)noexcept {
   
6.     constexpr unsigned char squares[] = { 0, 1, 4, 9, 16, 25, 36, 49, 64, 81 };
   
7.     static unsigned char cache[7 * squares[9] + 1] = {[1] = 1, [89] = 89};
   
8.     unsigned int temp;
   
9.     unsigned short res = 0;
   
10. 
    
11.     while (x) {
    
12.         temp = x;
    
13.         x /= 10;
    
14.         res += squares[temp - x * 10];
    
15.     }
    
16. 
    
17.     if (cache[res]) {
    
18.         return cache[res];
    
19.     }
    
20. 
    
21.     return cache[res] = arrive_at(res);
    
22. }
    
23. 
    
24. 
    
25. 
    
26. int main() {
    
27.     using namespace std;
    
28.     ios::sync_with_stdio(false);
    
29. 
    
30.     unsigned int count = 0, num;
    
31. 
    
32. 
    
33.     for (num = 1; num < 10000000; num++) {
    
34.         count += arrive_at(num) == 89;
    
35.     }
    
36. 
    
37. 
    
38.     cout << count << endl;
    
39.     return 0;
    
40. }

复制代码

永恒的蓝色梦想

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

把 get_sum 函数改为

1. def get_sum(x):
   
2.     result = 0
   
3.    
   
4.     while x:
   
5.         x,temp = divmod(x,10)
   
6.         result += temp * temp
   
7.    
   
8.     return result

复制代码

会更好。

QingXin

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

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

永恒的蓝色梦想

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

确实是写错了

debuggerzh

8581146

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

1. #include<iostream>
   
2. using namespace std;
   
3. 
   
4. const int M = 1e7;
   
5. int e[M] = {0};
   
6. 
   
7. int square_sum(int x){
   
8.   int res = 0;
   
9.   int x0 = x;
   
10.   if (e[x0])  return e[x0];
    
11. 
    
12.   while(x){
    
13.     int t = x % 10;
    
14.     res += t*t;
    
15.     x /= 10;
    
16.   }
    
17. 
    
18.   if (res == 1 || res == 89) return e[x0] = res;
    
19.   return e[x0] = square_sum(res);
    
20. }
    
21. 
    
22. int main(){
    
23.   int cnt = 0;
    
24. 
    
25.   for (int i = 1;i < M;i++){
    
26.     square_sum(i);
    
27.     if (e[i] == 89) cnt++;
    
28.   }
    
29.   cout << cnt << endl;
    
30.   return 0;
    
31. }
    

复制代码

guosl

1. /*
   
2. 答案：8581146
   
3. 耗时：0.314319秒（八核）
   
4. */
   
5. #include <iostream>
   
6. #include <algorithm>
   
7. #include <omp.h>
   
8. using namespace std;
   
9. 
   
10. int v1[5] = { 1,10,13,32,44 };
    
11. int v89[9] = { 4,16,20,37,42,58,85,89,145 };
    
12. int S[10] = { 0,1,4,9,16,25,36,49,64,81 };
    
13. 
    
14. int main(void)
    
15. {
    
16.   double t = omp_get_wtime();
    
17.   int nCount = 0;
    
18. #pragma omp parallel for shared(v1,v89,S) reduction(+:nCount)
    
19.   for (int n = 1; n <= 10000000; ++n)
    
20.   {
    
21.     int k = n;
    
22.     bool bFind = false;
    
23.     while (true)
    
24.     {
    
25.       int nSum = 0;
    
26.       while (k != 0)
    
27.       {
    
28.         nSum += S[k % 10];
    
29.         k /= 10;
    
30.       }
    
31.       if (binary_search(v1, v1 + 5, nSum))
    
32.         break;
    
33.       if (binary_search(v89, v89 + 9, nSum))
    
34.       {
    
35.         bFind = true;
    
36.         break;
    
37.       }
    
38.       k = nSum;
    
39.     }
    
40.     if (bFind)
    
41.       ++nCount;
    
42.   }
    
43.   t = omp_get_wtime() - t;
    
44.   cout << nCount << endl << t << endl;
    
45.   return 0;
    
46. }

复制代码