## Aug 17, 2013

### Project Euler Problem Nos 43

Original problem posted at:

http://projecteuler.net/problem=43

This is my solution to problem 43:

#!/usr/bin/python

### problem 43

import string

def get_divisible_set(n):
myset=[]
for i in range(2,999):
if (i%n==0):
myset.append(str(i).zfill(3))
###myset.append(str.format("%03d", i))
###n = '4'
###>>> print n.zfill(3)
###>>> '004'
return myset

if ((a[1]==b[0])and(a[2]==b[1])):
return 1
else:
return 0

myset=[]
#### assuming setb is the smaller set....
mylenb=len(setb)
mylena=len(seta)
for i in range(mylenb):
for j in range(mylena):
###print seta[j], setb[i]
mysettmp=set(seta[j])
mysettmp=mysettmp.union(set(setb[i]))
myset.append((seta[j],setb[i]))
return myset

myset17=get_divisible_set(17)
myset13=get_divisible_set(13)
myset11=get_divisible_set(11)

nextset=[]
for i in range(len(myset)):
#print myset[i]
(a,b)=myset[i]
tmp=[]
mysettmp=set()
tmp.append(a)
if len(tmpset)>0:
for j in range(len(tmpset)):
(c,d)=tmpset[j]
mysettmp=set(d)
mysettmp=mysettmp.union(set(c))
mysettmp=mysettmp.union(set(a))
mysettmp=mysettmp.union(set(b))
if len(mysettmp)==5:
nextset.append((c,a,b))

print "aaaa"
print nextset

myset7=get_divisible_set(7)

nextset1=[]

for i in range(len(nextset)):
(a,b,c)=nextset[i]
tmp=[]
mysettmp=set()
tmp.append(a)
if len(tmpset)>0:
for j in range(len(tmpset)):
(d,e)=tmpset[j]
mysettmp=set(e)
mysettmp=mysettmp.union(set(d))
mysettmp=mysettmp.union(set(a))
mysettmp=mysettmp.union(set(b))
mysettmp=mysettmp.union(set(c))
if len(mysettmp)==6:
nextset1.append((d,e,b,c))

print "bbb"
print nextset1

myset5=get_divisible_set(5)

nextset2=[]

for i in range(len(nextset1)):
(a,b,c,d)=nextset1[i]
tmp=[]
mysettmp=set()
tmp.append(a)
if len(tmpset)>0:
for j in range(len(tmpset)):
(e,f)=tmpset[j]
mysettmp=set(f)
mysettmp=mysettmp.union(set(e))
mysettmp=mysettmp.union(set(a))
mysettmp=mysettmp.union(set(b))
mysettmp=mysettmp.union(set(c))
mysettmp=mysettmp.union(set(d))
if len(mysettmp)==7:
nextset2.append((e,a,b,c,d))

print "bbb"
print nextset2

myset3=get_divisible_set(3)

nextset3=[]

for i in range(len(nextset2)):
(a,b,c,d,e)=nextset2[i]
tmp=[]
mysettmp=set()
tmp.append(a)
if len(tmpset)>0:
for j in range(len(tmpset)):
(f,g)=tmpset[j]
mysettmp=set(g)
mysettmp=mysettmp.union(set(f))
mysettmp=mysettmp.union(set(a))
mysettmp=mysettmp.union(set(b))
mysettmp=mysettmp.union(set(c))
mysettmp=mysettmp.union(set(d))
mysettmp=mysettmp.union(set(e))
if len(mysettmp)==8:
nextset3.append((f,a,b,c,d,e))

myset2=get_divisible_set(2)

nextset4=[]

for i in range(len(nextset3)):
(a,b,c,d,e,f)=nextset3[i]
tmp=[]
mysettmp=set()
tmp.append(a)
if len(tmpset)>0:
for j in range(len(tmpset)):
(g,h)=tmpset[j]
mysettmp=set(h)
mysettmp=mysettmp.union(set(g))
mysettmp=mysettmp.union(set(a))
mysettmp=mysettmp.union(set(b))
mysettmp=mysettmp.union(set(c))
mysettmp=mysettmp.union(set(d))
mysettmp=mysettmp.union(set(e))
mysettmp=mysettmp.union(set(f))
if len(mysettmp)==9:
nextset4.append((g,a,b,c,d,e,f))

print "final ans"
print nextset4

Output from the python script:

[('160', '603', '035', '357', '572', '728', '289'), ('460', '603', '035', '357', '572', '728', '289'), ('106', '063', '635', '357', '572', '728', '289'), ('406', '063', '635', '357', '572', '728', '289'), ('130', '309', '095', '952', '528', '286', '867'), ('430', '309', '095', '952', '528', '286', '867')]

Or after rearranging the digits according to the rules in problem 43:

4160357289
1460357289
4106357289
1406357289
4130952867
1430952867

These are the six numbers that satisfy all the properties and will add up to the answer.