论坛 › 欧拉计划（Project Euler） › 题目74：包含60个不重复项的阶乘链有多少个？

欧拉计划 发表于 2015-11-5 17:01:25

题目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 发表于 2016-10-16 15:58:32

进度：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 =
    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))

逗逼小龙 发表于 2017-2-5 21:27:19

新手学习很多地方很幼稚
答案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)
    returnfen_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 ))

芒果加黄桃 发表于 2017-2-16 15:44:48

# 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 =
            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 = l_tmp
    print(count)   
   
if __name__ == '__main__':
    start = time()
    euler072()
    print('cost %.6f sec' % (time() - start))

402
cost 62.502249 sec

najin 发表于 2017-10-14 21:35:38

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

时间已过 0.771700 秒。
>>

wyp02033 发表于 2018-3-12 22:42:24

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 =
    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

永恒的蓝色梦想 发表于 2019-8-1 14:37:11

本帖最后由 永恒的蓝色梦想 于 2021-1-7 20:10 编辑

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

debuggerzh 发表于 2020-8-30 10:57:55

402

Process returned 0 (0x0)   execution time : 0.219 s
Press any key to continue.
动态规划+记忆化搜索
设f(x)为x各位数阶乘之和
设集合https://wx1.sinaimg.cn/mw690/0081qlg6ly1gi8nir7wk8j30o7013wec.jpg
设len(x)为以x开始的链的不重复项数，则状态转移方程https://wx3.sinaimg.cn/mw690/0081qlg6ly1gi8nir7vsnj30ba03lwed.jpg
#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 = {0};
int mx = 0;

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

int len(int x){
//mx = max(mx,x);
int & ans = dp;
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 发表于 2022-1-12 16:38:52

/*
答案：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;
}
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 发表于 2023-3-1 10:02:01

本帖最后由 TLM 于 2023-3-1 10:03 编辑

储存计算过的数值，阶乘也提前算好
402
Time:1.909942865371704s
import time
st=time.time()
n=1000000
# 获取阶乘数列
jiecheng=
for i in range(1,10):
    jiecheng.append(jiecheng[-1]*i)
# 创建dict()
data=dict()
def getl(n):
    if n in data:
      return data
    data2=dict()
    nn=n
    u=0
    while nn not in data2:
      num=0
      ii=nn
      while ii>0:
            num=jiecheng+num
            ii=ii//10
      data2=len(data2)+1
      nn=num
      if nn in data:
            u=data-1
            data2=len(data2)+1
            break
    for j in data2:
      if data2>=data2:
            data=len(data2)+1-data2+u
      else:
            data=len(data2)+1-data2+u
    return data
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))

查看完整版本: 题目74：包含60个不重复项的阶乘链有多少个？