-
Notifications
You must be signed in to change notification settings - Fork 0
/
euler34.py
130 lines (110 loc) · 2.41 KB
/
euler34.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
"""Euler 34: Sum of Factorials of their Digits
trying the same thing as 30, 5th powers.
wtf? I only come up with 1, 2, and 145. 1 & 2 are dq'd for not being sums,
and 145 was their example. I put in 145 and they say no. Tried everything up
to 5 million.
"""
def fact(n):
f=1
while n>1:
f*=n
n-=1
return f
# make a lookup
facts={0:1,1:1}
for i in range(2,10):
facts[i]=fact(i)
# brute force forward test
def facttest(n,m):
res=[]
for i in range(n,m):
facttot=0
maybe=True
for digit in str(i):
facttot+=facts[int(digit)]
if facttot>i:
maybe=False
break
if maybe and facttot==i:
res.append(i)
return res
# revised brute force forward test
def factzeros(n,m):
res=[]
for i in range(n,m):
facttot=0
for digit in str(i):
facttot+=facts[int(digit)]
if int(str(facttot).replace('0',''))==i:
res.append(i)
return res
"""
ok, so checking with forward tests I'm being redundant. I only need to check
each combination of digits and see if the sum of their factorials without its
zeroes returns the same set.
two digits could be done bluntly in a test with two for loops, three with three.
i could keep a running array of known things, then append.
"""
dig=['1','2','3','4','5','6','7','8','9']
def testset(test):
testres=[]
for i in test:
# print "testing " + i
ilist=list(i)
ilist.sort()
facttot=0
for digit in str(i):
facttot+=facts[int(digit)]
l=list(str(facttot).replace('0',''))
l.sort()
if ''.join(l)==''.join(ilist):
print "matched "+ i
testres.append(i)
return testres
def iterset(old):
# print 'iterating set'
new=[]
for elementi in ['1','2','3','4','5','6','7','8','9']:
for elementj in old:
new.append(elementi+elementj)
return new
#res=[]
#for i in range(0,7):
# res+=testset(dig)
# dig=iterset(dig)
# print res
"""
This is still brute force. How can I narrow down the set of numbers that
could petentially be the sums of the factorials of their digits?
"""
"""
the set of digit factorials establishes a set similar to prime factorials.
There was something about this in number theory, I'm sure of it. Given two numbers,
what other numbers can be made out of combinations of them?
0=1
1=1
2=2
3=6
4=24
5=120
6=720
7=5040
8=40320
9=362880
edit: shit, zero factorial = 1. I think I did a lot of previous stuff here assuming
it was zero.
wtf.
40585 is the only other one.
"""
# array of digit factorials:
df=[1
,1
,2
,6
,24
,120
,720
,5040
,40320
,362880
]