Ivars Peterson's MathTrek
April 12, 2004
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 symbols, 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? Ed Pegg Jr. of Wolfram Research in Champaign, Ill., offered the challenge of expressing this number by using a minimal number of some digit 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 and output symbols (its alphabet), 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.
Copyright © 2004 by Ivars Peterson
Alexeev, B. In press. Minimal DFAs for testing divisibility. Journal of Computer and System Sciences. Preprint available at http://arxiv.org/PS_cache/cs/pdf/0309/0309052.pdf.
Ball, W.W.R., and H.S.M. Coxeter. 1974. Mathematical Recreations & Essaysth ed. Toronto: University of Toronto Press.
Gardner, M. 1967. The Numerology of Dr. Matrix. New York: Simon and Schuster.
Pegg Jr., E. 2004. Number games. MAA Online (March 1).
Erich Friedman's monthly math puzzles can be found at http://www.stetson.edu/~efriedma/mathmagic/.
Ed Pegg's ongoing commentary on recreational math is available at http://www.mathpuzzle.com/.
A brief biography of Boris Alexeev can be found at http://www.sciserv.org/sts/63sts/Alexeev.asp. Additional information about the 2004 Intel Science Talent Search is available at http://www.sciserv.org/sts/.
Comments are welcome. Please send messages to Ivars Peterson at email@example.com.
A collection of Ivars Peterson's early MathTrek articles, updated and illustrated, is now available as the Mathematical Association of America (MAA) book Mathematical Treks: From Surreal Numbers to Magic Circles. See http://www.maa.org/pubs/books/mtr.html.