Tag Archives: cycle detection

Problem Thirty One

7 Dec

Here’s problem thirty one:

Question: How many different ways can £2 be made using any number of coins?

My solution to this wasn’t very pretty — just look at the monstrous for loop below.

result = 2

for b in range(2):
	for c in range(5):
		if 100*b + 50*c > 200: continue
		for d in range(11):
			if 100*b + 50*c + 20*d > 200: continue
			for e in range(21):
				if 100*b + 50*c + 20*d + 10*e > 200: continue
				for f in range(41):
					if 100*b + 50*c + 20*d + 10*e + 5*f > 200: continue
					for g in range(101):
						if 100*b + 50*c + 20*d + 10*e + 5*f + 2*g > 200: continue
						for h in range(201):
							if 100*b + 50*c + 20*d + 10*e + 5*f + 2*g + h == 200:
								result += 1

print(result)

Yeah…zero points for style there. I know for a fact that there is a “clever” way of solving this problem, but its explanation was pretty over my head. Essentially this code works by trying (almost) every combination of coins possible and testing it to see if its value is 200. This is slightly streamlined by initially considering two possibilities, 200 and 100 + 100, so that there are less total calculations. This is the reason why result is initialized to 2 and there is no loop for the 200 coin. The number of calculations is also reduced by continuing (skipping to the next iteration) the for loop whenever the current value is greater than 200, which also skips all corresponding inner nested loops.

This slight detail allows us to skip most of the 1,922,707,710 calculations needed for a complete brute force solution, and returns an answer in a reasonable amount of time.

Answer: 73682

Advertisements

Problem Twenty Six

17 Nov

Here’s problem twenty six:

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

I had to find a clever solution to this problem, mainly because I didn’t know how to brute force it (maybe I should’ve read this). I learn something new everyday, and by solving this problem I discovered a neat application for Fermat’s Little Theorem.

Take a look:

def lengthDecimal(n): # finds length of recurring cycle of 1/n
	while n % 2 == 0:
		n //= 2
	while n % 5 == 0:
		n //= 5
	
	for x in range(1, n):
		if (10**x - 1) % n == 0:
			return x
			
	return 0

result = [0, 0] # number, length

for n in range(2, 1000):
	if lengthDecimal(n) > result[1]:
		result = [n, lengthDecimal(n)]
	
print(result)

Any multiple of 2 or 5 in the denominator will yield the same number of decimal places, so that is the first step of the lengthDecimal() function. If a prime number is in the denominator, we can use a trick based on Fermat’s Little Theorem to calculate the length of the recurring decimal cycle. The application is as follows: 1/n has a cycle of x digits if (10x – 1) % n = 0. Given n, it’s a simple matter of guess and check to find x.

This function is used to test numbers up to 1000.

Answer: 983