20210808, 17:19  #1 
Aug 2021
2·5 Posts 
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 
20210808, 19:49  #2  
6809 > 6502
"""""""""""""""""""
Aug 2003
101×103 Posts
10,513 Posts 
Quote:
Quote:
Quote:
Quote:
Quote:
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 

20210808, 20:06  #3  
Jan 2021
California
2·191 Posts 
Quote:
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. Last fiddled with by slandrum on 20210808 at 20:18 

20210808, 20:10  #4  
Undefined
"The unspeakable one"
Jun 2006
My evil lair
6,449 Posts 
Quote:
Perhaps writing "d <= sqrt(n)" would make it clearer. Uncwilly seems to have missed that point. 

20210808, 20:36  #5  
Aug 2021
2×5 Posts 
Quote:
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. 

20210809, 07:36  #6 
Romulan Interpreter
"name field"
Jun 2011
Thailand
7·1,423 Posts 
Last fiddled with by LaurV on 20210809 at 07:44 
20210809, 07:46  #7  
"Viliam Furík"
Jul 2018
Martin, Slovakia
3·251 Posts 
Quote:
Just noticed your correction. 

20210809, 07:49  #8 
Romulan Interpreter
"name field"
Jun 2011
Thailand
23351_{8} Posts 
Sorry, being stupid, haha. I reread the game again. Please ignore my posts. (I could delete them, but where is the fun in that? )
Last fiddled with by LaurV on 20210809 at 08:08 
20210809, 10:41  #9  
Just call me Henry
"David"
Sep 2007
Liverpool (GMT/BST)
2^{5}·11·17 Posts 
Quote:
The following may or may not be optimal(likely not) 106 / 2 53  1 52 / 4 13  1 12 / 3 4 / 2 

20210809, 18:56  #10 
"Viliam Furík"
Jul 2018
Martin, Slovakia
3×251 Posts 

20210809, 23:54  #11  
Aug 2021
2·5 Posts 
Quote:
Yes that is correct. 106 is a Zweiwertzahl (twovalued 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_{0}(200) = 29 W_{1}(200) = 142 W_{2}(200) = 27 W_{3}(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_{0}(1000) = 108 W_{1}(1000) = 686 W_{2}(1000) = 201 W_{3}(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^{12}, 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^{12} 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^{12} seperatly. In the next few years, when faster computers are available, we want to try a total analysis up to 10^{18}. Theoretically, a total analysis of up to 10^{18} 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^{18}. But I will never experience the smallest Sechswertzahl, which is around 10^{49}. 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^{120}. The number that indicates the number of all elementary particles in the observable universe is therefore shorter than 60 cm. Our earthsun 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 earthsun 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^{12} times better than humans. The 10digit 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! 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
A game theory paradox puzzle  ZFR  Puzzles  11  20210107 05:17 
Two number theory questions  sweety439  Math  0  20201029 18:20 
Help with a number theory equivalence  lukerichards  Number Theory Discussion Group  7  20180129 14:58 
Easy number theory.  mfgoode  Puzzles  2  20060530 09:46 
number theory help  math  Homework Help  2  20040502 18:09 