Find all integers between m and n whose sum of squared divisors is itself a square

Question

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 \le m \le 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.

I started learning Ruby two weeks ago so I don't know much. This is my first programming language.

Is it possible to rewrite the below code so it runs faster? It currently times out at n>9999.

def list_squared(m, n)


r = (m..n).to_a.map { |z| (1..z).select { |x| z % x == 0} } 
#returns the divisors of each number in an array of arrays

squarenumbers = r.map { |x| x.map { |c| c**2 }.inject(:+) }.select { |x| Math.sqrt(x) % 1 == 0 } 
#this finds all integers between m and n whose sum of squared divisors  is itself a square

booleans = r.map { |x| x.map { |c| c**2 }.inject(:+) }.map { |x| Math.sqrt(x) % 1 == 0 }
#returns an array of booleans.

indexer = booleans.map.with_index{|x, i| i if x == true }.compact
#returns the index of each of the true values in booleans as an array

unsqr = indexer.map { |x| (m..n).to_a[x] }
#returns the numbers whose squared divisors is a square in an array

unsqr.zip(squarenumbers) 
#merges the two arrays together, element for element and creates an array of arrays

end

#for m = 1 and n = 1000 the result would be

#[[1, 1], [42, 2500], [246, 84100], [287, 84100], [728, 722500]]

Answer 1

If you were able to write this after just two weeks, knowing nothing previously about programming, then I would have to say: well done! This is excellent code for a beginner. I really like the way you have applied transformations and filters to entire arrays, instead of falling into the trap of proceeding instruction by instruction.

Performance

Where is the performance problem likely to lie? It's almost certainly with the factoring (calculating r). For every number z, you test every candidate divisor from 1 to z. If you have n numbers to factor, then we would say that this step is O(n²). That indicates a scalability problem.

Calculating squarenumbers is relatively straightforward. Summing the squares of a list of numbers is easy. Checking whether their square roots are integer is slightly more expensive, but still a simple operation.

Calculating booleans is also straightforward. But it's repeating exactly the same calculations as for calculating squarenumbers, which is wasteful.

The last three statements to gather the result are also quite simple.

So, the problem is with factoring. How can that be improved? Observe that factors always occur in pairs: 1×42 = 2×21 = 3×14 = 6×7. Once you discover the factors of \$z\$ up to \$\sqrt{z}\$ by trial-and-error, you automatically know the corresponding larger factors.

Readability

In the first statement, you used z for the dummy variable. In subsequent statements, you switched to x. I recommend using the same name for variables that serve the same purpose.

There are some nested map calls. That makes the code trickier to read. What can we do about that? Notice that we test every z (subsequently called "x") independently. Therefore, there is no need to calculate the divisors of each number in an array of arrays. We can just consider each number in [m, m + 1, m + 2, …, n] on its own.

Suggested solution

require 'set'

def list_squared(m, n)
  (m..n).map do |num|
    divisors = Set.new((1..Math.sqrt(num)).select { |d| num % d == 0 })
    divisors += divisors.map { |d| num / d } 

    sum_sq_divisors = divisors.map { |d| d * d }.inject(:+)
    [num, sum_sq_divisors] if Math.sqrt(sum_sq_divisors) % 1 == 0
  end.compact
end

Answer 2

More on efficiency

Focus on prime divisors. For example, \$42 = 2*3*7\$. Notice that

\$(1+2^2)(1+3^2)(1+7^2) = 5*10*50 = 2500\$

This is not a coincidence. Using a standard number theoretical reasoning it is easy to prove that \$\sigma_2\$ (which you are suppose to compute) is a multiplicative function, that is for \$m,n\$ coprime, \$\sigma_2(mn) = \sigma_2(m)\sigma_2(n)\$.

This observation, and memoizing results, is a key to an efficient solution. Given \$n\$, find some prime factor \$p\$, and completely factor it out, so that \$n = p^am\$ and \$m\$ is not divisible by \$p\$. Now you have two coprimes; both less than \$n\$ so their sigmas are already known. Multiply and check for squaredness.

PS: I seriously dislike such problems. They are not about programming.