Solution to Project Euler 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: 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.
Updated: Aug. 15, 2022 — Training Time: 2 minutes
Overseen by: Archangel Macsika
All Training Resources
Scroll for more menu list
Topic: Project Euler Problem 26: Reciprocal cycles.
Difficulty: Easy.
Objective: 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.
Input: None.
Expected Output: 983.
Sikademy Solution in Java Programming Language
package sikademy;
/**
*
* @author Archangel Macsika
* Copyright (c) Sikademy. All rights reserved
*/
import java.util.HashMap;
import java.util.Map;
public class SikademyEulerSolution {
public String run() {
int bestNumber = 0;
int bestLength = 0;
for (int i = 1; i <= 1000; i++) {
int len = getCycleLength(i);
if (len > bestLength) {
bestNumber = i;
bestLength = len;
}
}
return Integer.toString(bestNumber);
}
private static int getCycleLength(int n) {
Map stateToIter = new HashMap<>();
int state = 1;
for (int iter = 0; ; iter++) {
if (stateToIter.containsKey(state))
return iter - stateToIter.get(state);
else {
stateToIter.put(state, iter);
state = state * 10 % n;
}
}
}
public static void main(String[] args) {
SikademyEulerSolution solution = new SikademyEulerSolution();
System.out.println(solution.run());
}
}
Sikademy Solution in Python Programming Language
#
# @author Archangel Macsika
# Copyright (c) Sikademy. All rights reserved.
#
import itertools
def compute():
ans = max(range(1, 1000), key=reciprocal_cycle_len)
return str(ans)
def reciprocal_cycle_len(n):
seen = {}
x = 1
for i in itertools.count():
if x in seen:
return i - seen[x]
else:
seen[x] = i
x = x * 10 % n
if __name__ == "__main__":
print(compute())