Find all integers between m and n whose sum of squares is the square

Question

Problematic issue

The devisors 42 are equal: 1, 2, 3, 6, 7, 14, 21, 42. These are the squares of the divisors: 1, 4, 9, 36, 49, 196, 441, 1764. The sum of the squares is the divisors 2500, 50 * 50, square !

For two integers m, n (1 <= m <= n), we want to find all integers between m and n whose sum of squares is a square. 42 is such a number.

The result will be an array of arrays, each of which will have two elements, first a number, whose quadratic squares are a square, and then the sum of the squares.

Code below

How can I make this particular program run faster? My current code expires after n> 9999.

#returns the divisors of each number in an array of arrays r = (m..n).to_a.map { |z| (1..z).select { |x| z % x == 0} } #this finds all integers between m and n whose sum of squared divisors is itself a square squarenumbers = r.map { |x| x.map { |c| c**2 }.inject(:+) }.select { |x| Math.sqrt(x) % 1 == 0 } #returns an array of booleans. booleans = r.map { |x| x.map { |c| c**2 }.inject(:+) }.map { |x| Math.sqrt(x) % 1 == 0 } #returns the index of each of the true values in booleans as an array indexer = booleans.map.with_index{|x, i| i if x == true }.compact #returns the numbers whose squared divisors is a square in an array unsqr = indexer.map { |x| (m..n).to_a[x] } #merges the two arrays together, element for element and creates an array of arrays unsqr.zip(squarenumbers) # for m = 1 and n = 1000 the result would be # [[1, 1], [42, 2500], [246, 84100], [287, 84100], [728, 722500]] 

Answer 1

Rough factor calculation

You start by calculating:

 m, n = 40, 42 r = (m..n).to_a.map { |z| (1..z).select { |x| z % x == 0} } #=> [[1, 2, 4, 5, 8, 10, 20, 40], [1, 41], [1, 2, 3, 6, 7, 14, 21, 42]] 

This is normal, but you do not need .to_a :

 r = (m..n).map { |z| (1..z).select { |x| z % x == 0} } #=> [[1, 2, 4, 5, 8, 10, 20, 40], [1, 41], [1, 2, 3, 6, 7, 14, 21, 42]] 

This avoids the extra step of creating a temporary array of ^1.2 :

 (m..n).to_a #=> [40, 41, 42] 

Solution structure

Let's work backwards to come up with our code. First, concentrate on determining for any given number q whether the sum of the squared factors of q itself an ideal square. Suppose we are magic_number? magic_number? method magic_number? which takes q as its only argument and returns true if q satisfies the required property, and false otherwise. Then we will calculate:

 (m..n).select { |q| magic_number?(q) } 

return an array of all numbers between m and n that satisfy the property. magic_number? you can write like this:

 def magic_number?(q) return true if q == 1 s = sum_of_squared_factors(q) s == Math.sqrt(s).round**2 end 

Calculation of the sum of squared factors

So, now we just have to write the sum_of_squared_factors method. We can use your code to obtain the following factors:

 def factors(q) (1..q).select { |x| q % x == 0 } end factors(40) #=> [1, 2, 4, 5, 8, 10, 20, 40] factors(41) #=> [1, 41] factors(42) #=> [1, 2, 3, 6, 7, 14, 21, 42] 

and then write:

 def sum_of_squared_factors(q) factors(q).reduce(0) { |t,i| t + i*i } end sum_of_squared_factors(40) #=> 2210 sum_of_squared_factors(41) #=> 1682 sum_of_squared_factors(42) #=> 2500 

Speed ​​up factor calculation

