最长的循环数字
Longest recurring cycle of digits
我试图找到小于 1000 的数字，它在除以 1 时产生最长的重复数字串。我有一个十进制数字列表，必须找到具有最长重复序列的数字。
这是我目前所拥有的
numbers = [*2..999]
decimal_representations = numbers.map { |number| 1.to_f/number }
decimal_representations.map!(&:to_s)
我可以使用正则表达式生成三维数组。正则表达式 /(.+)+/ 生成一个重复子字符串数组。我想找到最长的子串，所以我使用了可枚举的max_by函数。
decimal_representations.map! { |decimal| decimal.scan(/(.+)+/).max_by(&:length) }.flatten
我必须压缩数组以删除 nil 个元素
decimal_representations.compact!
然后我可以找出最长的长度。
decimal_representations.max_by(&:length)
我得到 0090009009，但我无法弄清楚哪个数字具有该十进制值，因为我从数组中删除了 nil 元素。
有什么想法吗？
Float 不能精确表示大多数小数，因此使用 (1.to_f/number).to_s 可能不会给您预期的结果。这意味着你的整个算法是不正确的。
您需要不同的算法。这里有一个提示：1.0 / 7 在数学中产生一个小数 0.142857142857...，重复序列是 142857。如果您使用此除法，您会注意到 142857 是 999999 的约数，这并非巧合。
2 或 5 的倍数的数字需要额外注意。诀窍是，例如 14 (7 * 2) 或 35 (7 * 5)，在它们的 1.0 / n 十进制表示中具有相同数量的重复序列.
如果没有代码，很难解释这个想法。我先解决了this Project Euler problem, but hope that you can solve it without looking at my source code
对应的数是111，我是用你答案的倒数计算出来的：
1/0.009009009009009 = 111
顺便说一句，我并不是说你的答案是正确的，我只是帮助你解读你得到的答案。 1/7的数字重复序列较长
真正解决问题
我真的解决了这个问题。这是我写的 code/notes 来解决它。如果您只是在查看我的代码之前阅读了我的评论，那么您应该能够自己编写代码以发现这里发生了什么。想被剧透的直接往最底下看答案是什么
# First, we need to figure out how digits in a decimal representation
# of a fraction get calculated. We will write a method that prints
# the first 50 decimal digits after the decimal point for the decimal
# representation of a/b, where a and b are integers.
def print_digits_after_decimal(a, b)
raise ArgumentError if !a.is_a?(Integer)
raise ArgumentError if !b.is_a?(Integer)
# We only care about what's happening after the decimal point.
r = a % b
print "#{a}/#{b} = ."
50.times do
r *= 10
digit = r / b
print digit
r = r % b
end
puts
end
print_digits_after_decimal(1, 7)
print_digits_after_decimal(11, 28)
# Results:
# 1/7 = .14285714285714285714285714285714285714285714285714
# 11/28 = .39285714285714285714285714285714285714285714285714
# The only thing that changes on each iteration of that loop is r.
# Observe that r is always within the finite range 0..(b-1). So
# eventually r MUST be equal to a value that it already had before.
# We will write a method to find that first repeated r value. This
# represents the state of the digit-generating state machine for the
# first state where the decimal digits start a repeating sequence.
def first_repeated_r(a, b)
raise ArgumentError if !a.is_a?(Integer)
raise ArgumentError if !b.is_a?(Integer)
r = a % b
log = []
while true do
return r if log.include?(r)
log << r
r = (r * 10) % b
end
end
# Now use that r value to generate the digits that repeat. We need to
# call the first_repeated_r method above, and generate digits until we
# see that r value again, and then return those digits as an array.
def repeating_decimal_sequence(a, b)
r_start = r = first_repeated_r(a, b)
digits = []
while true
r *= 10
digits << r / b
r = r % b
break if r == r_start
end
digits
end
# Keep in mind that each r value corresponds to a digit we print out,
# but many different r values can correspond to the same digit. We
# have not proved that the sequence returned by
# repeating_decimal_sequence doesn't contain a repeated sequence
# inside itself. We will write a method that takes an array of digits
# and shortens it to the smallest repeating sequence.
def decimal_sequence_deduplicate(digits)
(1..digits.size).each do |n|
subsequence = digits[0, n]
q, r = digits.size.divmod(n)
if r == 0 && subsequence * q == digits
return subsequence
end
end
raise "Impossible!" # math broke
end
p decimal_sequence_deduplicate([1, 5, 8]) # => [1, 5, 8]
p decimal_sequence_deduplicate([1, 5, 1, 5]) # => [1, 5]
# Now we can put these pieces together to answer your question.
answer = (1...1000).max_by do |n|
decimal_sequence_deduplicate(repeating_decimal_sequence(1, n)).size
end
puts answer # => 983
# And now we should feel kind of dumb because 983 is simply the
# largest prime number less than 1000, and Euler probably knew that
# without doing this much work!
您可以按如下方式进行。
代码
def longest_repeating_decimal(last)
n = (3..last).max_by { |i| find_repeating(i).size }
end
def find_repeating(n)
num = 1
a = []
remainders = {}
loop do
d,r = num.divmod(n)
return '' if r.zero?
a << d
return a[remainders[r]..-1].join if remainders.key?(r)
remainders[r] = a.size
num = 10*r
end
end
例子
n = longest_repeating_decimal(999)
#=> 983
find_repeating(n).size
#=> 982
find_repeating(n)
#=> "00101729399796541200...54323499491353"
require 'bigdecimal'
BigDecimal.new(Rational(1,n),990).to_s('990F')
#=> "0.00101729399796541200...5432349949135300101729..."
# |repeating->
n = longest_repeating_decimal(9_999)
#=> 9967
find_repeating(n).size
#=> 9966
n = longest_repeating_decimal(99_999)
#=> 99989 (took several minutes)
find_repeating(n).size
#=> 99988
嗯。有趣的模式。
以下是 3 和 30 之间有重复小数的数字：
def display(n)
(3..n).each do |i|
repeat = find_repeating(i)
(puts "%2d %9s %23.20f" % [i, repeat, 1.0/i]) unless repeat.empty?
end
end
display(30)
n repeating 1.0/n
3 3 0.33333333333333331483
6 6 0.16666666666666665741
7 142857 0.14285714285714284921
9 1 0.11111111111111110494
11 90 0.09090909090909091161
12 3 0.08333333333333332871
13 769230 0.07692307692307692735
14 714285 0.07142857142857142461
15 6 0.06666666666666666574
17 8 0.05882352941176470507
18 5 0.05555555555555555247
19 52631 0.05263157894736841813
21 476190 0.04761904761904761640
22 45 0.04545454545454545581
23 43 0.04347826086956521618
24 6 0.04166666666666666435
26 384615 0.03846153846153846367
27 370 0.03703703703703703498
28 571428 0.03571428571428571230
29 4 0.03448275862068965469
30 3 0.03333333333333333287
说明
当你在做长除法的时候，遇到了之前的余数，你知道从前面的余数开始的序列会永远重复，所以你就停在那里，标记重复的序列。这正是 find_repeating 所做的。如果 1.0/n（n 是 find_repeating 的参数）有重复数字，则返回重复数字的字符串。如果 1.0/n 具有有限值，则返回空字符串。
一边
您问的是："I get 009009009, but I can't figure out which number had that decimal value,..."。 （你在中间多了一个零，我认为这是一个打字错误。）这是获取数字的方法。
1/n = 0.009009...
10**3 * (1/n) = 9.009009...
10**3 * (1/n) - 1/n = 9
(10**3 - 1)/n = 9
n = (10**3 - 1)/9
= 111
确认：
1.0/111 #=> 0.009009...
对于更长的重复小数，您将不得不使用 BigDecimal。
我试图找到小于 1000 的数字，它在除以 1 时产生最长的重复数字串。我有一个十进制数字列表，必须找到具有最长重复序列的数字。
这是我目前所拥有的
numbers = [*2..999]
decimal_representations = numbers.map { |number| 1.to_f/number }
decimal_representations.map!(&:to_s)
我可以使用正则表达式生成三维数组。正则表达式 /(.+)+/ 生成一个重复子字符串数组。我想找到最长的子串，所以我使用了可枚举的max_by函数。
decimal_representations.map! { |decimal| decimal.scan(/(.+)+/).max_by(&:length) }.flatten
我必须压缩数组以删除 nil 个元素
decimal_representations.compact!
然后我可以找出最长的长度。
decimal_representations.max_by(&:length)
我得到 0090009009，但我无法弄清楚哪个数字具有该十进制值，因为我从数组中删除了 nil 元素。
有什么想法吗？
Float 不能精确表示大多数小数，因此使用 (1.to_f/number).to_s 可能不会给您预期的结果。这意味着你的整个算法是不正确的。
您需要不同的算法。这里有一个提示：1.0 / 7 在数学中产生一个小数 0.142857142857...，重复序列是 142857。如果您使用此除法，您会注意到 142857 是 999999 的约数，这并非巧合。
2 或 5 的倍数的数字需要额外注意。诀窍是，例如 14 (7 * 2) 或 35 (7 * 5)，在它们的 1.0 / n 十进制表示中具有相同数量的重复序列.
如果没有代码，很难解释这个想法。我先解决了this Project Euler problem, but hope that you can solve it without looking at my source code
对应的数是111，我是用你答案的倒数计算出来的：
1/0.009009009009009 = 111
顺便说一句，我并不是说你的答案是正确的，我只是帮助你解读你得到的答案。 1/7的数字重复序列较长
真正解决问题
我真的解决了这个问题。这是我写的 code/notes 来解决它。如果您只是在查看我的代码之前阅读了我的评论，那么您应该能够自己编写代码以发现这里发生了什么。想被剧透的直接往最底下看答案是什么
# First, we need to figure out how digits in a decimal representation
# of a fraction get calculated. We will write a method that prints
# the first 50 decimal digits after the decimal point for the decimal
# representation of a/b, where a and b are integers.
def print_digits_after_decimal(a, b)
raise ArgumentError if !a.is_a?(Integer)
raise ArgumentError if !b.is_a?(Integer)
# We only care about what's happening after the decimal point.
r = a % b
print "#{a}/#{b} = ."
50.times do
r *= 10
digit = r / b
print digit
r = r % b
end
puts
end
print_digits_after_decimal(1, 7)
print_digits_after_decimal(11, 28)
# Results:
# 1/7 = .14285714285714285714285714285714285714285714285714
# 11/28 = .39285714285714285714285714285714285714285714285714
# The only thing that changes on each iteration of that loop is r.
# Observe that r is always within the finite range 0..(b-1). So
# eventually r MUST be equal to a value that it already had before.
# We will write a method to find that first repeated r value. This
# represents the state of the digit-generating state machine for the
# first state where the decimal digits start a repeating sequence.
def first_repeated_r(a, b)
raise ArgumentError if !a.is_a?(Integer)
raise ArgumentError if !b.is_a?(Integer)
r = a % b
log = []
while true do
return r if log.include?(r)
log << r
r = (r * 10) % b
end
end
# Now use that r value to generate the digits that repeat. We need to
# call the first_repeated_r method above, and generate digits until we
# see that r value again, and then return those digits as an array.
def repeating_decimal_sequence(a, b)
r_start = r = first_repeated_r(a, b)
digits = []
while true
r *= 10
digits << r / b
r = r % b
break if r == r_start
end
digits
end
# Keep in mind that each r value corresponds to a digit we print out,
# but many different r values can correspond to the same digit. We
# have not proved that the sequence returned by
# repeating_decimal_sequence doesn't contain a repeated sequence
# inside itself. We will write a method that takes an array of digits
# and shortens it to the smallest repeating sequence.
def decimal_sequence_deduplicate(digits)
(1..digits.size).each do |n|
subsequence = digits[0, n]
q, r = digits.size.divmod(n)
if r == 0 && subsequence * q == digits
return subsequence
end
end
raise "Impossible!" # math broke
end
p decimal_sequence_deduplicate([1, 5, 8]) # => [1, 5, 8]
p decimal_sequence_deduplicate([1, 5, 1, 5]) # => [1, 5]
# Now we can put these pieces together to answer your question.
answer = (1...1000).max_by do |n|
decimal_sequence_deduplicate(repeating_decimal_sequence(1, n)).size
end
puts answer # => 983
# And now we should feel kind of dumb because 983 is simply the
# largest prime number less than 1000, and Euler probably knew that
# without doing this much work!
您可以按如下方式进行。
代码
def longest_repeating_decimal(last)
n = (3..last).max_by { |i| find_repeating(i).size }
end
def find_repeating(n)
num = 1
a = []
remainders = {}
loop do
d,r = num.divmod(n)
return '' if r.zero?
a << d
return a[remainders[r]..-1].join if remainders.key?(r)
remainders[r] = a.size
num = 10*r
end
end
例子
n = longest_repeating_decimal(999)
#=> 983
find_repeating(n).size
#=> 982
find_repeating(n)
#=> "00101729399796541200...54323499491353"
require 'bigdecimal'
BigDecimal.new(Rational(1,n),990).to_s('990F')
#=> "0.00101729399796541200...5432349949135300101729..."
# |repeating->
n = longest_repeating_decimal(9_999)
#=> 9967
find_repeating(n).size
#=> 9966
n = longest_repeating_decimal(99_999)
#=> 99989 (took several minutes)
find_repeating(n).size
#=> 99988
嗯。有趣的模式。
以下是 3 和 30 之间有重复小数的数字：
def display(n)
(3..n).each do |i|
repeat = find_repeating(i)
(puts "%2d %9s %23.20f" % [i, repeat, 1.0/i]) unless repeat.empty?
end
end
display(30)
n repeating 1.0/n
3 3 0.33333333333333331483
6 6 0.16666666666666665741
7 142857 0.14285714285714284921
9 1 0.11111111111111110494
11 90 0.09090909090909091161
12 3 0.08333333333333332871
13 769230 0.07692307692307692735
14 714285 0.07142857142857142461
15 6 0.06666666666666666574
17 8 0.05882352941176470507
18 5 0.05555555555555555247
19 52631 0.05263157894736841813
21 476190 0.04761904761904761640
22 45 0.04545454545454545581
23 43 0.04347826086956521618
24 6 0.04166666666666666435
26 384615 0.03846153846153846367
27 370 0.03703703703703703498
28 571428 0.03571428571428571230
29 4 0.03448275862068965469
30 3 0.03333333333333333287
说明
当你在做长除法的时候，遇到了之前的余数，你知道从前面的余数开始的序列会永远重复，所以你就停在那里，标记重复的序列。这正是 find_repeating 所做的。如果 1.0/n（n 是 find_repeating 的参数）有重复数字，则返回重复数字的字符串。如果 1.0/n 具有有限值，则返回空字符串。
一边
您问的是："I get 009009009, but I can't figure out which number had that decimal value,..."。 （你在中间多了一个零，我认为这是一个打字错误。）这是获取数字的方法。
1/n = 0.009009...
10**3 * (1/n) = 9.009009...
10**3 * (1/n) - 1/n = 9
(10**3 - 1)/n = 9
n = (10**3 - 1)/9
= 111
确认：
1.0/111 #=> 0.009009...
对于更长的重复小数，您将不得不使用 BigDecimal。