Problem 26(Reciprocal cycles)

Problem 26(Reciprocal cycles)

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.

 

In Python:

import time

def remainder(i, r):
    return 10 * r % i

startTime = time.time()
sizeCycle = []
for i in range(2, 1000):
    remainders = [1]
    while(True):
        remainders.append(remainder(i, remainders[-1]))
        if remainders[-1] in remainders[0: -1] or remainders[-1] == 0:
            sizeCycle.append(len(remainders))
            break
print(sizeCycle.index(max(sizeCycle)) + 2)
print(time.time() - startTime, "seconds")

Run time: 0.3535029888153076 seconds

 

In Java:

package project_euler21_30;

import java.util.ArrayList;
import java.util.Collections;

public class Euler26 {
	public static int remainder(int i, int r) {
		return 10 * r % i;
	}
	public static void main(String[] args) {
		long startTime = System.currentTimeMillis();
		ArrayList<Integer> sizeCycle = new ArrayList<Integer>();
		for (int i = 2; i < 1000; i++) {
			ArrayList<Integer> remainders = new ArrayList<Integer>();
			remainders.add(1);
			while(true) {
				int value = remainder(i, remainders.get(remainders.size() - 1));
				if (remainders.contains(value) == true || value == 0) {
					sizeCycle.add(remainders.size());
					break;
				} else {
					remainders.add(value);
				}
			}
		}
		System.out.println(sizeCycle.indexOf(Collections.max(sizeCycle)) + 2);
		long endTime = System.currentTimeMillis();
		System.out.println((double)(endTime - startTime)/(double)1000 + "seconds");
	}
}

Run time: 0.063seconds

 

Solution: 983