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

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