Sum Of Squares Of Divisors Is Square

May 24, 2019

A few days ago I answered this question on Stack Overflow:

Divisors of 42 are : 1, 2, 3, 6, 7, 14, 21, 42. These divisors squared are: 1, 4, 9, 36, 49, 196, 441, 1764. The sum of the squared divisors is 2500 which is 50 * 50, a square!

Given two integers m, n (1 ≤ mn) we want to find all integers between m and n whose sum of squared divisors is itself a square. 42 is such a number.

The result will be an array of arrays, each subarray having two elements, first the number whose squared divisors is a square and then the sum of the squared divisors.

Your task is to solve MrOldSir’s problem; he asked for a solution in Python, but you are free to use any language. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

2 Responses to “Sum Of Squares Of Divisors Is Square”

  1. Zack said

    Nice one. Here is my take in Julia (1.0):

    function IsSquare(x::Int64)
    sr = sqrt(x)
    return round(sr)^2 == x
    end

    function FindDivisors(x::Int64)
    d = falses(x)
    d[1] = d[end] = true
    z = div(x, 2)

    if 2*z == x
        d[2] = d[z] = true
    end
    
    for i = 3:(z-1)
        z = div(x, i)
        if i*z == x; d[i] = d[z] = true; end
    end
    
    temp = (1:x).*d
    return temp[temp.>0]
    

    end

    function test(x::Int64)
    d = FindDivisors(x)
    n = length(d)

    for i = 1:n
        d[i] *= d[i]
    end
    
    s = sum(d)
    return IsSquare(s), s
    

    end

    function main(m::Int64, n::Int64)
    d = n – m + 1
    Q = Array{Array{Int64, 1}}(undef, d)
    c = 0

    for x = m:n
        y, z = test(x)
    
        if y
            c += 1
            Q[c] = [x, z]
        end
    end
    
    return Q[1:c]
    

    end

    Example:
    julia> main(1,1000)
    5-element Array{Array{Int64,1},1}:
    [1, 1]
    [42, 2500]
    [246, 84100]
    [287, 84100]
    [728, 722500]

    The functions could use some optimization, but for small numbers the performance is decent. Cheers

  2. Milbrae said

    Some Pari/GP

    sosodis(m, n) = for (x = m, n, s = sigma(x, 2); if (issquare(s), print ("(", x, ", ", s, ")")))
    print (sosodis(1, 1000))

    Output is just like Zack’s

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: