Taxman, also known as Tax Factor, Number Shark, The Factor Game, Factor Blast, Factor Blaster, or Dr. Factor, is a mathematical game invented by mathematician Diane Resek.
Description The game is played between two players on a board consisting of whole numbered tokens labeled 1 through N, where N is any positive whole number. During each turn, one player (deemed the tax payer) takes a number from the board, and the other player (deemed the taxman) removes all remaining factors of the tax payer's number from the board. The game ends when there are no legal moves left, and each player's score is calculated by adding up the values of the numbers they have collected. The player with the highest score wins.
Single-player version
In the single-player version, (Taxman, Tax Factor, Number Shark), the human player assumes the role of the tax payer each turn while the computer player is always the taxman. In addition, the human player may only collect a number that still has proper factors remaining on the board. When there are no legal moves left, the taxman collects all of the remaining tokens on the board.
Two-player versions
In all two-player versions of the game, (The Factor Game, Factor Blast, Factor Blaster, Dr. Factor), the two players swap roles each turn, so that whoever is playing as the taxman during one turn will be the tax payer during the next turn, and vice versa.
In some versions, the tax payer may only collect a number that still has proper factors remaining on the board. If a player picks a number incorrectly, they may or may not lose their next turn, and they may or may not keep the number. In some versions, the taxman may neglect to collect all of the factors of the tax payer's number, or may attempt to collect a factor incorrectly. The taxman may or may not lose points for missing factors or choosing incorrectly, and the tax payer may or may not be able to steal a factor that the taxman misses. In some versions, there is the option to remove one or more numbers from the board before the game starts.
Origin and spread
Taxman was invented by Resek sometime in the late 60's or early 70's while working at the Lawrence Hall of Science. It was published as a BASIC program in the September 1973 issue of the People's Computer Company Newsletter, and later appeared in the 1975 programming anthology book What to Do After You Hit Return.
In 1980, Taxman appeared as part of the software collection MECC - Elementary Volume 1 for the Apple II. The concept was later reused in other MECC titles, such as Wonderland Puzzles (as Hedgehog Croquet) and The Secret Island of Dr. Quandary (as Tax Factor) in 1992.
Starting in 1984, Taxman appeared as a coding exercise in a series of programming textbooks written by Lowell Carmony, a professor at Lake Forest College (and Berkeley alumnus). Carmony was part of the writing group for the 1993 NRC publication Measuring Up: Prototypes for Mathematics Assessment, which included Taxman as one of its prototypes. Carmony also described Taxman in an article for SIGCSE.
In 1996, a list of the best possible scores in Taxman, (called the Taxman sequence), was uploaded to the On-Line Encyclopedia of Integer Sequences. As of 2022, the sequence has been calculated out to a board size of 1000.
Around 2000, a version of Taxman was uploaded to the NRW's learn:line educational server under the name Der Zahlenhai (or Number Shark in English). A version of Number Shark was later added to CrypTool in 2006.
In 2015, Taxman appeared in the New York Times' Numberplay column as The Tax Collector.
Two-player versions
A two-player version of Taxman, known simply as The Factor Game, was described in an article for the November 1973 issue of The Arithmetic Teacher, a publication of the National Council of Teachers of Mathematics. The article was later reprinted in the 1975 anthology Games and Puzzles for Elementary and Middle School Mathematics.
In 1983, Factor Blast by Joe DeMuth was published by Hayden Software. Around 2000, educator Terry Kawas developed teaching materials for a similar variant called Factor Blaster which was later uploaded to Mathwire, a math education resource website.
In 1985, Dr. Factor appeared as one of four games in Playing To Learn by Antonia Stone, Joshua Abrams, and Ihor Charischak of HRM Software.
In 1986, another variant, also called The Factor Game, appeared as the first activity in the Factors and Multiples module of the Middle Grades Mathematics Project curriculum, and later appeared as part of the Connected Mathematics Project in 1996. Interactive versions were developed for Macintosh and Windows, and eventually a web version was developed for the NCTM's Illuminations website in 2001.
In education
Taxman and its variants have been studied and used as tools in mathematics and computer science education.
O'Brien used Taxman and another computer game to "foster the development of higher-level thinking skills in children". Harkin and Martin describe using the two-player version of Taxman, which they called "the factor game", to involve students with concepts of prime and composite numbers, and to apply the fundamental theorem of arithmetic. Researchers at Michigan State University also used the factor game, together with the Sieve of Eratosthenes, to help improve the quality of arithmetic instruction for middle-school students.
Carmony and Holliday proposed using the one-player game to teach concepts in algorithm design and data structures. They examined the data structures needed to program the Taxman game, and then explored adding intelligence to allow the program to play the game. Trono describes using the Taxman game as an assignment in a CS2 programming course, dividing the students into teams that each devised a different strategy and competed to find the one that performed best.
Analysis
The winnability, strategy, and optimal score for the single-player version of Taxman have been studied.
First we can make some elementary observations. Taxman is a zero-sum game, in which the player and the taxman divide a total between them equal to the sum of the numbers from 1 to N, which is N(N+1)/2. To win the game, the player must get a score equal to more than half that sum.
It is easy to see that the best first move is to take the largest prime on the board. Taking it gives the taxman only the number 1, which he will take on the first move anyway, rendering all remaining primes unpickable. Taking the largest prime does not prevent any later picks that could be made, since it has no multiples on the board.
An absolute upper limit to the player's score can be found as follows. Since the taxman must take at least one number on every turn, the best the player can do is to take as many numbers as the taxman, and take them all from the upper half of the range, greater than N/2, leaving the lower half to the taxman. Some simple algebra shows that the sum of these numbers approaches, but is always less than, 3/4 of the total available points. For N=10, the player is able to do this, taking 40 of the available 55 points, or about 73%. For N>10, it is not possible for the player to take all of the numbers above N/2, since some of them inevitably become unpickable as their divisors are taken by the taxman. Because of this, the optimal score for large N is always significantly below this bound. For N ≤ 1000, the average value of the optimal score as a fraction of the available points is found to be about 63%.
Although finding the optimal play for one-player Taxman is probably NP-hard, and therefore prohibitive to compute for large values of N, winning strategies that are efficient to compute have been published. Hensley, approaching the problem from a number-theory perspective, devised a divide-and-conquer algorithm which he showed wins for large enough values of N. However, he was unable to determine a minimum value of N above which the strategy would always win. Perlmutter devised a sequence of clever picks, also based on number theory, that provably wins for sufficiently large N, but he too was unable to determine the minimum value of N to guarantee winning. Finally, Franklin and Moniot, treating the game as a graph theory problem, obtained a strategy that they proved wins for all N except 1 and 3 (which are not winnable). These proven winning strategies are not readily computed mentally by a human player. Other strategies have been found that are relatively easy for the player to use and that are observed to win, at least most of the time.
Carmony and Holliday explored several heuristic strategies for winning the game. One of them, a greedy algorithm called MaxTurn, picks the number that maximizes the difference between the player's take (the chosen number) and the taxman's take (the sum of the remaining unplayed divisors of the chosen number) on each turn. It reliably gets a good, though not necessarily optimal, score. Trono published a short analysis of the Taxman game, comparing various simple strategies, including MaxTurn.
Moniot used the Taxman game to illustrate concepts in computational complexity theory and brute-force tree search algorithms with pruning. The results suggested that the time required to find the optimal play increases exponentially with N. Franklin and Moniot showed that the problem of finding optimal play is similar to a problem that has been proved to be NP-complete, suggesting that optimal Taxman is probably NP-hard. Nonetheless, Chess has made substantial progress on finding optimal move sequences and optimal scores. Currently the optimal score and move sequence are known out to N = 1000. He has exploited the fact that for many cases, the optimal play for N can be quickly derived from that for N - 1. An example of this is when N is prime: then the optimal play is found simply by replacing the first move, which was the largest prime less than or equal to N - 1, by the new largest prime, N. Also, the maximum score for N cannot be larger than N plus the maximum score for N - 1. Considerations like these allow the search space to be pruned considerably.
Franklin and Moniot also found efficient algorithms for computing tight upper and lower bounds on the optimal score. The lower-bound algorithm yields a playable sequence that is observed to perform quite well.
References
External links
The Factor Game on the NCTM's Illuminations website