• Martin Thoma
  • Home
  • Categories
  • Tags
  • Archives
  • Support me

Project Euler: Problem 33

Contents

  • Project Euler: Problem 33
    • How to solve
    • My solution
    • Solving it without programming

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.


Published

Nov 14, 2012
by Martin Thoma

Category

Code

Tags

  • Challenge 7
  • Programming 52
  • Project Euler 9
  • Python 141

Contact

  • Martin Thoma - A blog about Code, the Web and Cyberculture
  • E-mail subscription
  • RSS-Feed
  • Privacy/Datenschutzerklärung
  • Impressum
  • Powered by Pelican. Theme: Elegant by Talha Mansoor