-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy patheuler_171.py
executable file
·150 lines (127 loc) · 5.83 KB
/
euler_171.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
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
#!/usr/bin/python
# Project euler #171
# find last 9 digits of the sum of all numbers 0<n<10^20 such that the
# sum of digits squared is a perfect square
#
# since we're summing over the last 9 digits, it's fruitful
# to divide the problem into two parts. First count the multiplicities
# in the first 11 digits, second find the possible 9 digit numbers which
# when added to a combination of the first 11 digits produces a perfect
# square. the total sum is then the multiplicity of that combination
# times the sum of the possible 9 digit numbers.
#
# It is possible to write an algorithm that efficiently does both parts. We
# store the 9-digit sums and their multiplicities in two dictionaries with keys
# corresponding to the the sum of squares of digits. The mult-dictionary can then
# be used to caculate teh 11-digit multiplicities, and the sum-dictionary gives us
# all 9-digit sums
# Currently only implemented to count sum_digits across a total of 2(sum_digits)+2
# digits. Runs faster this way
# answer: 142989277
import timeit
class Euler171:
def __init__(self, sum_digits=9):
# number of digits we're concerned with
self.n_digits = 2*sum_digits+2
# sum over only the last sum_digits
self.sum_digits = sum_digits
# the max that the first 10 digits can add up to
self.max_count_int = 81*(self.n_digits-self.sum_digits)
# a list of single digit squares [0..81]
self.single_digit_squares = self.possibleperfectsquares(1)
# create lookup dictionary for digit squared
# with strings as keys and dict for keeping trakc of the differences
# this will ensure we don't have to loop through every
# number, just add from lookup-dict
self.squares_lookup_dict = {}
for i in range(10):
self.squares_lookup_dict[str(i)] = i**2
self.squares_diff_dict = {}
self.squares_diff_dict['0'] = 0
for i in range(1, 10):
self.squares_diff_dict[i] = 2*i-1
self.two_digit_squares_dict = dict.fromkeys(range(81*2+1), 0)
for i in range(10**2):
a_square = self.sum_digits_squared(str(i))
self.two_digit_squares_dict[a_square] +=1
# perf_square targets we want to hit
self.perf_squares = self.possibleperfectsquares(self.n_digits)
# keep track of the sum of the last 9 digits
self.sum_psquared = 0
# keep track of the multiplicity of the first 10 digits
self.count = 0
# dict to keep track of count
self.count_dict = {}
# keep track of the total sum across all different possible
# combinations of multiplicities
self.sum_total = 0
# keep track of sums already calculated
self.sum_dict = dict.fromkeys(range(81*self.sum_digits+1), 0)
self.sum_multiplicity_dict = dict.fromkeys(range(81*self.sum_digits+1), 0)
def possibleperfectsquares(self, n):
''' given n where n is the maximum number of digits, return
a list of possible perfect squares
'''
psquare = []
curr = 0
while curr**2 <= (9**2)*n:
psquare.append(curr**2)
curr+=1
return psquare
def sum_digits_squared(self, str_i):
sum_of_squares = 0
for digit in str_i:
sum_of_squares += self.squares_lookup_dict[digit]
return sum_of_squares
def create_sum_dict(self):
split = self.sum_digits/2
for j in range(10**split):
subrange_min = j * 10**(self.sum_digits-split)
subrange_max = (j+1) * 10**(self.sum_digits-split)
print 'range', j, 'out of', 10**split
print 'subranges', subrange_min, subrange_max
sum_of_squares = 0
for i in range(subrange_min, subrange_max):
# need to recalculate the sum of digits squared
# every ten increments
if i % 10 == 0:
iteration = 0
str_i = str(i)
sum_of_squares = self.sum_digits_squared(str_i)
else:
iteration += 1
sum_of_squares += self.squares_diff_dict[iteration]
self.sum_dict[sum_of_squares] += i
# self.sum_dict[sum_of_squares] %= 10**self.sum_digits
self.sum_multiplicity_dict[sum_of_squares] +=1
def count_psquaredigits(self, num):
for a_square, multi in self.two_digit_squares_dict.iteritems():
if num < a_square:
# break out of loop if num-a_square < 0
break
if self.sum_multiplicity_dict.has_key(num-a_square):
self.count+=self.sum_multiplicity_dict[num-a_square]*multi
def create_count_dict(self):
if not self.sum_multiplicity_dict[0]:
self.create_sum_dict()
for i in range(self.max_count_int+1):
self.count = 0
self.count_psquaredigits(i)
# print i, self.count
self.count_dict[i] = self.count
def main(self):
self.create_count_dict()
for a_square in self.perf_squares:
for i in range(a_square+1):
if not self.count_dict.has_key(i):
continue
elif not self.sum_dict.has_key(a_square-i):
continue
multiplicity = self.count_dict[i]
this_sum = self.sum_dict[a_square-i]
# print 'square', a_square
# print 'first sum', i, 'last sum', a_square - i
# print 'multiplicity', multiplicity, 'sum', this_sum
self.sum_total += (multiplicity * this_sum)
# self.sum_total %= 10**(self.sum_digits)
print 'current square', a_square, 'sum_total', self.sum_total