Multiple choice: which of the following equations are correct?

  1. $$6 \times 9 = 54$$

  2. $$6 \times 9 = 46$$

  3. $$6 \times 9 = 42$$

  4. $$6 \times 9 = 39$$

You may probably be surprised when we state that all of them are correct, as long as they are evaluated in the correct numeral system. The decimal system is the most commonly used numeral system in the Western world. In this system, the digits of a number have a numerical value that is a power of 10. As such, the number $$abc$$ is interpreted as $$c$$ + $$10 \times b$$ + $$10^2 \times a$$ and the ten digits $$0\ldots 9$$ are used. In the binary numeral system, numerical values are powers of two and only the digits $$0$$ and $$1$$ are used. Hence, the number $$abc$$ is interpreted in the binary numeral system (base 2) as $$c$$ + $$2 \times b$$ + $$2^2 \times a$$. In numeral systems with base $$10 < b \leq 36$$, aside from the arabic digits $$0, 1, \ldots, 9$$ also the letters of the alphabet $$A, B, \ldots, Z$$ are used as digits. The latter then correspond to the values $$10, 11, \ldots, 35$$. In this case, no distinction is made between upper case and lower case letters. 

When we now return to the equations above, we see that the second equation is valid in the numeral system with base 12, the third in the numeral system with base 13 and the fourth in the numeral system with base 15.

A hitchhiker's guide to the galaxy

The fact that $$6 \times 9 = 42$$ is a valid equation in the numeral system with base 13 is well-known among science fiction fans that have read the books in "The Hitchhiker's Guide to the Galaxy" series (or have watched the movies). In this comic series by Douglas Adams, a group of hyper-intelligent pan-dimensional beings had built a supercomputer — Deep Tought — that was demanded to learn the Answer to the Ultimate Question of Life, the Universe and Everything. After having computed for 7½ million years, the supercomputer finally came up with the answer, which turned out to be $$42$$. Deep Thought pointed out that the answer seems meaningless because the beings who instructed it never actually knew what the Question was.

When asked to produce The Ultimate Question, Deep Thought says that it cannot; however, it can help to design an even more powerful computer that can. This new computer will incorporate living beings into the "computational matrix" and will run for ten million years. It is revealed as being the planet Earth, with its pan-dimensional creators assuming the form of mice to observe its running. The process is hindered after eight million years by the unexpected arrival on Earth of the Golgafrinchans and then is ruined completely, five minutes before completion, when the Earth is destroyed by the Vogons to make way for a new Hyperspace Bypass. In The Restaurant at the End of the Universe, this is revealed to have been a ruse: the Vogons had been hired to destroy the Earth by a consortium of psychiatrists, led by Gag Halfrunt, who feared for the loss of their careers when the meaning of life became known.

Lacking a real question, the mice decide not to go through the whole thing again and settle for the out-of-thin-air suggestion "How many roads must a man walk down?" from Bob Dylan's song "Blowin' in the Wind". At the end of the story, Arthur Dent, having escaped the Earth's destruction, potentially has some of the computational matrix in his brain. He attempts to discover The Ultimate Question by extracting it from his brainwave patterns, as abusively suggested by Ford Prefect, when a Scrabble-playing caveman spells out forty two. Arthur pulls random letters from a bag, but only gets the sentence "What do you get if you multiply six by nine?"

"Six by nine. Forty two."
"That's it. That's all there is."
"I always thought something was fundamentally wrong with the universe"

Six times nine is actually fifty-four. The program on the "Earth computer" should have run correctly, but the unexpected arrival of the Golgafrinchans on prehistoric Earth caused input errors into the system — computing (because of the garbage in, garbage out rule) the wrong question — the question in Arthur's subconscious being invalid all along. Some readers noticed that $$(6 \times 9 = 42)_{13}$$ (using base 13). Douglas Adams later joked about this observation, saying, "I may be a sorry case, but I don't write jokes in base 13."

Assignment

The goal of this exercise is to find the smallest possible base $$b \leq 36$$ for which a given equation is valid. You may assume that equations only contain digits, brackets, + and *. In order to do so, you should proceed as follows:

Preparation

Python has a built-in function eval that can be used to evaluate the string representation of an expression that is passed as an argument to the function. This evaluation function always interprets the expression in the decimal numeral system. The built-in function int can be used to convert the string representation of an integer in a numeral system with base $$b$$ into the corresponding integer in the decimal numeral system. Use the optional second argument (base) to pass the base of the numeral system to the function int.

>>> eval('12 * 3 + 6')
42
>>> int('2C', base=15)
42

Example

>>> evaluation('6 * 9', 13)
54
>>> evaluation('42', 13)
54
>>> evaluation('17 + 33 * 56', 23)
8742
>>> evaluation('41 * 42', 23)
8742

>>> numeralSystem('6 * 9 = 42')
13
>>> numeralSystem('17 + 33 * 56 = 41 * 42')
23