Reciprocal cycles

2014-09-17

Problem 026: Reciprocal cycles

Description:

A unit fraction contains 1 in the numerator. The decimal representation of the unit fractions with denominators 2 to 10 are given:

1/2  =  0.5
1/3  =  0.(3)
1/4  =  0.25
1/5  =  0.2
1/6  =  0.1(6)
1/7  =  0.(142857)
1/8  =  0.125
1/9  =  0.(1)
1/10 =  0.1

Where 0.1(6) means 0.166666..., and has a 1-digit recurring cycle. It can be seen that 1/7 has a 6-digit recurring cycle.

Find the value of d < 1000 for which 1/d contains the longest recurring cycle in its decimal fraction part.

Solution:

v
####################################################################################################
####################################################################################################
####################################################################################################
####################################################################################################
####################################################################################################
####################################################################################################
####################################################################################################
####################################################################################################
####################################################################################################
####################################################################################################

>"d"00p"}"8*60p080p090p              #v v#                  p+1/g00g04%g00g04g05<
>60g>:30p>:10p>0\00g%10g00g/v>140p050p>4 0g55+*30g%40p50g1+50p40g00g%40g00g/1+g!|
  >80g.@      |p01::-1g01p+1<           vp08g03p09_v#`g09:-g+1/g00g04%g00g04g05 <
^_^#p06:-1g06 ># $#          ^#         <         $<

Start

Pause

Reset

Download

Output:

Stack: (0)

Explanation:

To calculate the repeating-digit-count we use an algorithm based on the idea of a long division. Here on the example of 1/7

Position	Value	Remainder	Note
0	0,	10/7	`10/7 = 1` & `(10%7)*10 = 30`
1	0,1	30/7	`30/7 = 1` & `(30%7)*10 = 20`
2	0,13	20/7	`20/7 = 1` & `(20%7)*10 = 60`
3	0,132	60/7	`60/7 = 1` & `(60%7)*10 = 40`
4	0,1328	40/7	`40/7 = 1` & `(40%7)*10 = 50`
5	0,13285	50/7	`50/7 = 1` & `(50%7)*10 = 10`
6	0,132857	10/7	duplicate remainder -> loop closed

=> RepeatingDigitCount := 6 - 0 = 6

We use a 1000-field "array" to remember every remainder we already had - as soon as we reach one that is already in use the digits start repeating itself.

For better understanding here the FindRepeatingDigitCount(int divisor) algorithm in pseudo-code:

int current = 1;
int position = 0;
while(true) {
    current = (current*10) % divisor;
    position++;

    if (grid[current] != 0) return position - grid[current];
    else grid[current] = position;
}