There’s an old puzzle that requires the solver to form as many whole numbers as possible, starting with 1, using only the digit 4 exactly four times, together with ordinary arithmetic and algebraic notation.
How far you can get depends on what you mean by “ordinary notation.” Using just decimals, parentheses, concatenation (44), and the symbols for addition, subtraction, multiplication, and division, you can readily reach 20. Allowing other mathematical operations, such as factorial (!) and square root, expands the possibilities.
The “four fours” puzzle has inspired many variants. One is to use the digits of a given year, such as 2004, to generate every number.
In 1999, Erich Friedman of Stetson University in DeLand, Fla., looked at the question of writing a given number in terms of each of the digits from 1 to 9. In his “problem of the month” (see Math Magic at http://www.stetson.edu/~efriedma/mathmagic/archive.html) for December 1999, he asked how many of each digit from 1 to 9 are needed to make the number 2000. The goal was to find the minimum number of copies of a digit needed to make the given number.
For example, using just parentheses, concatenation, addition, subtraction, multiplication, division, and powers, it takes eight 1s to get 2000:
(1 + 1) * (11 – 1)1 + 1 + 1.
You can find answers for other digits at http://www.stetson.edu/~efriedma/mathmagic/1299.html.
What about 2004? That’s the challenge offered by Ed Pegg Jr. of Wolfram Research in Champaign, Ill., last February in his regularly updated commentary on recreational math at http://www.mathpuzzle.com/.
One of those who couldn’t resist tackling the problem was Boris Alexeev, a senior at Cedar Shoals High School in Athens, Ga. He came up with answers for all the digits from 0 to 9, providing the minimal expression for several instances.
For example, Alexeev could write 2004 in terms of five 3s:
333 * 3! + 3!
Some of his shorter answers involved the use of a mathematical function called ceil. The function produces the smallest integer that’s greater than the given number. For example, if the number is 6.04, ceil(6.04) = 7.
Hence, 2004 can be expressed as 6 * 6 * 6 * 6 + 6! – 6 – 6 or, more tersely, ceil[(6 – sqrt(6))6].
As it happens, Alexeev also placed second in this year’s Intel Science Talent Search. His computer science project dealt with the application of automata theory to methods of testing the divisibility of numbers not only in base 10 but also in other bases.
In computer science, an automaton is an abstract machine (or idealized computer) that can serve as a model of computation. A given automaton has a finite set of states, a finite set of input symbols (its alphabet) and outputs, and rules that specify what happens for a given input.
In essence, an automaton starts in some initial state and reads in a string of symbols from its alphabet. Its rules, or transition functions, determine the next state, based on the current state and the symbol just read.
Suppose, for example, that an automaton’s alphabet consists of just 0 and 1. Simple transition rules can be set up to determine if an input string contains, say, an even number of 0s. Or, to decide whether a given string of 1s and 0s is divisible by a certain number, k.
Different automata can often be set up to solve the same problem. One key question is finding the automaton with the smallest possible number of states to do so. Alexeev tackled the task of characterizing minimal “deterministic finite” automata for testing divisibility.
The question boils down to how many states are needed to test whether a certain number is divisible by another, given number. For example, to test whether a number written in decimal digits is divisible by 2, you need check only whether the last digit is even. This involves just two states. Testing binary numbers for divisibility by 16 requires eight states.
Alexeev describes his results in a report to be published in the Journal of Computer and System Sciences.
Deterministic finite automata have applications not only in theoretical computer science but also in many automated devices, from garage door openers to traffic lights. They also provide insights into complex problems, from deciphering the human genome to speech processing and optical character recognition, especially wherever you need to search for patterns and respond to regularities.
