找出m和n之间的所有整数,它们的平方除数之和本身就是一个平方 [英] Find all integers between m and n whose sum of squared divisors is itself a square
问题描述
42的因子为:1、2、3、6、7、14、21、42。这些因子的平方为:1、4, 9,36,49,196,441,1764。平方除数的总和是2500,即50 * 50,一个平方!
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!
给出两个整数m,n (1< = m< = n)我们想找到m和n之间的所有整数,它们的平方除数之和本身就是一个平方。 42是这样的数字。
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.
如何使此特定程序运行得更快?我当前的代码在n> 9999之后超时。
How can I make this specific program run faster? My current code times out 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]]
推荐答案
因素的蛮力计算
您首先要计算:
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
:
That's OK, but you don't 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]]
这避免了额外的步骤,即创建临时数组 1,2 :
This avoids an extra step, which is the creation of the temporary array1,2:
(m..n).to_a #=> [40, 41, 42]
解决方案的结构
让我们倒退一下,以得出我们的代码。首先,对于任何给定的数字 q
,专注于确定 q
因子的平方和是否本身一个完美的正方形。假设我们构造了一个方法 magic_number?
,该方法将 q
作为唯一参数并返回 true
如果 q
满足要求的属性,否则为 false
。然后我们将计算:
Let's work backwards to come up with our code. First, concentrate on determining, for any given number q
, if the sum of squares of the factors of q
is itself a perfect square. Suppose we construct a 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 compute:
(m..n).select { |q| magic_number?(q) }
返回 m之间所有数字的数组满足该属性的
和 n
。 magic_number?
可以这样写:
to return an array of all numbers between m
and n
that satisfy the property. magic_number?
can be written like this:
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
。我们可以使用您的代码来获取因子:
So now we are left with writing the method sum_of_squared_factors
. We can use your code to obtain the 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
)。因此,我们只需要获得每对中较小的一个即可。
There's something more we can do to speed up the calculation of factors. If f
is a factor of n
, f
and n/f
, are both factors of n
. (For example, since 3
is a factor of 42
, so is 42/3 #=> 14
). We therefore need only obtain the smaller of each pair.
此规则有一个例外。如果 n
是一个完美的正方形,而 f == n ** 0.5
,则 f = n / f
,因此我们在 n
的因素中只包括 f
(不包括 n / f
)。
There is one exception to this rule. If n
is a perfect square and f == n**0.5
, then f = n/f
, so we only include f
among the factors of n
(not n/f
as well).
如果事实证明,如果 f
是该货币对中的较小者,则 f< =(n ** 0.5).round
3 。因此,我们只需要检查(1 ..(n ** 0.5).round)
中的哪些是因子并包括补数(除非 n
是一个完美的正方形,在这种情况下,我们不会重复计算(n ** 0.5).round
):
If turns out that if f
is the smaller of the pair, f <=(n**0.5).round
3. We therefore need only check to see which of the numbers (1..(n**0.5).round)
are factors and include their complements (unless n
is a perfect square, in which case we do not double-count (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表达式:
Substituting out arr
("chaining" expressions), we obtain 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]
请参见< a href = http://ruby-doc.org/core-2.5.1/Enumerable.html#method-i-flat_map rel = nofollow noreferrer> Enumerable#flat_map 和 Object#tap 。 (无需对该数组进行排序。在需要对其进行排序的应用程序中,只需将 .sort
粘贴到 flat_map的末尾
s block。)
See Enumerable#flat_map and Object#tap. (There's no need for this array to be sorted. In applications where it needs to be sorted, just tack .sort
onto the end of flat_map
s 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
。
Lastly, let me describe an even faster way to compute the factors of a number, using the method Prime::prime_division. That method decomposes any number into its prime components. Consider, for example, 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
s乘以 0
或 1
5
。因此:
It also tells us that every factor of 360
is the product of between 0
and 3
2
's, multiplied by between 0
and 2
3
's, multiplied by 0
or 1
5
's. Therefore:
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 的每个类使用code>。
Array
是一个,但(m..n).class#=>范围
是另一个。 (请参见范围的第二段。)
3。假设 f
小于 n / f
和 f> n ** 0.5
,然后 n / f< n /(n ** 0.5)= n ** 0.5< f
,矛盾。
1. You could instead write that [*m..n] #=> [40, 41, 42]
.
2. Why is it not necessary to convert the range to an array? Enumerable#map, being an instance method of the module Enumerable
, is available for use by every class that include
s Enumerable
. Array
is one, but (m..n).class #=> Range
is another. (See the second paragraph at Range).
3. Suppose f
is smaller than n/f
and f > n**0.5
, then n/f < n/(n**0.5) = n**0.5 < f
, a contradiction.
这篇关于找出m和n之间的所有整数,它们的平方除数之和本身就是一个平方的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!