# An interesting problem with fractions

These are a few examples of how "forbidden" procedures can lead us to the correct answer:

$$\displaystyle\frac{1\not4^1}{2\not8_2} = \frac{11}{22}=\frac{1}{2}$$

$$\displaystyle\frac{1\not3^1}{3\not9_3} = \frac{11}{33}=\frac{1}{3}$$

$$\displaystyle\frac{{\not3^1}0}{{\not6_2}0} = \frac{10}{20}=\frac{1}{2}$$

I am interested in the question does there exist a fraction such that it satisfies these $5$ requirements and such that it can be "solved" using this "technique"?

1. The numerator and denominator have $n$ digits where $5\leq n\leq9$
2. The number in numerator doesnt end in $0$.
3. The number in denominator deosn´t end in $0$.
4. All digits in number in numerator are different.
5. All digits in number in denominator are different.

EDIT1: The user found that it is possible for $n=5$, now I have a somewhat different version of the problem with modified first requirement:

1*. The numerator and denominator have $n$ digits where $6\leq n\leq9$

2.,3.,4.,5. Same as above.

I believe that now such fraction doesnt exist and would be very pleased if someone shows that it is so or finds a counterexample in any of these two cases:

Case A) Only one cancellation is allowed.

Case B) More than one cancellation is allowed.

EDIT2: It seems that belief in non-existence of such fraction in the modified problem $6\leq n\leq9$ was a failure, below you can see that user Ivan Loh found the solution for the cases $n=6,7$ with one cancellation and solution for the case $n=8$ with two cancellations which is indeed more than I was asking, and, following his examples, I found the case for $n=8$ with one cancellation, it is $\displaystyle\frac {21945703}{65837109}=\frac {21945701}{65837103}=\frac {1}{3}$.

-

In case you still want a 5 digit example:

$$\frac{14573}{43719}=\frac{14571}{43713}=\frac{1}{3}$$

A 6 digit example:

$$\frac{194573}{583719}=\frac{194571}{583713}=\frac{1}{3}$$

In fact, let's add a $0$, so

$$\frac{1945703}{5837109}=\frac{1945701}{5837103}=\frac{1}{3}$$

If you want more than 1 cancellation, use

$$\frac{19457023}{58371069}=\frac{19457011}{58371033}=\frac{1}{3}$$

-
Amazing! Thank you! – user67878 Mar 22 '13 at 15:18
May I ask how did you find these? Brute force? Some algorithm? Algebra? – YatharthROCK Mar 23 '13 at 17:33
@YatharthROCK I was searching for a fraction satisfying the given restrictions and an additional one: Digits which do not cancel are relatively prime. The reason was because fractions like $$\frac{1234567809}{1234567809}=\frac{1234567801}{1234567801}=\frac{1}{1}$$ did not seem nice enough. With this additional restriction in mind, we clearly are not going to have much luck with $\frac{1}{1}$ or $\frac{1}{2}$. I next tried fractions which reduce to $\frac{1}{3}$, and with a bit of trial and error, got the 5 digit example. All other examples came from trying to add digits to that example. – Ivan Loh Mar 24 '13 at 4:07

5 digit numbers using more than one cancellations:

$$\frac{43201}{86402} = \frac{11101}{22202} = \frac{1}{2}$$

-
Only one cancellation is allowed, i forgot to mention that, I will edit the question now, but you have proved that if more than one cancellation is allowed then the answer is affirmative, well done! – user67878 Mar 22 '13 at 14:39
@Thus: You can choose to cancel in any or all of the four nonzero positions alone, and it will still work. (The point requirement for this to work is simply that there's no carry either into the position or out of it when calculating $43201\times 2$). – Henning Makholm Mar 22 '13 at 14:47
Isn't requiring it to cancel in just one step a WEAKER condition? – Sean Ballentine Mar 22 '13 at 14:49
Brilliant! I didn´t actually see it. – user67878 Mar 22 '13 at 14:50
@Thus even if you require the fraction to have only 1 possible cancellation (all other digits cannot cancel), it is still possible. – Ivan Loh Mar 22 '13 at 14:52

These are known as howlers. Not all fractions obey these laws.

For more info on how to generate them, look at this Dr. Math post.

For the example you need $\frac{31402}{62804}=\frac{1}{2}$.

-
I know that majority of them doesnt obey this law, but I want to know if there exist at least one fraction that follows above mentioned requirements such that it obeys the law. Thank you for the information. It also can be seen that this requirements significantly reduce the number of all possible combinations. – user67878 Mar 22 '13 at 14:35
Feel free to do it! :) – user67878 Mar 22 '13 at 15:07

I wrote some code to generate these kind of fractions. It's written in Python, so it's practically like pseudocode. Basically, I just brute-force over all numbers and simply validate whether it is a Howler fraction or not.

# -*- coding: utf-8 -*-
from fractions import Fraction, gcd

def digitify(x):
return list(str(x))

def intify(digits):
return int(float(''.join(map(lambda digit: str(digit), digits))))

def primes(max_ = None, req = None):
x = 2
while True:
composite = None
for divisor in range(2, x // 2):
if (x % divisor) == 0:
composite = True
break
if not composite:
yield x
x += 1

def factorize(x):
factors = []
x = int(x)

for prime in primes():
if x == 0 or x == 1:
break

if x % prime == 0:
factors.append(prime)
while x % prime == 0:
x /= prime

return factors

def validate(num, den, strict=False):
frac = Fraction(num, den)
num = digitify(num)
den = digitify(den)

# cancel last digits
if (not strict) or (gcd(intify(num[:-1]), intify(den[:-1])) == 1):
factors = factorize(gcd(int(num[-1]), int(den[-1])))
for factor in factors:
num_ = intify(num[:-1] + [int(num[-1]) / factor])
den_ = intify(den[:-1] + [int(den[-1]) / factor])
frac_ = Fraction(num_, den_)
if frac_ == frac:
return frac_

# cancel first digits
if (not strict) or (gcd(intify(num[1:]), intify(den[1:])) == 1):
factors = factorize(gcd(int(num[0]), int(den[0])))
for factor in factors:
num_ = intify([int(num[0]) / factor] + num[1:])
den_ = intify([int(den[0]) / factor] + den[1:])
frac_ = Fraction(num_, den_)
if frac_ == frac:
return frac_

def find(n):
start = 10 ** (n-1)
stop = 10**n + 1

for x in range(start, stop):
for y in range(start, stop):
if x == y:
continue
frac = validate(x, y)
if frac:
print(x, y, frac)


Executing $find(n)$ provides you with all the Howler fractions of size $n$, though it takes a bit if time to compute them all.

I improvised the algorithm a bit. Now, it takes a fraction finds valid equivalent fractions with the added restriction that the :

def find(frac):
num = frac.numerator
den = frac.denominator
x = 1

while True:
x += 1
num_ = num * x
den_ = den * x
frac = validate(num_, den_, strict=True)
if frac:
print(num_, den_, frac)
`

This gives more Howler fractions in significantly less time, although you can't find fractions of length $n$ upfront.

I ran the code on my machine but as soon as I started to paste the output on SE or any pastebin, Chrome froze. But you can run the code on your machine and try (It's Python 3 BTW).

Update: First few fractions of length 5 are here;

-
+1 for the effort! – user67878 Mar 24 '13 at 13:39
@Thus I really wish I had a machine and this retarded GIL would go away from Python, then I could give you results. trying to leverage AppEngine now... – YatharthROCK Mar 25 '13 at 10:04