Solution to Prob #38
The problem statement is here. I spent some time thinking the best way to exit the brute force loop. I still don’t claim to have gotten it right, but this one is atleast not too slow and gets the right answer.
def list_to_number(l) :
r = 0
for i in l :
r *= 10
r += i
return r
def number_to_list(n) :
r = []
while n :
r.insert(0, n%10)
n /= 10
return r
def is_1to9_pandigital(l) :
if len(l) 9 :
return False
for i in range(1, 10) :
if i not in l :
return False
return True
def get_next_seed(s) :
seed = s + 1
while seed 9999 :
return -1
return seed
if __name__ == '__main__' :
seed = 1
pans = 0
while True :
pandigital = []
n = 1
while True :
p = seed * n
pl = number_to_list(p)
fail = False
for l in pl :
if l in pandigital :
fail = True
break
if fail :
break
pandigital.extend(pl)
if is_1to9_pandigital(pandigital) :
pd = list_to_number(pandigital)
if pd >= pans :
pans = pd
print "Current Pandigital is ", pd
print seed, n
fail = True
break
n += 1
digits_left = []
for i in range(1, 10) :
if i not in pandigital :
digits_left.append(i)
digits_left.sort(reverse=True)
if n*seed > list_to_number(digits_left) :
break
seed = get_next_seed(seed)
if seed == -1 :
break
print "Exhausted!"
I will upload this into the bitbucket repo real soon 
Project Euler Solutions on Bitbucket
I am finally adding my solutions to a repository for better access and managing changes and/or incorporating suggestions. I have a dormant bitbucket account and since it is recently in news, I decided to make something out of the account 
My bitbucket url.
Solution to Prob #44
The problem statement is here. I solved this problem a couple of days back trying to use lists and minimize the number of computations. Eventually, i found that the list could be a tad more expensive than the computation . Here is my final version of the solution, faster than I expected!
from math import sqrt
pentagonal = lambda n: n*((3*n)-1)/2
def is_pentagonal(num) :
if num == 0 :
return False
n = int((1 + sqrt((1 + (24*num))))/6)
return pentagonal(n) == num
# 1560090 7042750
#
if __name__ == '__main__' :
max = 10
done = False
while not done:
for i in xrange(2, max) :
pi = pentagonal(i)
for j in xrange(2, max) :
pj = pentagonal(j)
if not is_pentagonal(pi+pj) :
continue
if is_pentagonal(abs(pi-pj)) :
print pi, pj
done = True
break
if done :
break
max += 10
Some of this has no explanation:
Why am I moving in steps of 10?
No logic there, just happen to like ten.
How does this guarantee that the difference is minimal?
Well, I dunno. I did not even see if there are other numbers
Solution to Prob #125
The problem is stated here. My solution in python is here:
from math import sqrt
sqr = lambda n: n*n
def reverse(num) :
rev = 0
while num :
rev = (rev*10) + num%10
num /= 10
return rev
def is_sum_of_squares(num) :
for seed in xrange(int(sqrt(num))) :
sum = 0
agg = seed
while sum<num :
sum += sqr(agg)
if sum == num and agg seed :
return True
agg += 1
return False
if __name__ == '__main__' :
sum = 0
for i in xrange(2,100000000) :
if i == reverse(i) :
if is_sum_of_squares(i) :
sum += i
print sum
Takes way too long to complete. Quite literally had lunch by the time this completed
Solution to Prob #92
The problem is stated here. My solution in python is here. Takes a while to complete, though. I really need to start practicing threaded programming and/or parallel stuff in python. This one may also be a good case for parallel programming. My solution:
if __name__ == '__main__' :
eighty9s = 0
for i in xrange(2,10000000) :
seed = i
while 1 :
if seed in (1,89) :
break
s_i = seed
n_seed = 0
while s_i :
n = s_i % 10
s_i /= 10
n_seed += n*n
seed = n_seed
if seed == 89 :
eighty9s += 1
print eighty9s
Solution to Prob #46
The problem is defined here. Quite a simple one and the solution in python is :
from math import sqrt
def is_prime(num) :
if num == 1 :
return False
for i in range(2, int(sqrt(num))+1) :
if not num%i:
return False
return True
if __name__ == '__main__' :
seed = 3
primes = [2]
while 1:
if is_prime(seed) :
primes.append(seed)
seed += 2
continue
# composite. good.
fail = False
for prime in primes :
seed_1 = seed - prime
seed_2 = seed_1 / 2
seed_3 = sqrt(seed_2)
seed_4 = int(seed_3)
if seed_4*seed_4 == seed_2 :
fail = True
break
if fail :
seed += 2
else :
print seed
break
Solution to Prob #33
The problem is defined here. Another quite a tricky problem. Works, but the solution looks very ugly 
Anyway, my solution in python is :
if __name__ == '__main__' :
pair = [1,1]
for nr in range(10, 100) :
nr_t = nr/10
nr_o = nr%10
if not nr_o :
continue
for dr in range(nr, 100) :
dr_t = dr/10
dr_o = dr%10
ndr = 100
nnr = 100
common = None
if dr_t not in (nr_t, nr_o) and dr_o in (nr_t, nr_o) :
ndr = dr_t
common = dr_o
elif dr_t in (nr_t, nr_o) and dr_o not in (nr_t, nr_o) :
ndr = dr_o
common = dr_t
else :
continue
if nr_t == common:
nnr = nr_o
else :
nnr = nr_t
if ndr and (nr*1.0)/dr == (nnr*1.0)/ndr :
pair[0] *= nr
pair[1] *= dr
print pair, pair[1]/pair[0]
Solution to Prob #37
The problem is defined here. Tricky one there and it took this link to realize that 1 is not considered prime . Anyway, my solution in python is:
from math import sqrt, log
def is_prime(num) :
if num == 1 :
return False
for i in range(2, int(sqrt(num))+1) :
if not num%i:
return False
return True
def l2r_list(num) :
retlist = []
n = num
while n > 9 :
n %= pow(10, int(log(n,10)))
retlist.append(n)
return retlist
def r2l_list(num) :
retlist = []
n = num
while n:
n /= 10
retlist.append(n)
return retlist
def truncatable(num, r2l=False, l2r=False) :
if r2l :
l_r2l = r2l_list(num)
for n in l_r2l :
if not is_prime(n) :
return False
return True
elif l2r :
l_l2r = l2r_list(num)
for n in l_l2r :
if not is_prime(n) :
return False
return True
return False
if __name__ == '__main__' :
print is_prime(1)
t_primes = []
for i in range(10, 999999) :
if is_prime(i) :
if truncatable(i, l2r=True) and truncatable(i, r2l=True) :
t_primes.append(i)
print len(t_primes), sum(t_primes)
I know what you are thinking! Many of those functions are redundant and useless. I wrote them trying to do half a dozen other things without realizing 1 is not prime. Works, nevertheless
Solution to Prob #56
Another easy problem, at least to solve using python. The statement of the problem is given here. My solution in python is here.
from string import atoi
def digital_sum(num) :
return sum(map(atoi, list(str(num))))
if __name__ == '__main__' :
max_sum = 0
for a in range(1,100) :
for b in range(1, 100) :
dsum = digital_sum(pow(a, b))
if dsum > max_sum :
max_sum = dsum
print max_sum
Solution to Prob #55
The problem is stated here. One of the more simpler problems to solve in python and worked quite fast too. Here is the python code that gets it right
def is_palindrome(num) :
l_num = list(str(num))
l_num.reverse()
return num == atoi("".join(l_num))
def reverse(num) :
s_num = str(num)
l_num = list(str(num))
l_num.reverse()
return atoi("".join(l_num))
def is_lycherel(num, count=0) :
if (count < 50) :
n = num + reverse(num)
if is_palindrome(n) :
return False
return is_lycherel(n, count+1)
else :
return True
if __name__ == '__main__' :
lycherel_nums = []
for no in range(10, 10000) :
if(is_lycherel(no)) :
lycherel_nums.append(no)
print len(lycherel_nums)
