Longest recurring cycle of digits

Question

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

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)

I get 0090009009, but I can't figure out which number had that decimal value, because I removed nil elements from my array.

Any ideas?

Answer 1

You can do that as follows.

Code

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

Examples

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

Hmmm. Interesting pattern.

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

Explanation

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.

Aside

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

Confirm:

1.0/111 #=> 0.009009...    

You will have to use BigDecimal for longer repeating decimals.