I've found this result : $$ \frac{1}2 = \frac1{2^2}+\frac1{3^2}+\frac1{4^2}+\frac1{5^2}+\frac1{6^2}+\frac1{15^2}+\frac1{18^2}+\frac1{36^2}+\frac1{60^2}+\frac1{180^2}$$ I've tried my best to make a program to find that result but i can't find a solution. I found this solution to an easier problem : the representation of a fraction as the sum of distinct reciprocals. I tried to expend this algorithm to solve my problem but when i execute my program the numbers given get too large:
def pgcd(a,b):
return a if b==0 else pgcd(b,a%b)
def subFrac(p1,q1,p2,q2):
u,v=p1*q2-p2*q1,q1*q2
d=pgcd(u,v)
return (u//d,v//d)
def dec(p,q):
print(p,q)
frac=[]
k=2
while p>0:
while 1/(k**2)>p/q:
k+=1
p,q=subFrac(p,q,1,k**2)
print(k,p,q)
frac.append(k)
k+=1
return frac
Gives : $$ \frac{1}2 = \frac1{2^2}+\frac1{3^2}+\frac1{4^2}+\frac1{5^2}+\frac1{6^2}+\frac1{11^2}+\frac1{54^2}+\frac1{519^2}+\frac1{59429^2}+...$$ In general, I'd like to make a program that gives a representation with reasonable number like the one given or this one from proofWiki: $$ \frac{1}2 = \frac1{2^2}+\frac1{3^2}+\frac1{4^2}+\frac1{5^2}+\frac1{7^2}+\frac1{12^2}+\frac1{15^2}+\frac1{20^2}+\frac1{28^2}+\frac1{35^2}$$ Thanks in advance!
EDIT:
Thanks for your answers. I looked into the problem 152 of Euler project and I saw that they mostly brute force to find solutions and try to reduce the initial list size using math. I will probably try this later. Here is a link to a solution (not mine) written in C++ and here in python.
I've tried James Arathoon solution and it works well. Here is the full python code if you are interested ( to find combinations i used a method which works but i think using a recursive function like they do in most project Euler 152 solutions is better ):
import numpy.polynomial.polynomial as nppol # To make the variable you called list
# Useful function, i could use already existing module
def Divisors(k):
l=[]
for ii in range(1,k+1):
if k%ii==0:
l.append(ii)
return l
def pgcd(a,b):
return a if b==0 else pgcd(b,a%b)
def addFrac(p1,q1,p2,q2):
assert q1!=0 and q2!=0
u,v=p1*q2+p2*q1,q1*q2
d=pgcd(u,v)
return (u//d,v//d)
def subFrac(p1,q1,p2,q2):
u,v=p1*q2-p2*q1,q1*q2
d=pgcd(u,v)
return (u//d,v//d)
# The interesting part
def test(alist, frac):
for i in alist:
testDivisors=Divisors(i)
testDivisorsSq=[k*k for k in testDivisors]
prod=[1] # Its a polynomial
for j in testDivisorsSq:
prod=nppol.polymul(prod,[1]+(j-1)*[0]+[1])
llist=[k for k in range(len(prod)) if prod[k]!=0]
totalInvTestDivisorsSq=(0,1)
for k in testDivisorsSq[1:]: # Remove 1 which is always the first element of TestDivisorsSq
totalInvTestDivisorsSq=addFrac(*totalInvTestDivisorsSq,1,k)
totalInvTestDivisorsSq=subFrac(*totalInvTestDivisorsSq,*frac)
testnum=testDivisorsSq[-1]/totalInvTestDivisorsSq[1]*totalInvTestDivisorsSq[0]
if testnum in llist:
print("Possible Solutions : ")
print(i," ",testDivisorsSq," ",testnum) # Max(Divisors(i))=i always and no need to reverse the list
# Find all the correct combination that add up to testnum
l=len(testDivisorsSq)
for j in range(1,2**l):
auth=("0"*l+bin(j)[2:])[-l:]
s=0
k=0
while s<=testnum and k<l:
if auth[k]=="1":
s+=testDivisorsSq[k]
k+=1
if s==testnum:
print("Find a combination : ",[testDivisorsSq[k] for k in range(1,l) if auth[l-1-k]=="0"])
# its l-1-k because its reversed
test([1,2,6,12,18,30,36,60,90,120,150,180],(1,2))
# It took a few seconds to run this program
It gives :
Possible Solutions :
120 [1, 4, 9, 16, 25, 36, 64, 100, 144, 225, 400, 576, 900, 1600, 3600, 14400] 500.0
Find a combination : [4, 9, 16, 25, 64, 100, 225, 400, 576, 900, 1600, 3600, 14400]
Find a combination : [4, 9, 16, 25, 64, 100, 144, 576, 900, 1600, 3600, 14400]
Possible Solutions :
180 [1, 4, 9, 16, 25, 36, 81, 100, 144, 225, 324, 400, 900, 1296, 2025, 3600, 8100, 32400] 1086.0
Find a combination : [4, 9, 16, 25, 81, 100, 144, 225, 400, 8100, 32400]
Find a combination : [4, 9, 16, 25, 36, 225, 324, 1296, 3600, 32400]
Find a combination : [4, 9, 16, 25, 36, 225, 400, 1296, 2025, 3600, 8100]
Find a combination : [4, 9, 16, 25, 36, 144, 1296, 2025, 3600, 8100]
Find a combination : [4, 9, 16, 25, 81, 100, 144, 324, 400, 900, 3600, 8100]
Find a combination : [4, 9, 16, 25, 81, 100, 144, 225, 900, 1296, 2025, 3600]