View Single Post
Old 2021-08-08, 17:19   #1
ThomasK
 
Aug 2021

11 Posts
Default 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 (Zero-value numbers).
Numbers with the value 1 are called Einswertzahlen (One-value numbers).
Numbers with the value 2 are called Zweiwertzahlen (Two-value numbers).
Numbers with the value 3 are called Dreiwertzahlen (Three-value numbers).
Numbers with the value 4 are called Vierwertzahlen (Four-value numbers).


W(n) denotes the value of n, so W(12) = 0 means that 12 is a Nullwertzahl (zero-value number).


W0(n) denotes the number of all Nullwertzahlen (zero-value numbers) less than or equal to n.

For example


W0(100) = 17
W1(100) = 71
W2(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


_______________________________


W0(n) denotes the number of all Nullwertzahlen that are less than or equal to n.
W1(n) denotes the number of all Einswertzahlen that are less than or equal to n.
W2(n) denotes the number of all Zweiwertzahlen that are less than or equal to n.
W3(n) denotes the number of all Dreiwertzahlen that are less than or equal to n.
W4(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 (zero-valued 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 (zero-valued 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 W0 (n) / pi (n) = C
C is on the order of about 0.61.

For example

W0(1012) = 22996137423
pi(1012) = 37607912018


In 2003 we did a minimum total analysis up to 1012 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

W0(1012) = 22996137423
W1(1012) = 541664112990
W2(1012) = 425608837164
W3(1012) = 9730782305
W4(1012) = 130117


The sum is not 1012, but 1012 -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 1018 and the smallest six-valued number at 1049.


The longest chain of consecutive Einswertzahlen (one-value numbers) has the length 47. It runs from 364964597713 to 364964597759 and is limited by two Nullwertzahlen (zero-value numbers).


The longest chain of consecutive Zweiwertzahlen (two-value 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 (one-value numbers) has the length 8. It runs from 635373605583 to 635373605590 and is limited by two Zweiwertzahlen (two-value numbers).


The greatest distance between two consecutive Nullwertzahlen (zero-valued numbers) is 780. There is no other Nullwertzahl zero-valued number between the two Nullwertzahlen (zero-valued 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, one-value twins and two-value 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 1024 the Zweiwertzahlen (two-valued numbers) are more densely distributed than the Einswertzahlen (one-valued 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 1012 there are 19 four-value 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 (five-valued 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 (five-valued number) to be around 1018.

The best algorithms for the minimum total analysis up to n have the running time O (n * ln n) and the memory requirement O(n0.5).




Greetings from Germany
ThomasK is offline   Reply With Quote