The task in Problem 33 of Project Euler is:
The fraction $\frac{49}{98}$ is a curious fraction, as an inexperienced mathematician in attempting to simplify it may incorrectly believe that $\frac{49}{98} = \frac{4}{8}$, which is correct, is obtained by cancelling the 9s. We shall consider fractions like, $\frac{30}{50} = \frac{3}{5}$, to be trivial examples. There are exactly four non-trivial examples of this type of fraction, less than one in value, and containing two digits in the numerator and denominator. If the product of these four fractions is given in its lowest common terms, find the value of the denominator.
How to solve
The solution to this task is pretty straight forward. As the nominator has to have two digits and the denominator also has to be in [10, 99], we only have about \(100 \cdot 100 = 10000\) that we have to check.
How do we check a given nominator / denominator pair? Well, we can go through each digit of the nominator and check if it is also in the denominator. If it is there, we have to check if the resulting fraction has the same value as before. If it has, we can print it.
My solution
#!/usr/bin/env python
# -*- coding: utf-8 -*-
def isCuriousFraction(numerator, denomiator):
for digit in str(numerator):
if digit in str(denomiator):
for i, j in [(i, j) for i in range(0, 2) for j in range(0, 2)]:
if str(numerator)[i] == digit == str(denomiator)[j]:
if int(str(denomiator)[(j + 1) % 2]) == 0:
continue # devision through 0 is bad
canceled = float(str(numerator)[(i + 1) % 2]) / int(
str(denomiator)[(j + 1) % 2]
)
divided = float(numerator) / denomiator
if abs(canceled - divided) < 0.0001:
print(
"%i/%i = %s/%s"
% (
numerator,
denomiator,
str(numerator)[(i + 1) % 2],
str(denomiator)[(j + 1) % 2],
)
)
return True
if __name__ == "__main__":
for i in range(10, 100):
if i % 10 == 0: # those are not interesting
continue
for j in range(i + 1, 100):
isCuriousFraction(i, j)
Solving it without programming
You can also solve this without programming at all: See post.