Automated Generation of Anomalous Cancellations

Shalosh B. EKHAD

(with a Foreword by Doron Zeilberger)

Foreword (By Doron Zeilberger)

In my last visit to Israel I bought a wonderful “popular” book [Sh], by the great expositor Haim Shapira, on game theory. There he mentions (p. 156) how clueless students are. Once, during a course on probability given in the Faculty of Engineering, he solved a problem whose answer happened to be

\frac{16}{64} .

He ‘simplified’ it, “cancelling out” the the digit 6:

\frac{1 6̸}{6̸4} = \frac{1}{4} ,

getting the right answer. Shapira went on to say that he hopes that none of his readers reduces fractions this way, and raised two questions, one to psychologists and one to mathematicians. The question to psychologists was: “How come no (engineering!) student commented on this ‘simplification’ for more than a minute and a half?”. The question to mathematicians was: “Can you make up more examples of this phenomenon?”.

Not being a psychologist, I tried to focus on the second question. When I got back home, I asked Neil Sloane whether he has seen this before, and, sure enough, he knew about this phenomenon, and referred me to sequence A159975 and a few other related sequences in the On Line Encyclopedia of Integer Sequences [Sl], that, in turn, referred me to a wonderful article [B] by the great analyst (who was also a great expositor!) Ralph Philip Boas.

In that article, Boas discusses the problem of finding such examples, in any given base. He derived some complicated non-linear diophantine equations.

But why think so hard? If, given a base b, and positive integers d_{1} and d_{2}, as well as the locations of the ‘cancelled’ digits, i_{1} and i_{2}, (0 ≤ i_{1} < d_{1} and 0 ≤ i_{2} < d_{2}), you are interested, in finding the set of all fractions

\frac{m}{n} ,

written in base b, where m and n are with d_{1} and d_{2} digits, respectively, and where the illegal cancellation of the i_{1}-th digit of the numerator and i_{2}-th digit of the denominator gives you the same ratio, it suffices to generate all (b^{d_{1}} − b^{d_{1}−1}) (b^{d_{2}} − b^{d_{2}−1}) such fractions and see which ones work out. Alas, this takes too long, even nowadays, if you want to go anywhere far.

The compromise between being too clever and being too dumb, is to fix the denominator, n, and places 0 ≤ i_{1}, i_{2} ≤ d_{2} − 1, and ask for a “clever” way to find all numerators m (of any size!) such that if you ‘cancel out’ the i_{1}-th digit of the top with the the i_{2}-th digit of the bottom, you get the same thing. This leads to a linear diophantine equation, that is very easy to solve, thanks to the Extended Euclidean Algorithm. Don Knuth ([K], p. 318, lines 5-6) calls the (unextended) Euclidean algorithm the granddaddy of all algorithms, and then goes on to comment, that, most likely, it is not due to Euclid (he only wrote it up in his textbook), and his ‘proof’ of validity was not quite up to his usual standards, since he lacked the concept of induction.

The Extended Euclidean Algorithm is a simple by-product of the Euclidean algorithm, and in addition to supplying the greatest common divisor of A and B

C = gcd(A, B) ,

it also outputs integers x and y such that

A x + B y = C .

See [K], pp. 325-327, for a very nice and detailed account, in Knuth’s inimitable style. According to an internet search, the Extended Euclidean Algorithm was first published by Roger Cotes (1682-1716) who used it to compute continued fractions.

So let’s describe an algorithm that

inputs

• A base b ;

• A positive integer n, written in base b, of d_{2} digits, say (so b^{d_{2}−1} ≤ n < b^{d_{2}}) ;

• Integers i_{1}, i_{2} satisfying 0 ≤ i_{1}, i_{2} ≤ d_{2} − 1 ;

and

outputs

• The set of all positive integers m (of any size) such that if m is written in base b, the i_{1}-th digit of m is the same as the i_{2}-th digit of n, and removing that common digit from both m and n does not alter the ratio.

