View Single Post
Old 2021-08-09, 23:54   #11
ThomasK
 
Aug 2021

11 Posts
Default

Quote:
Originally Posted by henryzz View Post
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!
ThomasK is offline   Reply With Quote