题目74：包含60个不重复项的阶乘链有多少个？

欧拉计划

Digit factorial chains

The number 145 is well known for the property that the sum of the factorial of its digits is equal to 145:

1! + 4! + 5! = 1 + 24 + 120 = 145

Perhaps less well known is 169, in that it produces the longest chain of numbers that link back to 169; it turns out that there are only three such loops that exist:

169 → 363601 → 1454 → 169
871 → 45361 → 871
872 → 45362 → 872

It is not difficult to prove that EVERY starting number will eventually get stuck in a loop. For example,

69 → 363600 → 1454 → 169 → 363601 (→ 1454)
78 → 45360 → 871 → 45361 (→ 871)
540 → 145 (→ 145)

Starting with 69 produces a chain of five non-repeating terms, but the longest non-repeating chain with a starting number below one million is sixty terms.

How many chains, with a starting number below one million, contain exactly sixty non-repeating terms?

题目：

数字 145 有一个著名的性质：其所有位上数字的阶乘和等于它本身。

1! + 4! + 5! = 1 + 24 + 120 = 145

169 不像 145 那么有名，但是 169 可以产生最长的能够连接回它自己的数字链。事实证明一共有三条这样的链：
169 → 363601 → 1454 → 169
871 → 45361 → 871
872 → 45362 → 872

不难证明每一个数字最终都将陷入一个循环。例如：

69 → 363600 → 1454 → 169 → 363601 (→ 1454)
78 → 45360 → 871 → 45361 (→ 871)
540 → 145 (→ 145)

从 69 开始可以产生一条有 5 个不重复元素的链，但是以一百万以下的数开始，能够产生的最长的不重复链包含 60 个项。

一共有多少条以一百万以下的数开始的链包含 60 个不重复项？

jerryxjr1220

进度：5 %  用时：9.589秒 >>>进度：10 %  用时：19.738秒 >>>进度：15 %  用时：29.751秒 >>>进度：20 %  用时：40.014秒 >>>进度：25 %  用时：50.148秒 >>>进度：30 %  用时：60.717秒 >>>进度：35 %  用时：70.462秒 >>>进度：40 %  用时：80.854秒 >>>进度：45 %  用时：90.833秒 >>>进度：50 %  用时：101.681秒 >>>进度：55 %  用时：111.471秒 >>>进度：60 %  用时：122.204秒 >>>进度：65 %  用时：133.301秒 >>>进度：70 %  用时：144.257秒 >>>进度：75 %  用时：154.717秒 >>>进度：80 %  用时：165.559秒 >>>进度：85 %  用时：176.494秒 >>>进度：90 %  用时：187.150秒 >>>进度：95 %  用时：198.313秒 >>>进度：100 %  用时：209.492秒 >>>答案： 402 总共用时：209.820秒

算法时间蛮长的，应该可以优化的。

from math import factorial as fct
def chain(n):
    chains = [n]
    count, calc = 1, 0
    for i in str(n):
        calc += fct(int(i))
    while calc not in chains:
        chains.append(calc)
        count += 1
        n1 = calc
        calc = 0
        for i in str(n1):
            calc += fct(int(i))
    return count

chainlist = []
for i in range(1,1000001):
    if i % 50000 == 0:
        middle = clock()
        print ('进度：%d' % int(i/10000), '%',' 用时：%.3f秒 >>>' % (middle-start), end ='')
    if chain(i) == 60:
        chainlist.append(i)
end = clock()
print ('答案： %d' % len(chainlist), '总共用时：%.3f秒' % (end-start))

逗逼小龙

新手学习  很多地方很幼稚
答案  402

# -*- coding: utf-8 -*-
import math
import time
start=time.clock()
list2=[]
list3=[]
list4=[]
def fen_2(m):
    list1=[]
    list2.append(m)
    for n in str(m) :
        n=int(n)
        list1.append(math.factorial(n))
    if len(list2)!=len(set(list2)):
        list2.pop()
        return len(list2)
    return  fen_2(sum(list1))
def fen(x):
    global list2
    list2 =[]
    return(fen_2(x))
for i in range(1,1000000):
    if fen(i)>=60:
        list3.append(i)
print(len(list3) )
for i in list3:
    fen(i)
    list4.extend(list(set(list2)&set(list3 )))
print(list4 == list3)
end=time.clock()
print('运行耗时:%f'%(end-start ))

芒果加黄桃

# encoding:utf-8
# 寻找100万以下60项的阶乘链  145 = 1！+2！+3！
from time import time
from math import factorial

def getFac(n):
    result = 0
    while n >= 10:
        result += factorial(n % 10)
        n = n // 10
    return result + factorial(n)

def euler072(N=100):
    d_facs = {}
    s_facs = set()
    count = 0
    for n in range(1, 1000001):
        if str(sorted(str(n))) in s_facs:
            count+=1
        else:
            l_tmp = [n]
            tmp,k = 0,n
            while True:
                tmp = getFac(k);
                if tmp not in l_tmp:
                    l_tmp.append(tmp)
                    k = tmp
                else:
                    break 
            if len(l_tmp)>=60:
                count+=1
                d_facs[str(sorted(str(n)))] = l_tmp
    print(count)    
    
