
Minimum (Number Theory Game)
Minimum (Number Theory Game)
In spring 1983 a couple of school friends asked me to define a number theory game that has very simple rules, but is also very complex. So in April 1983 I defined the number theory game Minimum, which I would like to introduce to you in this thread.
When I started to work on defining the Minimum game at Easter 1983, it was clear to me that I had to use additive and multiplicative components at the same time, because in number theory in general the complexity increases very sharply as soon as additive and multiplicative elements are used combined with each other.
Rules of the game Minimum
1. At the beginning of the game, any natural number > = 2 is drawn. The number of decimal digits of n is determined in advance and should be between 10 and 60.
2. Each player tries to get from the number n to the number 2 with a series of arithmetic steps, independently of all other players, within the given time. Only paper and pen are permitted as aids. The time to think is six minutes per decimal digit of the drawn number, i.e. between one and six hours.
3. In a calculation step, the player replaces n with n + 1 (addition step), with n  1 (subtraction step) or with n / d, where d is a divisor of n and at the same time d <= (n ^ 0.5) . If a player has reached the number 2, his game is over. The player has to record all calculation steps in full.
4. Each addition step and each subtraction step costs one move. Division steps are free.
5. The player who took fewer moves to get from n to 2 wins. If the number of moves is the same, the game ends in a draw. Anyone who miscalculates or exceeds the time to think will be treated as if they had only used subtraction steps after the last correct intermediate number.
6. If there are more than two players, everyone is compared to everyone else; a point is awarded for a win and half a point for a draw.
An example: The number 13356 was drawn.
Player A plays as follows:
13356 : 12
1113: 21
53 + 1
54 : 6
9 : 3
3  1
2
Player A therefore needs 2 moves to get from n (here 13356) to 2.
Player B plays as follows:
13356 : 7
1908 : 3
636 : 4
159 + 1
160 : 10
16 : 4
4 : 2
2
B only needs one move to get from n (here 13356) to 2. So A lost and B won, so the result is 0 : 1.
In computer science it is now relevant if a player plays infinitely well, i.e. does not make a mistake in order to get from n to 2. If you analyze the number 13356 you will find out that with an infinitely good game you don't need a move to get to the number 2.
13356 : 53
252 : 7
36 : 3
12 : 3
4 : 2
2
In minimum theory, the minimum number of moves that one needs to get from n to 2 is called the value of n.
Numbers with the value 0 are called Nullwertzahlen (Zerovalue numbers).
Numbers with the value 1 are called Einswertzahlen (Onevalue numbers).
Numbers with the value 2 are called Zweiwertzahlen (Twovalue numbers).
Numbers with the value 3 are called Dreiwertzahlen (Threevalue numbers).
Numbers with the value 4 are called Vierwertzahlen (Fourvalue numbers).
W(n) denotes the value of n, so W(12) = 0 means that 12 is a Nullwertzahl (zerovalue number).
W_{0}(n) denotes the number of all Nullwertzahlen (zerovalue numbers) less than or equal to n.
For example
W_{0}(100) = 17
W_{1}(100) = 71
W_{2}(100) = 11
The values of the first 20 numbers are as follows
W(1) = not defined
W(2) = 0
W(3) = 1
W(4) = 0
W(5) = 1
W(6) = 1
W(7) = 1
W(8) = 0
W(9) = 1
W(10) = 1
W(11) = 1
W(12) = 0
W(13) = 1
W(14) = 1
W(15) = 1
W(16) = 0
W(17) = 1
W(18) = 1
W(19) = 2
W(20) = 1
_______________________________
W_{0}(n) denotes the number of all Nullwertzahlen that are less than or equal to n.
W_{1}(n) denotes the number of all Einswertzahlen that are less than or equal to n.
W_{2}(n) denotes the number of all Zweiwertzahlen that are less than or equal to n.
W_{3}(n) denotes the number of all Dreiwertzahlen that are less than or equal to n.
W_{4}(n) denotes the number of all Vierwertzahlen that are less than or equal to n.
W (n) = 0 if and only if, when
n = p1 * p2 * p3 * p4 * p5 *...* pk, where pi are primes with p1 <= p2 <= p3 <= p4 ...; then p1 = 2 and p1*p2*...*pi >= p(i+1) for all i < k.
See also A047836 OEIS.
The Nullwertzahlen (zerovalued numbers) are comparable to the prime numbers in many ways, but often behave exactly the opposite of what the prime numbers do.
There are 17 Nullwertzahlen (zerovalued numbers) up to 100:
2, 4, 8, 12, 16, 24, 32, 36, 40, 48, 56, 60, 64, 72, 80, 84, 96.
For example, it is assumed that W_{0} (n) / pi (n) = C
C is on the order of about 0.61.
For example
W_{0}(10^{12}) = 22996137423
pi(10^{12}) = 37607912018
In 2003 we did a minimum total analysis up to 10^{12} and calculated the values and number of all numbers: At that time ten Pentium IV computers with 3.06 GHz each were in use around the clock at the same time; 1.6 GB of RAM were available on each computer. The total computing time for the total analysis up to 10 ^ 12 was 4937859 seconds, i.e. about 57 days.
Here are a few results
W_{0}(10^{12}) = 22996137423
W_{1}(10^{12}) = 541664112990
W_{2}(10^{12}) = 425608837164
W_{3}(10^{12}) = 9730782305
W_{4}(10^{12}) = 130117
The sum is not 10^{12}, but 10^{12} 1 because the value of 1 is not defined.
So up to 10 ^ 12 there are 22996137423 Nullwertzahlen, 541664112990 Einswertzahlen, 425608837164 Zweiwertzahlen, 9730782305 Dreiwertzahlen and 130117 Vierwertzahlen, but not a single Fünfwertzahl. We expect the smallest Fünfwertzahl to be around 10^{18} and the smallest sixvalued number at 10^{49}.
The longest chain of consecutive Einswertzahlen (onevalue numbers) has the length 47. It runs from 364964597713 to 364964597759 and is limited by two Nullwertzahlen (zerovalue numbers).
The longest chain of consecutive Zweiwertzahlen (twovalue numbers) has the length 31. It runs from 237809823890 to237809823920 and is limited by a Einswertzahl and a Dreiwertzahl.
The longest chain of consecutive Dreiwertzahlen (onevalue numbers) has the length 8. It runs from 635373605583 to 635373605590 and is limited by two Zweiwertzahlen (twovalue numbers).
The greatest distance between two consecutive Nullwertzahlen (zerovalued numbers) is 780. There is no other Nullwertzahl zerovalued number between the two Nullwertzahlen (zerovalued numbers) 763896600180 and 763896600960.
The function W (n) behaves very chaotically. Sometimes the function jumps back and forth between the function values 1 and 2, sometimes also between the function values 2 and 3. At other points, onevalue twins and twovalue twins alternate, i.e. 1, 1, 2, 2, 1, 1, 2, 2 , sometimes there is a waltz measure 1, 2, 2, 1, 2, 2 or 2, 3, 3, 2, 3, 3 and sometimes no recognizable pattern at all. The only certain knowledge is that the difference between the two function values of two consecutive numbers can only be 1, 0 or 1.
Our extrapolations show that from around 10^{24} the Zweiwertzahlen (twovalued numbers) are more densely distributed than the Einswertzahlen (onevalued numbers).
The smallest Nullwertzahl is 2, the smallest Einswertzahl is 3, the smallest Zweiwertzahl is 19, the smallest Dreiwertzahl is 173 and the smallest Vierwertzahl is 3976733.
Up to 10^{12} there are 19 fourvalue twins.
W (11872177333) = W (11872177334) = 4
W (128907074146) = W (128907074147) = 4
W (153592049893) = W (153592049894) = 4
W (173277915346) = W (173277915347) = 4
W (218180421013) = W (218180421014) = 4
W (372099798262) = W (372099798263) = 4
W (468167023417) = W (468167023418) = 4
W (496310532853) = W (496310532854) = 4
W (499081630666) = W (499081630667) = 4
W (533381128933) = W (533381128934) = 4
W (569616671893) = W (569616671894) = 4
W (571632935206) = W (571632935207) = 4
W (579535129813) = W (579535129814) = 4
W (829161163813) = W (829161163814) = 4
W (866580745333) = W (866580745334) = 4
W (945276981106) = W (945276981107) = 4
W (945635700586) = W (945635700587) = 4
W (960970734706) = W (960970734707) = 4
W (975903758266) = W (975903758267) = 4
A necessary but insufficient condition for the smallest Fünfwertzahl (fivevalued number) n is:
n is prime and W (0,5 * n  0,5) = W (0,5 * n + 0.5) = 4
We expect the smallest Fünfwertzahl (fivevalued number) to be around 10^{18}.
The best algorithms for the minimum total analysis up to n have the running time O (n * ln n) and the memory requirement O(n^{0.5}).
Greetings from Germany
