mersenneforum.org Minimum (Number Theory Game)
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

2021-08-08, 19:49   #2
Uncwilly
6809 > 6502

"""""""""""""""""""
Aug 2003
101×103 Posts

2×3×11×167 Posts

Quote:
 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.
Quote:
 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.
Quote:
 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.
Quote:
 An example: The number 13356 was drawn.
This is less than the 10 to 60 digits in your suggestion.

Quote:
 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

2021-08-08, 20:06   #3
slandrum

Jan 2021
California

10458 Posts

Quote:
 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.

Last fiddled with by slandrum on 2021-08-08 at 20:18

2021-08-08, 20:10   #4
retina
Undefined

"The unspeakable one"
Jun 2006
My evil lair

677110 Posts

Quote:
 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.

2021-08-08, 20:36   #5

Aug 2021

B16 Posts

Quote:
 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 > 1060.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.

2021-08-09, 07:36   #6
LaurV
Romulan Interpreter

"name field"
Jun 2011
Thailand

24·643 Posts

Quote:
 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.

Last fiddled with by LaurV on 2021-08-09 at 07:44

2021-08-09, 07:46   #7
Viliam Furik

"Viliam Furík"
Jul 2018
Martin, Slovakia

32116 Posts

Quote:
 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.

 2021-08-09, 07:49 #8 LaurV Romulan Interpreter     "name field" Jun 2011 Thailand 24·643 Posts 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? ) Last fiddled with by LaurV on 2021-08-09 at 08:08
2021-08-09, 10:41   #9
henryzz
Just call me Henry

"David"
Sep 2007
Liverpool (GMT/BST)

10111111100012 Posts

Quote:
 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

2021-08-09, 18:56   #10
Viliam Furik

"Viliam Furík"
Jul 2018
Martin, Slovakia

32×89 Posts

Quote:
 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.

2021-08-09, 23:54   #11

Aug 2021

11 Posts

Quote:
 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.

W0(200) = 29
W1(200) = 142
W2(200) = 27
W3(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:

W0(1000) = 108
W1(1000) = 686
W2(1000) = 201
W3(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 1012, 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 1012 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 1012 seperatly. In the next few years, when faster computers are available, we want to try a total analysis up to 1018.

Theoretically, a total analysis of up to 1018 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 n0.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 1018. But I will never experience the smallest Sechswertzahl, which is around 1049.

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 n0.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 10120. 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 1012 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!

 Similar Threads Thread Thread Starter Forum Replies Last Post ZFR Puzzles 11 2021-01-07 05:17 sweety439 sweety439 0 2020-10-29 18:20 lukerichards Number Theory Discussion Group 7 2018-01-29 14:58 mfgoode Puzzles 2 2006-05-30 09:46 math Homework Help 2 2004-05-02 18:09

All times are UTC. The time now is 00:22.

Sun Jun 4 00:22:01 UTC 2023 up 289 days, 21:50, 0 users, load averages: 0.59, 0.82, 0.87

Copyright ©2000 - 2023, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