Project Euler with Befunge


Fork me on GitHub
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
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;
}

Interpreter steps: 21 266 126
Execution time (BefunExec): 4.48s (4.75 MHz)
Program size: 100 x 16
Solution: 983
Solved at: 2014-09-17



made with vanilla PHP and MySQL, no frameworks, no bootstrap, no unnecessary* javascript