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

Float can't represent most decimal numbers precisely, so using (1.to_f/number).to_s probably won't give you the expected result. This means your whole algorithm is incorrect.

---

You need a different algorithm. Here's a hint: 1.0 / 7 in math produce a decimal 0.142857142857..., the repeated sequence is 142857. If you do this division using, you'll notice that 142857 is a divisor of 999999, which is not a coincidence.

Numbers that are multiples of 2 or 5 need some extra attention. The trick is that, for example, 14 (7 * 2) or 35 (7 * 5), have the same number of repeated sequence in their 1.0 / n decimal representation.

It's a little difficult to explain this idea without code. I have solved this Project Euler problem, but hope that you can solve it without looking at my source code first.