There is something else we can do to expedite the calculation of factors. If f is a factor of n , f and n/f , both are coefficients of n . (For example, since 3 is a coefficient of 42 , then 42/3 #=> 14 ). Therefore, we only need to get the smallest of each pair.

There is one exception to this rule. If n is an ideal square and f == n**0.5 , then f = n/f , so we include f only in the number of factors n (not n/f as well).

If it turns out that if f less than a pair, then f <=(n**0.5).round ³ . Therefore, we only need to check which of the numbers (1..(n**0.5).round) are factors and include their complements (if n is an ideal square, in this case we do not double (n**0.5).round ):

 q = 42 arr = (1..Math.sqrt(q).round).select { |x| q % x == 0 } #=> [1, 2, 3, 6] arr = arr.flat_map { |n| [n, q/n] } #=> [1, 42, 2, 21, 3, 14, 6, 7] arr.pop if a[-2] == a[-1] arr #=> [1, 42, 2, 21, 3, 14, 6, 7] q = 36 arr = (1..Math.sqrt(q).round).select { |x| q % x == 0 } #=> [1, 2, 3, 4, 6] arr = arr.flat_map { |n| [n, q/n] } #=> [1, 36, 2, 18, 3, 12, 4, 9, 6, 6] arr.pop if a[-2] == a[-1] #=> 6 arr #=> [1, 36, 2, 18, 3, 12, 4, 9, 6] 

so that we can write:

 def factors(q) arr = (1..Math.sqrt(q)).select { |x| q % x == 0 } arr = arr.flat_map { |n| [n, q/n] } arr.pop if arr[-2] == arr[-1] arr end 

Substituting arr (chaining expressions), we get a typical Ruby expression:

 def factors(q) (1..Math.sqrt(q)).select { |x| q % x == 0 }. flat_map { |n| [n, q/n] }. tap { |a| a.pop if a[-2] == a[-1] } end factors(42) #=> [1, 42, 2, 21, 3, 14, 6, 7] factors(36) #=> [1, 36, 2, 18, 3, 12, 4, 9, 6] 

See Enumerable # flat_map and Object # tap . (There is no need to sort this array. In applications where it should be sorted, simply .sort to the end of the flat_map block.)

Completion

As a result, we have the following:

 def magic_number?(q) return true if q == 1 s = sum_of_squared_factors(q) s == Math.sqrt(s).round**2 end def sum_of_squared_factors(q) factors(q).reduce(0) { |t,i| t + i*i } end def factors(q) (1..Math.sqrt(q)).select { |x| q % x == 0 }. flat_map { |n| [n, q/n] }. tap { |a| a.pop if a[-2] == a[-1] } end m, n = 1, 1000 (m..n).select { |q| magic_number?(q) } #=> '[1, 42, 246, 287, 728] 

This calculation was completed in no time.

Calculate prime numbers for further calculation of factor speed

Finally, let me describe an even faster way to calculate number factors using the Prime :: prime_division method . This method splits any number into its main components. Consider, for example, n = 360 .

 require 'prime' Prime.prime_division(360) #=> [[2, 3], [3, 2], [5, 1]] 

This tells us that:

 360 == 2**3 * 3**2 * 5**1 #=> true 

This also tells us that each factor of 360 is a product from 0 to 3 2 times 0 and 2 3 times 0 or 1 5 . Hence:

  def factors(n) Prime.prime_division(n).reduce([1]) do |a,(prime,pow)| a.product((0..pow).map { |po| prime**po }).map { |x,y| x*y } end end a = factors(360).sort #=> [ 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 18, # 20, 24, 30, 36, 40, 45, 60, 72, 90, 120, 180, 360] 

We can check this:

  a == (1..360).select { |n| (360 % n).zero? } #=> true 

One more check:

  factors(40).sort #=> [1, 2, 4, 5, 8, 10, 20, 40] 

^{1. Instead, you can write this [*m..n] #=> [40, 41, 42] . 2. Why is there no need to convert the range to an array? Enumerable # map , which is an instance method of the Enumerable module, is available for use by each class in which Enumerable . Array is one, but (m..n).class #=> Range is another. (See second paragraph in the range ). 3. Assume that f less than n/f and f > n**0.5 , then n/f < n/(n**0.5) = n**0.5 < f , a contradiction.}

Answer 2

I do not know Ruby, but the problem lies in the algorithm used when searching for number divisors (which is not specific to the language used, that is, Ruby in this case).

 r = (m..n).to_a.map { |z| (1..z).select { |x| z % x == 0} } 

To find the divisors of the integer n , you divide n by all positive integers up to n - 1 , which means that the cycle runs n - 1 times. However, it suffices to calculate up to sort(n) to calculate the divisors. In pseudo code, it looks like this:

 for i = 1 to i <= sqrt(n) r = n % i if r == 0 then i is a divisor if n / i != i then n / i is another divisor 

For instance:

 sqrt_42 = 6.48074069840786 i = 1 => 1 and 42 are two divisors i = 2 => 2 and 21 i = 3 => 3 and 14 i = 4 => no divisor i = 5 => no divisor i = 6 => 6 and 7 

And that’s all.

This will significantly improve performance, since now the loop only works sort(n) times instead of n - 1 times, which is a big difference for large n .