Minimum (Number Theory Game)

[ThomasK]

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).


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

For example


W₀(100) = 17
W₁(100) = 71
W₂(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₀(n) denotes the number of all Nullwertzahlen that are less than or equal to n.
W₁(n) denotes the number of all Einswertzahlen that are less than or equal to n.
W₂(n) denotes the number of all Zweiwertzahlen that are less than or equal to n.
W₃(n) denotes the number of all Dreiwertzahlen that are less than or equal to n.
W₄(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 W₀ (n) / pi (n) = C
C is on the order of about 0.61.

For example

W₀(10¹²) = 22996137423
pi(10¹²) = 37607912018


In 2003 we did a minimum total analysis up to 10¹² 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₀(10¹²) = 22996137423
W₁(10¹²) = 541664112990
W₂(10¹²) = 425608837164
W₃(10¹²) = 9730782305
W₄(10¹²) = 130117


The sum is not 10¹², but 10¹² -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¹⁸ and the smallest six-valued number at 10⁴⁹.


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 10²⁴ 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 10¹² 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 10¹⁸.

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

[Uncwilly]

Originally Posted by ThomasK

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.

So for the example you gave you gave a number smaller than 10 digits.

2. Each player tries to get from the number n to the number 2

So 2 is always your goal and has nothing to do with the 2 in rule 1.

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.

I can choose to subtract n-2 from n and go right to the final in a single step. Or I can divide n by n (no cost division) and then add 1, thus a single step.

An example: The number 13356 was drawn.

This is less than the 10 to 60 digits in your suggestion.

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

This shows that the actual strategy is to go the other direction. Factor out excess powers of 2, then 3 or 5, then 5 or 3, then 7, etc. There are tricks for many of the low primes to check for divisiblity. Since divides are free we get:

13356 / 2
6678 / 3
2226 / 3
742 / 7 [checked via 7 divisibility trick (74 - (2 * 2) = 70, a multiple of 7)
106 / 53 [a quick check against 2 shows it to be 53]
2

[slandrum]

Originally Posted by Uncwilly

I can choose to subtract n-2 from n and go right to the final in a single step. Or I can divide n by n (no cost division) and then add 1, thus a single step.

No - as stated, the moves that cost one are replace n with n+1 or n-1, not n-x. The no cost move is to replace n with n/d where d <= square root(n).

For the example given to demonstrate the process the factoring strategy works (but you'll have to write the divisions in reverse) because it's smooth and has 4 as a factor. You can't go from 106 to 2 because 53^2 > 106.

All powers of 2 are trivially 0 move numbers, and any 0 move number n multiplied by a number m where m < n results in another 0 move number.

[retina]

Originally Posted by ThomasK

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.

I suspect you wanted d to also be a proper divisor of n. Otherwise you are dealing with fractions.

Perhaps writing "d <= sqrt(n)" would make it clearer. Uncwilly seems to have missed that point.

[ThomasK]

Originally Posted by Uncwilly

So for the example you gave you gave a number smaller than 10 digits.


So 2 is always your goal and has nothing to do with the 2 in rule 1.
I can choose to subtract n-2 from n and go right to the final in a single step. Or I can divide n by n (no cost division) and then add 1, thus a single step.

This is less than the 10 to 60 digits in your suggestion.

This shows that the actual strategy is to go the other direction. Factor out excess powers of 2, then 3 or 5, then 5 or 3, then 7, etc. There are tricks for many of the low primes to check for divisiblity. Since divides are free we get:

13356 / 2
6678 / 3
2226 / 3
742 / 7 [checked via 7 divisibility trick (74 - (2 * 2) = 70, a multiple of 7)
106 / 53 [a quick check against 2 shows it to be 53]
2

I have only given the number 13356 as an introductory example. This posting is not a Minimum match!

If you subtract n - 2, this counts as n - 2 moves!

You cannot divide n by n, because the divisor must always be less than or equal to n ^ 0.5.


You play

13356 / 2
6678 / 3
2226 / 3
742 / 7
106 / 53
2


53 > 106^0.5 = 10.2956..., therefore 106 is the last correctly calculated number. Since 106 / 53 is illegal, therefore 106 is the last correctly calculated number. Since 106 / 53 is illegal, the referee would score 104 steps from 106 to 2 in the tournament.

[LaurV]

Originally Posted by ThomasK

An example: The number 13356 was drawn.

grrr... as this is an even number, you just divide it by its half to get to 2. <-Scratch that! Missed the part about the square root. Anyhow, minimum number of steps is always deterministic and it has nothing to do with the "number theory", more with programming, think about writing your number in binary and do some "magic" with it... I can't believe you wrote so much text for such a trivial problem, and these guys here fell into this trap.

[Viliam Furik]

Originally Posted by LaurV

grrr... as this is an even number, you just divide it by its half to get to 2. <-Scratch that! Missed the part about the square root. Anyhow, minimum number of steps is always deterministic and it has nothing to do with the "number theory", more with programming, think about writing your number in binary and do some "magic" with it... I can't believe you wrote so much text for such a trivial problem, and these guys here fell into this trap.

Didn't read the rules...

You can't divide by a number that is bigger than the number you are dividing. Divisor d of n is only allowed to divide n if d <= sqrt(n). For any number 2k > 4, k > sqrt(2k).

Just noticed your correction.

[LaurV]

Sorry, being stupid, haha. I re-read the game again. Please ignore my posts. (I could delete them, but where is the fun in that? )

[henryzz]

Originally Posted by LaurV

grrr... as this is an even number, you just divide it by its half to get to 2. <-Scratch that! Missed the part about the square root. Anyhow, minimum number of steps is always deterministic and it has nothing to do with the "number theory", more with programming, think about writing your number in binary and do some "magic" with it... I can't believe you wrote so much text for such a trivial problem, and these guys here fell into this trap.

Unless I am missing something you could divide it by 2 though.

The following may or may not be optimal(likely not)
106 / 2
53 - 1
52 / 4
13 - 1
12 / 3
4 / 2

[Viliam Furik]

Originally Posted by henryzz

Unless I am missing something you could divide it by 2 though.

The following may or may not be optimal(likely not)
106 / 2
53 - 1
52 / 4
13 - 1
12 / 3
4 / 2

I think this is the best you can do for this number.

[ThomasK]

Originally Posted by henryzz

Unless I am missing something you could divide it by 2 though.

The following may or may not be optimal(likely not)
106 / 2
53 - 1
52 / 4
13 - 1
12 / 3
4 / 2

Yes that is correct. 106 is a Zweiwertzahl (two-valued number). In the Minimum theory we write W (106) = 2.
106 is the 14th Zweiwertzahl. There are 27 Zweiwertzahlen up to 200:

19, 29, 38, 43, 53, 58, 67, 76, 86, 87, 89, 101, 103, 106, 116, 134, 137, 139, 149, 151, 152, 157, 163, 172, 174, 178, 197.

Up to 200 there is only one Dreiwertzahl, 173.

Up to 200 there are 29 Nullwertzahlen:

2, 4, 8, 12, 16, 24, 32, 36, 40, 48, 56, 60, 64, 72, 80, 84, 96, 108, 112, 120, 128, 132, 144, 160, 168, 176, 180, 192, 200.

The whole remainder (142 numbers) are Einswertzahlen.

W₀(200) = 29
W₁(200) = 142
W₂(200) = 27
W₃(200) = 1


All numbers between 2 and 172 have the value 0, 1 or 2.
3 moves are required for the number 173. W (173) = 3.

I do not even need to look up the hard drive in this small range of numbers. I know that by heart.

In this number range, the Nullwertzahlen are just before the Zweiwertzahlen, but this changes shortly afterwards. Already at 1000 the Zweiwertzahlen are clearly ahead:

W₀(1000) = 108
W₁(1000) = 686
W₂(1000) = 201
W₃(1000) = 4

The 4 Dreiwertzahlen less than 1000 are 173, 347, 823 and 907.
_________________________________

In order to save the values ​​of all numbers up to 10¹², we need 250 GByte with our algorithm. We need two bits for each number, so that we can store four numbers with one byte.

00 = Nullwertzahl
01 = Einswertzahl
10 = Zweiwertzahl
11 = Dreiwertzahl
00 = Vierwertzahl


Up to 10¹² there are only 130117 Vierwertzahlen; that can be stored separately.

Since the value between n and n + 1 can only differ by 1, 0, or -1, we stored the Vierwertzahlen - just like the Nullwertzahlen - as 00. However, since a Nullwertzahl is always between two Einswertzahlen, but a Vierwertzahl is always between a Dreiwertzahl, a Vierwertzahl (or at some point, when we have found the smallest Fünfwertzahl) also next to a Fünfwertzahl, it is no problem to save the 130117 Vierwertzahlen up to 10¹² seperatly. In the next few years, when faster computers are available, we want to try a total analysis up to 10¹⁸.

Theoretically, a total analysis of up to 10¹⁸ could already be carried out on mainframes today. But we do not manage to improve the running time of the algorithm. The running time is O(n * ln n). As far as I am informed, the running time of the algorithm for calculating pi (n) is about n^0.5+epsilon with an infinitesimally small epsilon > 0.

I think that I have a very good chance live to see the smallest Fünfwertzahl, which is around 10¹⁸. But I will never experience the smallest Sechswertzahl, which is around 10⁴⁹.

According to our theoretical estimates, we assume that the asymptotic density for the distribution of the Zweiwertzahlen is 1, i.e. if you draw a random natural number between 2 and n and let n run towards infinity, then the probability of drawn a Zweiwertzahl is 1.

On the other hand, we have the conjecture:

The statement "There is an upper bound s such that W (n) <= s for all natural numbers." is wrong!

This may seem surprising since there are infinitely many Nullwertzahlen, but our heuristics rely on the following two proven theorems:

1. Almost all natural numbers n have more than (1 - epsilon) * ln ln n and less than (1 + epsilon) * ln ln n prime factors with an infinitesimally small epsilon > 0.
2. If one draw any natural number n and lets n go to infinity, then the probability that the greatest prime factor of n is greater than n^0.5 is about ln 2 = 0.693147......

Here is an example. Let us imagine a strip of paper that extends from the earth to the sun and is therefore 150 million kilometers long. Now we write a natural number on this strip of paper, calculating 0.5 cm per decimal digit. So the number is about 10 ^ (3 * 10 ^ 13). This number is of course far greater than the number of all elementary particles in the observable universe, which is well below 10¹²⁰. The number that indicates the number of all elementary particles in the observable universe is therefore shorter than 60 cm. Our earth-sun number is therefore 10 ^ (3 * 10 ^ 13). So this number is 150 million kilometers long. The square root of this number is 10 ^ (1.5 * 10 ^ 13) and is therefore 75 million kilometers long. The probability that the largest prime factor of a 150 million kilometers long number is a number that is at least 75 million kilometers long is ln 2 = 0.693147......

In order to make an estimate of the density of Einswertzahlen and Zweiwertzahlen, we need to know how many prime factors such a number normally has. The answer is about ln ln n.

ln ln (10 ^ (3 * 10 ^ 13)) = ln (3 * 10 ^ 13 * ln 10) is about 32. A number in the order of magnitude of the earth-sun number, i.e. (10 ^ (3 * 10 ^ 13)) has usually about 32 or 33 prime factors, depending on whether you include the powers of the prime factorization or not.

It turns out that in the Minimum theory the function ln ln n plays a very decisive role.
___________________________________

In the Minimum game, computers are more than 10¹² times better than humans.

The 10-digit number 8808334453 was drawn. I found a solution in 3 moves; my opponent one in 4 moves, so that I had won. After the game, I entered the number 8808334453 into the computer and was shocked. In less than a tenth of a second the computer displayed the following:

W (8808334453) = 1

8808334453 / 51307
171679 + 1
171680 / 37
4640 / 29
160 / 10
16 / 4
4 / 2
2

At first I was proud to have found a solution in 3 moves, but after the computer result all pride was completely destroyed.

Never ever play Minimum against a computer!