最长的数字循环周期 [英] Longest recurring cycle of digits
问题描述
我试图找到小于1000的数字，该数字在除以1时会产生最长的重复数字字符串。我有一个十进制数字列表，必须找到重复序列最长的数字。
I'm trying to find the number less than 1000 that produces the longest string of repeated numbers when it divides 1. I have a list of decimal numbers and have to find the ones which have the longest repeated sequence.
这是我到目前为止所拥有的
Here's what I have so far
numbers = [*2..999]
decimal_representations = numbers.map { |number| 1.to_f/number }
decimal_representations.map!(&:to_s)
I可以通过使用正则表达式生成三维数组。正则表达式 /（。+）\1 + / 产生一个重复的子字符串数组。我想找到最长的子字符串，所以我使用了可枚举的 max_by 函数。
I can produce a three dimensional array by using regex. Regex /(.+)\1+/ produces an array of repeated substrings. I want to find the longest substring, so I used enumerable's max_by function.
decimal_representations.map! { |decimal| decimal.scan(/(.+)\1+/).max_by(&:length) }.flatten
我必须压缩数组以删除 nil 个元素
I have to compact my array to remove nil elements
decimal_representations.compact!
然后我可以找出长度最长的文件。
Then I can find out which had the longest length.
decimal_representations.max_by(&:length)
我得到 0090009009 ，但是由于从数组中删除了零个元素，所以我无法弄清楚哪个数字具有该十进制值。
I get 0090009009, but I can't figure out which number had that decimal value, because I removed nil elements from my array.
有什么想法吗？
推荐答案
您可以按照以下步骤进行操作。
You can do that as follows.
代码
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 具有重复的小数：
Here are the numbers between 3 and 30 that have repeating decimals:
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 具有有限值，则返回一个空字符串。
When you are doing long-division and encounter a remainder you had previously, you know the sequence from the earlier remainder on will repeat forever, so you stop there and mark the repeating sequence. That's precisely what find_repeating does. If 1.0/n (n being find_repeating's argument) has repeating digits, a string of the repeating digits is returned. If 1.0/n has a finite value, an empty string is returned.
在旁边 >
您问：我得到009009009，但我不知道哪个数字具有该十进制值，...。 （您在中间有一个额外的零，我认为这是一个错字。）这是获取数字的方法。
You asked: "I get 009009009, but I can't figure out which number had that decimal value,...". (You had an extra zero in the middle, which I assume was a typo.) Here's how to get the number.
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 以获得更长的重复小数。
You will have to use BigDecimal for longer repeating decimals.
这篇关于最长的数字循环周期的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
