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

Question

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

• the Tin Man: 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.
• GhostRider: 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
• slowjack2k: What are you using for m and n? Just to have the same test case.
• GhostRider: 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).
• slowjack2k: Sounds like a test from codility.

Answer 1

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.

Answer 2

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.

Answer 3

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