Return to Question

I've recently came across an interesting paper : ON FINITE SUMS OF RECIPROCALS OF DISTINCT n-th POWERS by R. L. GRAHAM. At the end of the paper he gives some exemples: $$ \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:

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:

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.

I've tried James Arathoon solution and it works well. Here is the full python code if you are interested:

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

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

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.

I've tried James Arathoon solution and it works well. Here is the full python code if you are interested:

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]