# Ruby function to find numbers whose sum of squares of divisors is a perfect square

I am doing a problem my buddy gave to me and I have my solution which works but needs to be optimised. I have tried to optimise it as much as I can with my knowledge but it seems there is still room for improvement. I am trying to improve my ruby. Here is the challenge:

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.

 def list_squared(m, n)
array = []
(m..n).to_a.each do |i|
q =  (1..i/2).to_a.push(i).map {|x| x**2 if i % x == 0 }.compact.reduce(:+)
array << [i, q] if Math.sqrt(q) % 1 == 0
end
array
end


This works but apparently is inefficient. Could someone point me in the right direction. I am assuming its the "map" but I initially had:

def list_squared(m, n)
array = []
(m..n).to_a.each do |i|
q =  (1..i/2).to_a.select {|x| i % x == 0 }.push(i).map { |x| x**2 }.reduce(:+)
array << [i, q] if Math.sqrt(q) % 1 == 0
end
array
end

• Consider (m..n).to_a.each. What happens if it evaluates to (0..1_000_000_000).to_a...? You've unnecessarily used a huge amount of memory where you could have iterated directly using each. – the Tin Man Oct 3 '16 at 16:00
• Thanks Tin man. I made that change...its still taking over 8 secs to evaluate which is "considered" unacceptable by the challenge. I could look at the solutions but to do so, would mean I get no credit – GhostRider Oct 3 '16 at 16:02
• What are you using for m and n? Just to have the same test case. – slowjack2k Oct 4 '16 at 10:57
• That's a fair question that I should have explained. My code is put through a number of test cases (15) but I'm being told although it passes, my code is inefficient (too slow). – GhostRider Oct 4 '16 at 11:00
• Sounds like a test from codility. – slowjack2k Oct 4 '16 at 11:14

You don't need to call to_a. Ranges are directly Enumerable.

Divisors always occur in pairs. You don't need to test (1..i/2); you only need to go up to $\sqrt{i}$.

For fast performance, though, you would need a solution based on number theory rather than brute-force enumeration.

Approach your divisors smarter. They are always smaller than root of n, and come in pairs.

 divisors = []
(1..(i**0.5)).each do |potential_divisor|
if i % potential_divisor == 0
divisors << potential_divisor
divisors << i/potential_divisor unless i/potential_divisor == potential_divisor
end
end
q =  divisors.map {|x| x**2 }.reduce{|a,b| a+b }


There are probably even better approaches if you dug into maths, but I got 16 times shorter execution time for m,n = 1, 10_000 this way, so it might just cut it for you.

My suggestion:

def list_squared(m, n)
(m..n).each_with_object([]) do |to_check, result|
to_check_sqrt = Math.sqrt(to_check).to_i

area = (2..to_check_sqrt).inject(1 + to_check ** 2) do |sum, divisor|
if to_check % divisor == 0
sum += divisor ** 2
sum += (to_check / divisor) ** 2 if divisor != (to_check / divisor)
end

sum
end

result << [to_check, area] if Math.sqrt(area) == Math.sqrt(area).to_i
end
end


Edit:

Or this way seems to work too and a little bit faster:

def list_squared2(m, n)
divisors = {}

# build a divisor lookup table
(1..Math.sqrt(n).to_i).each do |divisor|
(((m / divisor).to_i * divisor)..n).step(divisor) do |divisor_of|
divisors[divisor_of] ||= []
divisors[divisor_of] << divisor
divisors[divisor_of] << divisor_of / divisor if divisor != (divisor_of / divisor)
end
end

# lookup needed values
(m..n).each_with_object([]) do |to_check, result|
divisors[to_check] += [to_check]
area = divisors[to_check].uniq.inject(0) { |sum, divisor| sum + divisor ** 2 }

result << [to_check, area] if Math.sqrt(area) == Math.sqrt(area).to_i
end
end