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 ≤ m ≤ n) 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.

Posted by programmingpraxis

Filed in Exercises

2 Comments »

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

Zack said
May 29, 2019 at 2:45 PM
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

Milbrae said

May 29, 2019 at 3:59 PM

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

Enter your comment here...

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

Email (required) (Address never made public)

Name (required)

Website

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

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

Cancel

Connecting to %s

Programming Praxis