#   
#  Problem statement

We have a fraction in which if we cancel the common digit from the numerator and denominator, the fraction thus obtained is an *equivalent fraction*.
This type of fraction is called a **curious fraction**.

There are indeed only four curious fractions whose actual value is less than one, with two digits in the numerator and denominator.

ex . 49/98 = 4/8

##
## Find the denominator of the product of such fractions when expressed in the lowest terms

## Solution

Suppose the following:
```c++
p/q = original fraction
i = digit to be cancelled
n/d = remaining fraction
```


    


After analyzing, we conclude that: 

   1. Out of four possible conditions, *only the fourth condition will be true for a curious fraction less than one.*

 2. i > d > n

def gcd(a,b):
    b, a= min((a, b)), max((a, b))
    if a%b == 0: return b
    
    # if any of a or b is odd, then we will skip all odd factors
    any_odd = (a|b)%2                   
    hcf = 1
    for j in range(2 + any_odd, b//2 + 1, 1 + any_odd):
        print('checking',j)
        if b%j == 0 and a%j == 0:
            hcf = j
    return hcf

# num/den is the multiplication of all curious fraction less than 1
num = 1
den = 1

# i is digit to be cancelled
for i in range(1, 10):
    # d is remaining digit in denominator
    for d in range(1, i):
        # n is remaining digit in numerator
        for n in range(1, d):
            if 10*n*d + i*d == 10*i*n + d*n:
                num *= 10*n + i
                den *= 10*i + d

common_term = gcd(num, den)

print(den//common_term)

33.py

#include <iostream>
using namespace std;

int gcd(int n, int m) {
    int b = min(n, m);
    int a = max(n, m);
    if (a%b == 0) {
        return b;
    } 
    
    // if any of a or b is odd, then we will skip all odd factors
    int any_odd = (a|b) % 2;              
    int hcf = 1;
    for (int j = 2+any_odd; j < b/2+1;j = j+1+any_odd){
        if (b%j == 0 and a%j == 0){
            hcf=j;
        }
    }
    return hcf;
}


int main()
{   // num/den is the multiplication of all curious fraction less than 1
    int num = 1, den = 1;
    
    // i is the digit to be cancelled
    for (int i=1; i<10; i++) {
        
        // d is remaining digit in denominator
        for (int d=1; d<i; d++) {
            
            // n is remaining digit in numerator
            for (int n=1; n<d; n++) {
                
                if (10*n*d + i*d == 10*i*n + d*n) {
                    num *= 10*n + i;
                    den *= 10*i + d;
                }
            }
        } 
    }
    int common_term = gcd(num,den);
    int answer = den/common_term;

    cout << answer;
    
    return 0;
}

33.cpp

Project Euler 33: digit canceling fractions

Curious fractions under one with two-digit numerators and denominators result in a denominator product expressed in the lowest terms.

Project Euler 33: digit canceling fractions

Problem statement

Find the denominator of the product of such fractions when expressed in the lowest terms

Solution

Analyzing cases

Code