Tag Archive for 'recurring'

Problem 26 in Project Euler is a very simple question. There are two options – check the periodicity of numbers in quotient, or check the periodicity of remainders. Yup! The periodicity of remainders implies periodicity in quotient.

Here is my Java solution. It runs in 125ms on my Latitude D630 laptop.

public class Problem_26 {
	/**
	 * @return The number which has the highest recurring decimal periodicity
	 */
	public int getLargestPeriodicityNumber() {
		PrimeNumbersIterator primes = new PrimeNumbersIterator(1000);
		primes.reverseOrder();
		MaxObject<Integer> maxNumber = MaxObject.init();

		Stopwatch sw = new Stopwatch();
		sw.start();
		while (primes.hasNext()) {
			int i = primes.next();
			maxNumber.compare(i, getPeriodicity(i));
		}
		sw.stop();
		System.out.println(sw);

		return maxNumber.getMaxObject();
	}

	/**
	 * Get the periodicity of recurring decimals by checking the remainders
	 *
	 * @param number The number for which the periodicity is required
	 * @return The periodicity of recurring decimal
	 */
	private int getPeriodicity(int number) {
		List<Integer> remainders = new ArrayList<Integer>();

		int remainder = 10;
		remainders.add(remainder);
		while (true) {
			remainder = remainder % number * 10;
			if (remainders.contains(remainder))
				return remainders.size() - remainders.indexOf(remainder);
			remainders.add(remainder);
		}
	}

	public static void main(String[] args) {
		System.out.println(new Problem_26().getLargestPeriodicityNumber());
	}
}

Popularity: 8% [?]