if __name__ == '__main__':
    start = time() 
    euler072()
    print('cost %.6f sec' % (time() - start))

402
cost 62.502249 sec

najin

用了新解法：
程序是matlab
结果是
   402

时间已过 0.771700 秒。
>>

wyp02033

from time import perf_counter


def factorial(n):
    if n == 0 or n == 1:
        return 1
    else:
        return n * factorial(n-1)

def generate_unrepetition_link(n):
    unrepetition_link = [n]
    num_str = str(n)
    while True:
        sum_ = 0
        for each in num_str:
            sum_ += factorial(int(each))
        if sum_ not in unrepetition_link:
            unrepetition_link.append(sum_)
            num_str = str(sum_)
        else:
            break
    return unrepetition_link
def main():
    n = 0
    for i in range(5, 1000000):
        if len(generate_unrepetition_link(i)) == 60:
            n += 1
    print(n)


if __name__ == '__main__':
    start = perf_counter()
    main()
    end = perf_counter()
    print("time uesd:", end - start)

结果：
402
time uesd: 103.1872067770146s

永恒的蓝色梦想

记录下思路,以后再写
0.出现过的不重复计算

debuggerzh

402

Process returned 0 (0x0)   execution time : 0.219 s
Press any key to continue.
动态规划+记忆化搜索
设f(x)为x各位数阶乘之和
设集合

                               
登录/注册后可看大图

设len(x)为以x开始的链的不重复项数，则状态转移方程

                               
登录/注册后可看大图

#include<iostream>
#include<algorithm>
using namespace std;

const int f[] = {1,1,2,6,24,120,720,5040,40320,362880};

const int len3[] = {169,1454,363601};
const int len2[] = {871,872,45361,45362};
const int len1[] = {0,1,2,145,40585};

const int M = 1e6;
int dp[M*10] = {0};
int mx = 0;

int f_sum(int x){
  int res = 0;
  if (x == 0) return 1;
  while(x){
    res += f[x % 10];
    x /= 10;
  }
  return res;
}

int len(int x){
  //mx = max(mx,x);
  int & ans = dp[x];
  if (ans)  return ans;

  if (find(len3,len3 +3,x) != len3 +3)  return ans = 3;
  if (find(len2,len2 +4,x) != len2 +4)  return ans = 2;
  if (find(len1,len1 +5,x) != len1 +5)  return ans = 1;

  return ans = len(f_sum(x)) + 1;
}

int main(){
  int cnt = 0;
  for (int i = 0;i <= M;i++)
    if (len(i) == 60) ++cnt;

  //cout << mx << endl;
  cout << cnt << endl;
  return 0;
}

guosl

/*
答案：402
耗时：4.07265秒（单核）
      0.658726秒（六核）
*/
#include <iostream>
#include <unordered_set>
#include <omp.h>
using namespace std;

const int f[] = { 1,1,2,6,24,120,720,5040,40320,362880 };

int GetFS(int n)
{
  int nS = 0;
  while (n > 0)
  {
    nS += f[n % 10];
    n /= 10;
  }
  return nS;
}

int main(void)
{
  double t = omp_get_wtime();
  int nCount = 0;
  unordered_set<long long> us;
#pragma omp parallel for private(us) reduction(+:nCount)
  for (int i = 1; i <= 1000000; ++i)
  {
    us.clear();
    int k = i;
    while (true)
    {
      auto itr = us.find(k);
      if (itr != us.end())
        break;
      us.insert(k);
      k = GetFS(k);
    }
    if (us.size() >= 60)
      ++nCount;
  }
  t = omp_get_wtime() - t;
  cout << nCount << endl << t << endl;
  return 0;
}

TLM

储存计算过的数值，阶乘也提前算好
402
Time:1.909942865371704s

import time
st=time.time()
n=1000000
# 获取阶乘数列
jiecheng=[1]
for i in range(1,10):
    jiecheng.append(jiecheng[-1]*i)
# 创建dict()
data=dict()
def getl(n):
    if n in data:
        return data[n]
    data2=dict()
    nn=n
    u=0
    while nn not in data2:
        num=0
        ii=nn
        while ii>0:
            num=jiecheng[ii%10]+num
            ii=ii//10
        data2[nn]=len(data2)+1
        nn=num
        if nn in data:
            u=data[nn]-1
            data2[nn]=len(data2)+1
            break
    for j in data2:
        if data2[j]>=data2[nn]:
            data[j]=len(data2)+1-data2[nn]+u
        else:
            data[j]=len(data2)+1-data2[j]+u
    return data[n]
numsum=0
for i in range(69,n+1):
    # print(getl(i))
    if getl(i)>=60:
        numsum=numsum+1
print(numsum)
# print(data)
print('Time:{}s'.format(time.time()-st))