arrays - 找出 m 和 n 之间的所有整数，这些整数的平方和本身就是一个平方

Question

问题问题

42 的因数是:1、2、3、6、7、14、21、42。这些因数的平方是:1、4、9、36、49、196、441、1764。平方和除数是 2500 即 50 * 50，一个正方形!

给定两个整数 m, n (1 <= m <= n)，我们想要找到 m 和 n 之间的所有整数，它们的平方除数之和本身就是一个平方。 42 就是这样一个数字。

结果将是一个数组数组，每个子数组有两个元素，第一个是平方因子为正方形的数，然后是平方因子的和。

代码如下

如何使这个特定程序运行得更快？我当前的代码在 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

因子的蛮力计算

您首先计算:

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]]

没关系，但你不需要 .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]]

这避免了额外的步骤，即创建临时数组^1,2:

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

解决方案的结构

让我们逆向工作以得出我们的代码。首先，集中精力确定，对于任何给定的数字 q , 如果 q 的因子的平方和本身就是一个完美的正方形。假设我们构造一个方法 magic_number?这需要 q作为它唯一的参数并返回 true如果q满足所需的属性和 false否则。然后我们将计算:

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

返回 m 之间所有数字的数组和 n满足性质。 magic_number?可以这样写:

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

计算平方因子之和

所以现在我们只剩下编写方法 sum_of_squared_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]

然后写:

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 

加速因子计算

我们还可以做更多的事情来加快因子的计算。如果f是 n 的因数, f和 n/f , 都是 n 的因子. (例如，由于 3 是 42 的因数，所以 42/3 #=> 14 也是)。因此，我们只需要获取每对中较小的一个。

这一规则有一个异常(exception)。如果n是一个完美的正方形并且f == n**0.5 , 然后 f = n/f , 所以我们只包括 f n的因素之一(也不是 n/f)。

如果结果是 f是这对中较小的一个，f <=(n**0.5).round ³。因此，我们只需要检查数字 (1..(n**0.5).round) 中的哪一个。是因子并包括它们的补码(除非 n 是一个完全正方形，在这种情况下我们不会重复计算 (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] 

所以我们可以这样写:

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

替换出 arr (“链接”表达式)，我们得到一个典型的 Ruby 表达式:

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] 

参见 Enumerable#flat_map和 Object#tap . (这个数组不需要排序。在需要排序的应用程序中，只需将 .sort 添加到 flat_map block 的末尾即可。)

总结

总而言之，我们剩下以下内容:

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]

这个计算一眨眼就完成了。

计算素数以进一步加速因子计算

最后，让我描述一种计算数字因子的更快方法，使用方法 Prime::prime_division .该方法将任何数字分解为其主要组成部分。例如，考虑 n = 360 .

require 'prime'

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

这告诉我们:

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

它还告诉我们 360 的每个因子是 0 之间的产物和 3 2的，乘以 0 之间和 2 3的，乘以 0或 1 5的。因此:

 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]

我们可以检查:

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

另一张支票:

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

^{1。你可以改为写 [*m..n] #=> [40, 41, 42] .}<补充>2。为什么不需要将范围转换为数组？ Enumerable#map , 作为模块的实例方法 Enumerable , 可供 include 的每个类使用s Enumerable . Array是一个，但是 (m..n).class #=> Range是另一个。 (参见 Range 的第二段)。<补充>3。假设 f小于 n/f和 f > n**0.5 , 然后 n/f < n/(n**0.5) = n**0.5 < f , 自相矛盾。