Since the denominator n is assumed known, and we are singling out its i_{2}-th digit, let’s call it c (0 ≤ c ≤ b − 1), we can express it as

n = N_{1} · b^{i_{2}+1} + c · b^{i_{2}} + N_{2} , 1 ≤ N_{1} ≤ b^{d_{2}−i_{2}−1} − 1 , 0 ≤ N_{2} ≤ b^{i_{2}} − 1 .

We are looking for integers m

m = M_{1} · b^{i_{1}+1} + c · b^{i_{1}} + M_{2} , 0 ≤ M_{1} , 0 ≤ M_{2} ≤ b^{i_{1}} − 1 ,

such that

\frac{M_{1} · b^{i_{1}+1} + c · b^{i_{1}} + M_{2}}{N_{1} · b^{i_{2}+1} + c · b^{i_{2}} + N_{2}} = \frac{M_{1} · b^{i_{1}} + M_{2}}{N_{1} · b^{i_{2}} + N_{2}} .

Cross-multiplying, this leads to a certain linear diophantine equation of the form

A M_{1} + B M_{2} = C ,

for some specific integers A, B, C (derivable from above), and unknowns M_{1}, M_{2}. If C is not divisible by gcd(A, B), then there is no solution of course. On the other hand, if C is divisible by gcd(A, B), let A_{1} = \frac{A}{gcd(A,B)}, B_{1} = \frac{B}{gcd(A,B)}, C_{1} = \frac{C}{gcd(A,B)}, and we get

A_{1} M_{1} + B_{1} M_{2} = C_{1} ,

where gcd(A_{1}, B_{1}) = 1. Using the Extended Euclidean algorithm, we manufacture a pair of integers (M_{1}^{(0)}, M_{2}^{(0)}) such that

A_{1} M_{1}^{(0)} + B_{1} M_{2}^{(0)} = 1 ,

from which we get the general solution

M_{1} = C_{1} M_{1}^{(0)} + B_{1} t , M_{2} = C_{1} M_{2}^{(0)} − A_{1} t.

We then look for all t that make M_{2} between 0 and b^{i1} − 1. The Maple package All this is implemented in the Maple package AnomalousCancellation.txt, available directly from

http://sites.math.rutgers.edu/~zeilberg/tokhniot/AnomalousCancellation.txt ,

or via the webpage of this article

http://sites.math.rutgers.edu/~zeilberg/mamarim/mamarimhtml/anomalous.html ,

where there are several input and outputs files. For example, for a list of all such anomalous cancellations where the denominator is ≤ 9999 (in our own base ten) see

http://sites.math.rutgers.edu/~zeilberg/mamarim/mamarimPDF/ac4.pdf ,

while for an extension of Boas’ tables in pp. 119-122 of [B] see

http://sites.math.rutgers.edu/~zeilberg/tokhniot/oAnomalousCancellation2.txt .

The above web-page has other output files, but readers who have Maple can use the Maple package AnomalousCancellation.txt to get as many more examples as they wish.

References

[B] R. P. Boas, Anomalous Cancellation, in: Ch. 6 (pp. 113-129) in “Mathematical Plums”, Ross Honsberger, ed., Dolciani Mathematical Expositions, Mathematical Association of America, 1979.

[K] Donald E. Knuth, “The Art of Computer Programming” vol. 2, Seminumerical algorithms, 2nd ed., Addison-Wesley, 1981.

[Sh] Haim Shapira, “Conversations on Game Theory” (in Hebrew), Kinneret, Zmora-Bitan, Dvir, 2008.

[Sl] N. J. A. Sloane, The On Line Encyclopedia of Integer Sequences, https://oeis.org .

Shalosh B. Ekhad, c/o D. Zeilberger, Department of Mathematics, Rutgers University (New Brunswick), Hill Center-Busch Campus, 110 Frelinghuysen Rd., Piscataway, NJ 08854-8019, USA.

ShaloshBEkhad at gmail dot com .

Exclusively published in the Personal Journal of Shalosh B. Ekhad and Doron Zeilberger and arxiv.org .