mersenneforum.org

mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Computer Science & Computational Number Theory (https://www.mersenneforum.org/forumdisplay.php?f=116)
-   -   Minimum (Number Theory Game) (https://www.mersenneforum.org/showthread.php?t=27056)

ThomasK 2021-08-08 17:19

Minimum (Number Theory Game)
 
[B]Minimum (Number Theory Game)[/B]


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[SUB]0[/SUB](n) denotes the number of all Nullwertzahlen (zero-value numbers) less than or equal to n.

For example


W[SUB]0[/SUB](100) = 17
W[SUB]1[/SUB](100) = 71
W[SUB]2[/SUB](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[SUB]0[/SUB](n) denotes the number of all Nullwertzahlen that are less than or equal to n.
W[SUB]1[/SUB](n) denotes the number of all Einswertzahlen that are less than or equal to n.
W[SUB]2[/SUB](n) denotes the number of all Zweiwertzahlen that are less than or equal to n.
W[SUB]3[/SUB](n) denotes the number of all Dreiwertzahlen that are less than or equal to n.
W[SUB]4[/SUB](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[SUB]0[/SUB] (n) / pi (n) = C
C is on the order of about 0.61.

For example

W[SUB]0[/SUB](10[SUP]12[/SUP]) = 22996137423
pi(10[SUP]12[/SUP]) = 37607912018


In 2003 we did a minimum total analysis up to 10[SUP]12[/SUP] 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[SUB]0[/SUB](10[SUP]12[/SUP]) = 22996137423
W[SUB]1[/SUB](10[SUP]12[/SUP]) = 541664112990
W[SUB]2[/SUB](10[SUP]12[/SUP]) = 425608837164
W[SUB]3[/SUB](10[SUP]12[/SUP]) = 9730782305
W[SUB]4[/SUB](10[SUP]12[/SUP]) = 130117


The sum is not 10[SUP]12[/SUP], but 10[SUP]12[/SUP] -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[SUP]18[/SUP] and the smallest six-valued number at 10[SUP]49[/SUP].


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[SUP]24[/SUP] 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[SUP]12[/SUP] 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[SUP]18[/SUP].

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[SUP]0.5[/SUP]).




Greetings from Germany

Uncwilly 2021-08-08 19:49

[QUOTE=ThomasK;585188]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.[/QUOTE]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[/QUOTE]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.[/QUOTE]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.[/QUOTE]
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[/QUOTE]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 2021-08-08 20:06

[QUOTE=Uncwilly;585197]
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]

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 2021-08-08 20:10

[QUOTE=ThomasK;585188]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.[/QUOTE]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 2021-08-08 20:36

[QUOTE=Uncwilly;585197]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[/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[SUP]0.5[/SUP] = 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 2021-08-09 07:36

[QUOTE=ThomasK;585188]An example: The number 13356 was drawn.
[/QUOTE]
[STRIKE]grrr... as this is an even number, you just divide it by its half to get to 2. [/STRIKE] <-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 2021-08-09 07:46

[QUOTE=LaurV;585230][STRIKE]grrr... as this is an even number, you just divide it by its half to get to 2. [/STRIKE] <-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.[/QUOTE]

Didn't read the rules...

[STRIKE]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).[/STRIKE]

Just noticed your correction.

LaurV 2021-08-09 07:49

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? :razz:)

henryzz 2021-08-09 10:41

[QUOTE=LaurV;585230][STRIKE]grrr... as this is an even number, you just divide it by its half to get to 2. [/STRIKE] <-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.[/QUOTE]

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 2021-08-09 18:56

[QUOTE=henryzz;585240]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[/QUOTE]

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

ThomasK 2021-08-09 23:54

[QUOTE=henryzz;585240]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[/QUOTE]


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[SUB]0[/SUB](200) = 29
W[SUB]1[/SUB](200) = 142
W[SUB]2[/SUB](200) = 27
W[SUB]3[/SUB](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[SUB]0[/SUB](1000) = 108
W[SUB]1[/SUB](1000) = 686
W[SUB]2[/SUB](1000) = 201
W[SUB]3[/SUB](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[SUP]12[/SUP], 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[SUP]12[/SUP] 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[SUP]12[/SUP] seperatly. In the next few years, when faster computers are available, we want to try a total analysis up to 10[SUP]18[/SUP].

Theoretically, a total analysis of up to 10[SUP]18[/SUP] 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[SUP]0.5+epsilon[/SUP] 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[SUP]18[/SUP]. But I will never experience the smallest Sechswertzahl, which is around 10[SUP]49[/SUP].

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."[B] [U]is wrong![/U][/B]

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[SUP]0.5[/SUP] 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[SUP]120[/SUP]. 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[SUP]12[/SUP] 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!

Happy5214 2021-08-10 05:01

[QUOTE=henryzz;585240]The following may or may not be optimal(likely not)
106 / 2
53 - 1
52 / 4
13 - 1
12 / 3
4 / 2[/QUOTE]

[QUOTE=Viliam Furik;585277]I think this is the best you can do for this number.[/QUOTE]

Tied for the best?

106 / 2
53 + 1
54 / 2
27 / 3
9 / 3
3 - 1

axn 2021-08-10 07:25

[QUOTE=Happy5214;585306]Tied for the best?

106 / 2
53 + 1
54 / 2
27 / 3
9 / 3
3 - 1[/QUOTE]

106 + 1
107 + 1
108 / 9
12 / 3
4 / 2

106 - 1
105 / 7 (alternate 105 / 3 / 5 + 1 / 2 / 2)
15 / 3 ; 15 + 1
5 - 1 ; 16 / 4
4 / 2

R. Gerbicz 2021-08-10 11:43

[QUOTE=ThomasK;585188]
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[SUP]0.5[/SUP]).
[/QUOTE]

Time in O(n*loglog(n)) is also possible, because with easy proof you can assume that you can always choose d=p prime, where p^2<=n.

When you compute the sequence:
W(n)<=min{W(n/p): p|n and p^2<=n}.
Calculate W() in large blocks, say in [1+2^e,2^(e+1)] then we already know the n/p<=n/2<=2^e W values.

W(n)<=min(W[n-1]+1,W[n+1]+1), but we wouldn't use +1 after -1, so with two pass you can get the whole W() sequence, once go from left then right.

W(n)<log2(n) is also trivial (use binary expansion of n: repeatedly divide by 2 for even n, otherwise subtract one).

With slow factoring, but the obvious sieving method gives the O(n*loglog(n)) algorithm. Use PARI-Gp,
[CODE]
F(E)={W=vector(2^E,n,E);
W[1]=W[2]=0;
for(e=1,E-1,for(n=1+2^e,2^(e+1),
a=factor(n);o=matsize(a)[1];
for(i=1,o,p=a[i,1];if(p^2<=n,W[n]=min(W[n],W[n/p]))));
for(n=1+2^e,2^(e+1),W[n]=min(W[n],W[n-1]+1));
forstep(n=-1+2^(e+1),1+2^e,-1,W[n]=min(W[n],W[n+1]+1)));
return(W)}

F(20);

for(h=0,5,print(h" "sum(i=2,10^6,W[i]==h)))
[/CODE]

The counts for [2,10^6] if you could check: [the counts for the given [2,1000] is good]
[CODE]
W() count
0 48474
1 614400
2 328988
3 8137
4 0
5 0
[/CODE]

Viliam Furik 2021-08-10 12:07

[QUOTE=Happy5214;585306]Tied for the best?

106 / 2
53 + 1
54 / 2
27 / 3
9 / 3
3 - 1[/QUOTE]

I messed up. I forgot you can do +1.

ThomasK 2021-08-10 12:58

To give you a feeling how the distribution of the numbers is developing, I give you the function values for all powers of ten from 1 to 12.


W[SUB]0[/SUB](10): 3
W[SUB]1[/SUB](10): 6
W[SUB]2[/SUB](10): 0
W[SUB]3[/SUB](10): 0
W[SUB]4[/SUB](10): 0


W[SUB]0[/SUB](100): 17
W[SUB]1[/SUB](100): 71
W[SUB]2[/SUB](100): 11
W[SUB]3[/SUB](100): 0
W[SUB]4[/SUB](100): 0


W[SUB]0[/SUB](10[SUP]3[/SUP]): 108
W[SUB]1[/SUB](10[SUP]3[/SUP]): 686
W[SUB]2[/SUB](10[SUP]3[/SUP]): 201
W[SUB]3[/SUB](10[SUP]3[/SUP]): 4
W[SUB]4[/SUB](10[SUP]3[/SUP]): 0


W[SUB]0[/SUB](10[SUP]4[/SUP]): 755
W[SUB]1[/SUB](10[SUP]4[/SUP]): 6598
W[SUB]2[/SUB](10[SUP]4[/SUP]): 2592
W[SUB]3[/SUB](10[SUP]4[/SUP]): 54
W[SUB]4[/SUB](10[SUP]4[/SUP]): 0


W[SUB]0[/SUB](10[SUP]5[/SUP]): 5936
W[SUB]1[/SUB](10[SUP]5[/SUP]): 63449
W[SUB]2[/SUB](10[SUP]5[/SUP]): 29916
W[SUB]3[/SUB](10[SUP]5[/SUP]): 698
W[SUB]4[/SUB](10[SUP]5[/SUP]): 0


W[SUB]0[/SUB](10[SUP]6[/SUP]): 48474
W[SUB]1[/SUB](10[SUP]6[/SUP]): 614400
W[SUB]2[/SUB](10[SUP]6[/SUP]): 328988
W[SUB]3[/SUB](10[SUP]6[/SUP]): 8137
W[SUB]4[/SUB](10[SUP]6[/SUP]): 0


W[SUB]0[/SUB](10[SUP]7[/SUP]): 406270
W[SUB]1[/SUB](10[SUP]7[/SUP]): 5952657
W[SUB]2[/SUB](10[SUP]7[/SUP]): 3550745
W[SUB]3[/SUB](10[SUP]7[/SUP]): 90324
W[SUB]4[/SUB](10[SUP]7[/SUP]): 3


W[SUB]0[/SUB](10[SUP]8[/SUP]): 3532031
W[SUB]1[/SUB](10[SUP]8[/SUP]): 58088295
W[SUB]2[/SUB](10[SUP]8[/SUP]): 37432690
W[SUB]3[/SUB](10[SUP]8[/SUP]): 946964
W[SUB]4[/SUB](10[SUP]8[/SUP]): 19


W[SUB]0[/SUB](10[SUP]9[/SUP]): 31295358
W[SUB]1[/SUB](10[SUP]9[/SUP]): 568932663
W[SUB]2[/SUB](10[SUP]9[/SUP]): 390065916
W[SUB]3[/SUB](10[SUP]9[/SUP]): 9705879
W[SUB]4[/SUB](10[SUP]9[/SUP]): 183


W[SUB]0[/SUB](10[SUP]10[/SUP]): 279591668
W[SUB]1[/SUB](10[SUP]10[/SUP]): 5588087493
W[SUB]2[/SUB](10[SUP]10[/SUP]): 4034529147
W[SUB]3[/SUB](10[SUP]10[/SUP]): 97790090
W[SUB]4[/SUB](10[SUP]10[/SUP]): 1601


W[SUB]0[/SUB](10[SUP]11[/SUP]): 2521429242
W[SUB]1[/SUB](10[SUP]11[/SUP]): 54968844332
W[SUB]2[/SUB](10[SUP]11[/SUP]): 41532029309
W[SUB]3[/SUB](10[SUP]11[/SUP]): 977682518
W[SUB]4[/SUB](10[SUP]11[/SUP]): 14598


W[SUB]0[/SUB](10[SUP]12[/SUP]): 22996137423
W[SUB]1[/SUB](10[SUP]12[/SUP]): 541664112990
W[SUB]2[/SUB](10[SUP]12[/SUP]): 425608837164
W[SUB]3[/SUB](10[SUP]12[/SUP]): 9730782305
W[SUB]4[/SUB](10[SUP]12[/SUP]): 130117


[B]Note: Always the sum is not 10[SUP]n[/SUP] but 10[SUP]n[/SUP] - 1, because W (1) is not defined.[/B]


_____________________________________________________


When we calculated a total analysis up to 10[SUP]10[/SUP] for the first time in the early years, we thought that, contrary to our theoretical estimates, which say that the asymptotic density for the Zweiwertzahlen is 1 and the asymptotic density for the Dreiwertzahlen is 0, there was a calculation error, because after the total analysis by the computer up to 10[SUP]10[/SUP] the proportion of Dreiwertzahlen increases.

That is a contradiction. To solve the problem we decided to do the total analysis up to 10[SUP]12[/SUP].

The relief and the cheering was very great when we read the intermediate results on the screen in the middle of the night during the calculation and the proportion of Dreiwertzahlen - as had long been expected - finally fell. If this hadn't been the case, then we could have thrown away all of our theoretical estimates.

The reason this takes so long is that the function ln ln n increases extremely slowly and it takes a very long time before the function ln ln n can assert itself against multiplicative constants.

We expect that around 10[SUP]24[/SUP] the Zweiwertzahlen will overtake the Einswertzahlen, i.e. W[SUB]2[/SUB](n) > W[SUB]1[/SUB](n) for all n > around 10[SUP]24[/SUP].

However, the Einswertzahlen offer very strong resistance against the Zweiwertzahlen. According to our extrapolations, it takes an extremely long time before the Zweiwertzahlen goes to the asyptotic density 1 and the Einswertzahlen goes to the asyptotic density 0 approach.


_____________________________________


In the next posts I will tell you something about our algorithm and prove a very important theorem from the Minimum theory.

ThomasK 2021-08-10 22:02

[QUOTE=R. Gerbicz;585321]Time in O(n*loglog(n)) is also possible, because with easy proof you can assume that you can always choose d=p prime, where p^2<=n.



(...)[/QUOTE]




Many Thanks. You are right, your algorithm is better with a running time of O (n * ln ln n) than our algorithm with a running time of O (n * ln n).

Our algorithm differentiates between a Grundblock (= basic block) and a Schiebeblock (= push block). If we want to create a total analysis up to n, then the basic block has a size of at least n[SUP]0.5[/SUP]. The values ​​of all numbers from 2 to at least n[SUP]0.5[/SUP] are stored in the basic block. No further analysis is necessary in this area, as all numbers are known with their value and prime factorization. It is practical if the basic block extends from 2 to 10[SUP]n[/SUP] for all n > = 3, since W (10[SUP]n[/SUP]) = 0 for all n > = 3. The length of the push block is n[SUP]0.5[/SUP]. In the total analysis up to 10[SUP]12[/SUP], the basic block was given from 2 to 10[SUP]6[/SUP]. The first push block ranged from 10[SUP]6[/SUP] + 1 to 2 * 10[SUP]6[/SUP], the second push block from 2 * 10[SUP]6[/SUP] + 1 to 3 * 10[SUP]6[/SUP], the nth push block from n * 10 ^ 6 + 1 to (n + 1) * 10 ^ 6 and the last push block from (10[SUP]6[/SUP] - 1) * 10[SUP]6[/SUP] to 10[SUP]6[/SUP] * 10[SUP]6[/SUP]. This classification guarantees that the first number of a push block is always a Einswertzahl and the last number of a push block is always a Nullwertzahl.

Now all Nullwertzahlen in a pushblock are determined within a push block; the numbers with a value > 0 fall through a sieve.

W (n) = 0 if and only if 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.

In the next run, all numbers are determined within the push block that can reach a zero value number with one move. These are then the Einswertzahlen. Numbers with a value > 1 fall through a sieve.
In the next run, all numbers are determined within the push block that can reach a Einswertzahl with one move, etc.
Once all the numbers within a push block have been analyzed, the corresponding analyzes are carried out and then the next push block is analyzed.

With this algorithm you can improve the multiplicative constant if you have saved the prime numbers. However, we do not manage to be better than n * ln n, which is why your algorithm is better. But I believe that beyond O (n * ln ln n) further improvements are impossible. Depending on how many prime numbers or Nullwertzahlen are stored, the only thing that matters in the runtime is the reduction of the multiplicative constant.

__________________________

In the next post we will prove the Theorem of value restriction of sufficiently large potencies:


W (n[SUP]k[/SUP]) = 0 for all k> = ln n / ln 2 - 1 if n is even
W (n[SUP]k[/SUP]) = 1 for all k> = (n-1) / 2 if n is odd

ThomasK 2021-08-12 13:02

[B]Theorem of value restriction of sufficiently large potencies:[/B]

n is a natural number with n >= 2


Then applies

W (n[SUP]k[/SUP]) = 0 for all k > = ln n / ln 2 - 1 if n is even
W (n[SUP]k[/SUP]) = 1 for all k > = (n-1) / 2 if n is odd


Proof:

We prove this theorem specifically for n = 2 and n = 3 and n = 4 and in general for n > = 5.

W(2[SUP]k[/SUP]) = 0 for all k = 1, 2, 3, 4, ....(Powers of 4 included)
W(3[SUP]k[/SUP]) = 1 for all k = 1, 2, 3, 4, ....

Let n > = 5 be a natural number and k a natural number.

First case: n is even

n = 2 * (n / 2) and n[SUP]k[/SUP] = 2[SUP]k[/SUP] * (n/2)[SUP]k[/SUP]. In the worst case, n / 2 is a prime number.

But if n / 2 <= 2[SUP]k[/SUP], you can divide each away n / 2 in the first k steps and get the Nullwertzahl 2[SUP]k[/SUP]. A sufficient condition for n[SUP]k[/SUP] to be a Nullwertzahl is therefore 2[SUP]k[/SUP] > = n / 2 or k > = ln (n / 2) / ln 2 = ln n / ln 2 - 1.


Second case: n is odd

n[SUP]2[/SUP] - 1 = (n + 1)(n - 1) = 2[SUP]2[/SUP] * (n + 1) / 2 * (n - 1) / 2
n[SUP]4[/SUP] - 1 = (n[SUP]2[/SUP] + 1)(n[SUP]2[/SUP] - 1) = (n[SUP]2[/SUP] + 1)(n + 1)(n - 1)

In general

n[SUP](2^j)[/SUP] - 1 = (n[SUP](2^(j-1))[/SUP] + 1)(n[SUP](2^(j-1))[/SUP] - 1) =
2[SUP](j+1)[/SUP] * (n[SUP](2^(j-1))[/SUP] + 1) / 2 * (n[SUP](2^(j-2))[/SUP] + 1) / 2 * ... * (n[SUP](2^1)[/SUP] + 1) / 2 * (n + 1) / 2 * (n - 1) / 2

Let us first take the case that k = 2[SUP]j[/SUP] is a power of 2. Then we subtract one from n[SUP]k[/SUP] and get n[SUP]k[/SUP] - 1, which costs us a move. From the above factorization of n[SUP](2^j)[/SUP] - 1 we can now divide away all the odd factors one after the other, first the largest, then the second largest, and so on, because of n > = 5 it the largest factor in each case is still smaller than the product of remaining factors. The last thing left is (n - 1) / 2, which in the worst case is a prime number. So n[SUP](2^j)[/SUP] - 1 is a Nullwertzahl if 2[SUP](j+1)[/SUP] >= (n - 1) / 2, from which 2[SUP]j[/SUP] > = (n - 1) / 4 follows.

In the general case that k is not a power of 2, we divide n from n[SUP]k[/SUP] away until the remaining exponent is a power of 2 that is 2[SUP]j[/SUP]. The original exponent k must shrink by half at most. So if k > = (n - 1) / 2, then 2[SUP]j[/SUP] > = (n - 1) / 4. So it follows that W (n[SUP]k[/SUP]) = 1 for all k > = (n - 1) / 2.


With this the [B]Theorem of value restriction of sufficiently large potencies [/B]is completely proved!


__________________________________________________________


This theorem has far-reaching consequences in Minimum theory.

We denote the set of all Nullwertzahlen with W[SUB]0[/SUB], the set of all Einswertzahlen with W[SUB]1[/SUB], the set of all Zweiwertzahlen with W[SUB]2[/SUB], the set of all Dreiwertzahlen with W[SUB]3[/SUB], the set of all Vierwertzahlen with W[SUB]4[/SUB], and the set of all k-valued numbers with W[SUB]k[/SUB].

If every sufficiently large power of [B]EVERY[/B] even natural number is a Nullwertzahl and every sufficiently large power of [B]EVERY[/B] odd natural number is a Einswertzahl, then the conjecture that the density of the set of all Numbers W[SUB]k[/SUB] is 0 [U][B]is false[/B][/U]!

Sometimes we call the set of Nullwertzahlen und Einswertzahlen together as cheap numbers and those numbers with W (n) > = 3 as expensive numbers. So far we have only carried out the total analysis up to 10[SUP]12[/SUP], but we took a random look at the distribution of the numbers above 10[SUP]12[/SUP]. The following table shows the number of Nullwertzahlen up to the Vierwertzahlen in the first milliard above 10[SUP]12[/SUP], 10[SUP]13[/SUP] and 10[SUP]14[/SUP].

The distribution is as our theoretical estimates predict. But there is still a long way to go to the smallest Fünfwertzahl, which we suspect to be on the order of 10[SUP]18[/SUP].


W[SUB]0[/SUB](10[SUP]12[/SUP] + 10[SUP]9[/SUP]) - W[SUB]0[/SUB](10[SUP]12[/SUP]): 22129699
W[SUB]1[/SUB](10[SUP]12[/SUP] + 10[SUP]9[/SUP]) - W[SUB]1[/SUB](10[SUP]12[/SUP]): 538366808
W[SUB]2[/SUB](10[SUP]12[/SUP] + 10[SUP]9[/SUP]) - W[SUB]2[/SUB](10[SUP]12[/SUP]): 429800315
W[SUB]3[/SUB](10[SUP]12[/SUP] + 10[SUP]9[/SUP]) - W[SUB]3[/SUB](10[SUP]12[/SUP]): 9703057
W[SUB]4[/SUB](10[SUP]12[/SUP] + 10[SUP]9[/SUP]) - W[SUB]4[/SUB](10[SUP]12[/SUP]): 121

W[SUB]0[/SUB](10[SUP]13[/SUP] + 10[SUP]9[/SUP]) - W[SUB]0[/SUB](10[SUP]13[/SUP]): 20455311
W[SUB]1[/SUB](10[SUP]13[/SUP] + 10[SUP]9[/SUP]) - W[SUB]1[/SUB](10[SUP]13[/SUP]): 531664281
W[SUB]2[/SUB](10[SUP]13[/SUP] + 10[SUP]9[/SUP]) - W[SUB]2[/SUB](10[SUP]13[/SUP]): 438266115
W[SUB]3[/SUB](10[SUP]13[/SUP] + 10[SUP]9[/SUP]) - W[SUB]3[/SUB](10[SUP]13[/SUP]): 9614183
W[SUB]4[/SUB](10[SUP]13[/SUP] + 10[SUP]9[/SUP]) - W[SUB]4[/SUB](10[SUP]13[/SUP]): 110

W[SUB]0[/SUB](10[SUP]14[/SUP] + 10[SUP]9[/SUP]) - W[SUB]0[/SUB](10[SUP]14[/SUP]): 19015775
W[SUB]1[/SUB](10[SUP]14[/SUP] + 10[SUP]9[/SUP]) - W[SUB]1[/SUB](10[SUP]14[/SUP]): 525804423
W[SUB]2[/SUB](10[SUP]14[/SUP] + 10[SUP]9[/SUP]) - W[SUB]2[/SUB](10[SUP]14[/SUP]): 445685370
W[SUB]3[/SUB](10[SUP]14[/SUP] + 10[SUP]9[/SUP]) - W[SUB]3[/SUB](10[SUP]14[/SUP]): 9494338
W[SUB]4[/SUB](10[SUP]14[/SUP] + 10[SUP]9[/SUP]) - W[SUB]4[/SUB](10[SUP]14[/SUP]): 94


In the next Posting we will compare the Nullwertzahlen with the prime numbers. The comparison of the functions W[SUB]0[/SUB](n) and pi (n) is very interesting.

ThomasK 2021-08-17 00:34

In this post we will compare the Nullwertzahlen with the prime numbers. In particular, it is also about the comparison of the functions Pi (x) and W[SUB]0[/SUB](x).

Pi (x) is the number of prime numbers less than or equal to x and W[SUB]0[/SUB](x) is the number of Nullwertzahlen less than or equal to x.

To get a feel for why the Nullwertzahlen behave like prime numbers on the one hand, but also like inverse prime numbers on the other, here all prime numbers and all Nullwertzahlen up to 10000.


Prime Numbers up to 10000:

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997, 1009, 1013, 1019, 1021, 1031, 1033, 1039, 1049, 1051, 1061, 1063, 1069, 1087, 1091, 1093, 1097, 1103, 1109, 1117, 1123, 1129, 1151, 1153, 1163, 1171, 1181, 1187, 1193, 1201, 1213, 1217, 1223, 1229, 1231, 1237, 1249, 1259, 1277, 1279, 1283, 1289, 1291, 1297, 1301, 1303, 1307, 1319, 1321, 1327, 1361, 1367, 1373, 1381, 1399, 1409, 1423, 1427, 1429, 1433, 1439, 1447, 1451, 1453, 1459, 1471, 1481, 1483, 1487, 1489, 1493, 1499, 1511, 1523, 1531, 1543, 1549, 1553, 1559, 1567, 1571, 1579, 1583, 1597, 1601, 1607, 1609, 1613, 1619, 1621, 1627, 1637, 1657, 1663, 1667, 1669, 1693, 1697, 1699, 1709, 1721, 1723, 1733, 1741, 1747, 1753, 1759, 1777, 1783, 1787, 1789, 1801, 1811, 1823, 1831, 1847, 1861, 1867, 1871, 1873, 1877, 1879, 1889, 1901, 1907, 1913, 1931, 1933, 1949, 1951, 1973, 1979, 1987, 1993, 1997, 1999, 2003, 2011, 2017, 2027, 2029, 2039, 2053, 2063, 2069, 2081, 2083, 2087, 2089, 2099, 2111, 2113, 2129, 2131, 2137, 2141, 2143, 2153, 2161, 2179, 2203, 2207, 2213, 2221, 2237, 2239, 2243, 2251, 2267, 2269, 2273, 2281, 2287, 2293, 2297, 2309, 2311, 2333, 2339, 2341, 2347, 2351, 2357, 2371, 2377, 2381, 2383, 2389, 2393, 2399, 2411, 2417, 2423, 2437, 2441, 2447, 2459, 2467, 2473, 2477, 2503, 2521, 2531, 2539, 2543, 2549, 2551, 2557, 2579, 2591, 2593, 2609, 2617, 2621, 2633, 2647, 2657, 2659, 2663, 2671, 2677, 2683, 2687, 2689, 2693, 2699, 2707, 2711, 2713, 2719, 2729, 2731, 2741, 2749, 2753, 2767, 2777, 2789, 2791, 2797, 2801, 2803, 2819, 2833, 2837, 2843, 2851, 2857, 2861, 2879, 2887, 2897, 2903, 2909, 2917, 2927, 2939, 2953, 2957, 2963, 2969, 2971, 2999, 3001, 3011, 3019, 3023, 3037, 3041, 3049, 3061, 3067, 3079, 3083, 3089, 3109, 3119, 3121, 3137, 3163, 3167, 3169, 3181, 3187, 3191, 3203, 3209, 3217, 3221, 3229, 3251, 3253, 3257, 3259, 3271, 3299, 3301, 3307, 3313, 3319, 3323, 3329, 3331, 3343, 3347, 3359, 3361, 3371, 3373, 3389, 3391, 3407, 3413, 3433, 3449, 3457, 3461, 3463, 3467, 3469, 3491, 3499, 3511, 3517, 3527, 3529, 3533, 3539, 3541, 3547, 3557, 3559, 3571, 3581, 3583, 3593, 3607, 3613, 3617, 3623, 3631, 3637, 3643, 3659, 3671, 3673, 3677, 3691, 3697, 3701, 3709, 3719, 3727, 3733, 3739, 3761, 3767, 3769, 3779, 3793, 3797, 3803, 3821, 3823, 3833, 3847, 3851, 3853, 3863, 3877, 3881, 3889, 3907, 3911, 3917, 3919, 3923, 3929, 3931, 3943, 3947, 3967, 3989, 4001, 4003, 4007, 4013, 4019, 4021, 4027, 4049, 4051, 4057, 4073, 4079, 4091, 4093, 4099, 4111, 4127, 4129, 4133, 4139, 4153, 4157, 4159, 4177, 4201, 4211, 4217, 4219, 4229, 4231, 4241, 4243, 4253, 4259, 4261, 4271, 4273, 4283, 4289, 4297, 4327, 4337, 4339, 4349, 4357, 4363, 4373, 4391, 4397, 4409, 4421, 4423, 4441, 4447, 4451, 4457, 4463, 4481, 4483, 4493, 4507, 4513, 4517, 4519, 4523, 4547, 4549, 4561, 4567, 4583, 4591, 4597, 4603, 4621, 4637, 4639, 4643, 4649, 4651, 4657, 4663, 4673, 4679, 4691, 4703, 4721, 4723, 4729, 4733, 4751, 4759, 4783, 4787, 4789, 4793, 4799, 4801, 4813, 4817, 4831, 4861, 4871, 4877, 4889, 4903, 4909, 4919, 4931, 4933, 4937, 4943, 4951, 4957, 4967, 4969, 4973, 4987, 4993, 4999, 5003, 5009, 5011, 5021, 5023, 5039, 5051, 5059, 5077, 5081, 5087, 5099, 5101, 5107, 5113, 5119, 5147, 5153, 5167, 5171, 5179, 5189, 5197, 5209, 5227, 5231, 5233, 5237, 5261, 5273, 5279, 5281, 5297, 5303, 5309, 5323, 5333, 5347, 5351, 5381, 5387, 5393, 5399, 5407, 5413, 5417, 5419, 5431, 5437, 5441, 5443, 5449, 5471, 5477, 5479, 5483, 5501, 5503, 5507, 5519, 5521, 5527, 5531, 5557, 5563, 5569, 5573, 5581, 5591, 5623, 5639, 5641, 5647, 5651, 5653, 5657, 5659, 5669, 5683, 5689, 5693, 5701, 5711, 5717, 5737, 5741, 5743, 5749, 5779, 5783, 5791, 5801, 5807, 5813, 5821, 5827, 5839, 5843, 5849, 5851, 5857, 5861, 5867, 5869, 5879, 5881, 5897, 5903, 5923, 5927, 5939, 5953, 5981, 5987, 6007, 6011, 6029, 6037, 6043, 6047, 6053, 6067, 6073, 6079, 6089, 6091, 6101, 6113, 6121, 6131, 6133, 6143, 6151, 6163, 6173, 6197, 6199, 6203, 6211, 6217, 6221, 6229, 6247, 6257, 6263, 6269, 6271, 6277, 6287, 6299, 6301, 6311, 6317, 6323, 6329, 6337, 6343, 6353, 6359, 6361, 6367, 6373, 6379, 6389, 6397, 6421, 6427, 6449, 6451, 6469, 6473, 6481, 6491, 6521, 6529, 6547, 6551, 6553, 6563, 6569, 6571, 6577, 6581, 6599, 6607, 6619, 6637, 6653, 6659, 6661, 6673, 6679, 6689, 6691, 6701, 6703, 6709, 6719, 6733, 6737, 6761, 6763, 6779, 6781, 6791, 6793, 6803, 6823, 6827, 6829, 6833, 6841, 6857, 6863, 6869, 6871, 6883, 6899, 6907, 6911, 6917, 6947, 6949, 6959, 6961, 6967, 6971, 6977, 6983, 6991, 6997, 7001, 7013, 7019, 7027, 7039, 7043, 7057, 7069, 7079, 7103, 7109, 7121, 7127, 7129, 7151, 7159, 7177, 7187, 7193, 7207, 7211, 7213, 7219, 7229, 7237, 7243, 7247, 7253, 7283, 7297, 7307, 7309, 7321, 7331, 7333, 7349, 7351, 7369, 7393, 7411, 7417, 7433, 7451, 7457, 7459, 7477, 7481, 7487, 7489, 7499, 7507, 7517, 7523, 7529, 7537, 7541, 7547, 7549, 7559, 7561, 7573, 7577, 7583, 7589, 7591, 7603, 7607, 7621, 7639, 7643, 7649, 7669, 7673, 7681, 7687, 7691, 7699, 7703, 7717, 7723, 7727, 7741, 7753, 7757, 7759, 7789, 7793, 7817, 7823, 7829, 7841, 7853, 7867, 7873, 7877, 7879, 7883, 7901, 7907, 7919, 7927, 7933, 7937, 7949, 7951, 7963, 7993, 8009, 8011, 8017, 8039, 8053, 8059, 8069, 8081, 8087, 8089, 8093, 8101, 8111, 8117, 8123, 8147, 8161, 8167, 8171, 8179, 8191, 8209, 8219, 8221, 8231, 8233, 8237, 8243, 8263, 8269, 8273, 8287, 8291, 8293, 8297, 8311, 8317, 8329, 8353, 8363, 8369, 8377, 8387, 8389, 8419, 8423, 8429, 8431, 8443, 8447, 8461, 8467, 8501, 8513, 8521, 8527, 8537, 8539, 8543, 8563, 8573, 8581, 8597, 8599, 8609, 8623, 8627, 8629, 8641, 8647, 8663, 8669, 8677, 8681, 8689, 8693, 8699, 8707, 8713, 8719, 8731, 8737, 8741, 8747, 8753, 8761, 8779, 8783, 8803, 8807, 8819, 8821, 8831, 8837, 8839, 8849, 8861, 8863, 8867, 8887, 8893, 8923, 8929, 8933, 8941, 8951, 8963, 8969, 8971, 8999, 9001, 9007, 9011, 9013, 9029, 9041, 9043, 9049, 9059, 9067, 9091, 9103, 9109, 9127, 9133, 9137, 9151, 9157, 9161, 9173, 9181, 9187, 9199, 9203, 9209, 9221, 9227, 9239, 9241, 9257, 9277, 9281, 9283, 9293, 9311, 9319, 9323, 9337, 9341, 9343, 9349, 9371, 9377, 9391, 9397, 9403, 9413, 9419, 9421, 9431, 9433, 9437, 9439, 9461, 9463, 9467, 9473, 9479, 9491, 9497, 9511, 9521, 9533, 9539, 9547, 9551, 9587, 9601, 9613, 9619, 9623, 9629, 9631, 9643, 9649, 9661, 9677, 9679, 9689, 9697, 9719, 9721, 9733, 9739, 9743, 9749, 9767, 9769, 9781, 9787, 9791, 9803, 9811, 9817, 9829, 9833, 9839, 9851, 9857, 9859, 9871, 9883, 9887, 9901, 9907, 9923, 9929, 9931, 9941, 9949, 9967, 9973.



Nullwertzahlen up to 10000:

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, 208, 216, 224, 240, 252, 256, 264, 280, 288, 300, 312, 320, 324, 336, 352, 360, 384, 392, 396, 400, 408, 416, 420, 432, 440, 448, 456, 468, 480, 504, 512, 520, 528, 540, 544, 552, 560, 576, 588, 600, 608, 612, 616, 624, 640, 648, 660, 672, 680, 684, 704, 720, 728, 736, 756, 760, 768, 780, 784, 792, 800, 816, 828, 832, 840, 864, 880, 896, 900, 912, 920, 924, 928, 936, 952, 960, 972, 992, 1000, 1008, 1020, 1024, 1040, 1044, 1056, 1064, 1080, 1088, 1092, 1104, 1116, 1120, 1140, 1152, 1160, 1176, 1188, 1200, 1216, 1224, 1232, 1240, 1248, 1260, 1280, 1288, 1296, 1320, 1344, 1360, 1368, 1380, 1392, 1400, 1404, 1408, 1428, 1440, 1452, 1456, 1472, 1480, 1488, 1500, 1512, 1520, 1536, 1560, 1568, 1584, 1596, 1600, 1620, 1624, 1632, 1656, 1664, 1680, 1716, 1728, 1736, 1740, 1760, 1764, 1776, 1792, 1800, 1824, 1836, 1840, 1848, 1856, 1860, 1872, 1904, 1920, 1932, 1936, 1944, 1960, 1968, 1980, 1984, 2000, 2016, 2040, 2048, 2052, 2064, 2072, 2080, 2088, 2100, 2112, 2128, 2160, 2176, 2184, 2200, 2208, 2220, 2232, 2240, 2244, 2256, 2268, 2280, 2288, 2296, 2304, 2320, 2340, 2352, 2368, 2376, 2400, 2408, 2432, 2436, 2448, 2460, 2464, 2480, 2484, 2496, 2508, 2520, 2560, 2576, 2580, 2592, 2600, 2604, 2624, 2632, 2640, 2664, 2688, 2700, 2704, 2720, 2736, 2744, 2752, 2760, 2772, 2784, 2800, 2808, 2816, 2820, 2856, 2880, 2904, 2912, 2916, 2940, 2944, 2952, 2960, 2968, 2976, 2992, 3000, 3008, 3024, 3036, 3040, 3060, 3072, 3080, 3096, 3108, 3120, 3132, 3136, 3168, 3180, 3192, 3200, 3240, 3248, 3264, 3276, 3280, 3300, 3312, 3328, 3344, 3348, 3360, 3384, 3392, 3400, 3420, 3432, 3440, 3444, 3456, 3472, 3480, 3520, 3528, 3536, 3540, 3552, 3564, 3584, 3600, 3612, 3640, 3648, 3672, 3680, 3696, 3712, 3720, 3744, 3760, 3776, 3780, 3800, 3808, 3816, 3828, 3840, 3864, 3872, 3888, 3900, 3904, 3920, 3936, 3948, 3952, 3960, 3968, 3996, 4000, 4032, 4048, 4056, 4080, 4092, 4096, 4104, 4116, 4128, 4140, 4144, 4160, 4176, 4200, 4212, 4224, 4240, 4248, 4256, 4284, 4312, 4320, 4352, 4356, 4368, 4392, 4400, 4416, 4428, 4440, 4452, 4464, 4480, 4488, 4500, 4512, 4536, 4560, 4576, 4592, 4600, 4608, 4620, 4640, 4644, 4680, 4704, 4720, 4736, 4752, 4760, 4784, 4788, 4800, 4816, 4824, 4840, 4860, 4864, 4872, 4880, 4884, 4896, 4920, 4928, 4956, 4960, 4968, 4992, 5000, 5016, 5040, 5076, 5088, 5096, 5100, 5104, 5112, 5120, 5124, 5148, 5152, 5160, 5184, 5200, 5208, 5220, 5248, 5264, 5280, 5292, 5304, 5320, 5328, 5360, 5376, 5400, 5408, 5412, 5440, 5456, 5460, 5472, 5488, 5504, 5508, 5520, 5544, 5568, 5580, 5600, 5616, 5628, 5632, 5640, 5664, 5676, 5680, 5700, 5712, 5720, 5724, 5760, 5796, 5800, 5808, 5824, 5832, 5840, 5856, 5880, 5888, 5904, 5920, 5928, 5936, 5940, 5952, 5964, 5984, 6000, 6016, 6032, 6048, 6072, 6080, 6084, 6120, 6132, 6144, 6156, 6160, 6192, 6200, 6204, 6216, 6240, 6264, 6272, 6300, 6320, 6336, 6360, 6372, 6384, 6400, 6432, 6440, 6448, 6468, 6480, 6496, 6512, 6528, 6552, 6560, 6588, 6600, 6608, 6624, 6636, 6656, 6660, 6664, 6688, 6696, 6720, 6732, 6760, 6768, 6776, 6784, 6800, 6804, 6816, 6832, 6840, 6864, 6880, 6888, 6900, 6912, 6936, 6944, 6960, 6972, 6996, 7000, 7008, 7020, 7040, 7056, 7072, 7080, 7104, 7128, 7140, 7168, 7176, 7200, 7216, 7224, 7236, 7260, 7280, 7296, 7308, 7320, 7344, 7360, 7380, 7392, 7400, 7424, 7440, 7448, 7452, 7480, 7488, 7500, 7504, 7520, 7524, 7552, 7560, 7568, 7584, 7600, 7616, 7632, 7644, 7656, 7668, 7680, 7696, 7728, 7740, 7744, 7752, 7776, 7788, 7800, 7808, 7812, 7840, 7872, 7884, 7896, 7904, 7920, 7936, 7952, 7956, 7968, 7980, 7992, 8000, 8008, 8040, 8052, 8064, 8096, 8100, 8112, 8120, 8160, 8176, 8184, 8192, 8200, 8208, 8232, 8256, 8272, 8280, 8288, 8316, 8320, 8352, 8360, 8400, 8424, 8448, 8460, 8480, 8496, 8512, 8520, 8528, 8532, 8544, 8568, 8576, 8580, 8600, 8624, 8640, 8664, 8680, 8700, 8704, 8712, 8736, 8748, 8760, 8784, 8800, 8820, 8832, 8840, 8844, 8848, 8856, 8880, 8892, 8904, 8928, 8944, 8960, 8964, 8976, 9000, 9016, 9024, 9048, 9072, 9088, 9108, 9120, 9152, 9180, 9184, 9200, 9216, 9240, 9248, 9280, 9288, 9296, 9300, 9324, 9328, 9344, 9360, 9372, 9384, 9396, 9400, 9408, 9440, 9464, 9472, 9480, 9504, 9520, 9540, 9568, 9576, 9600, 9612, 9632, 9636, 9648, 9660, 9672, 9680, 9720, 9728, 9744, 9760, 9768, 9776, 9792, 9800, 9828, 9840, 9856, 9880, 9900, 9912, 9920, 9936, 9960, 9968, 9984, 9996, 10000.



If you look at the distribution of the prime numbers as well as the distribution of the Nullwertzahlen, you will see amazing similarities on the one hand, but also some interesting differences on the other.


Number of divisors:

Prime number: 2
Nullwertzahl: at least C * ln n
___________________________________

Number of prim divisors:

Prime number: 1
Nullwertzahl: at least C * ln ln n
___________________________________

Construction:

Prim number: very difficult
Nullwertzahl: very easy
____________________________________

Determination of the prime divisors:

Prim number: very easy
Nullwertzahl: difficult
______________________________________

Congruence without the number 2:

Prim number: 1 mod 4 or 3 mod 4
Nullwertzahl: 0 mod 4
________________________________________

Difference of twins:

Prim number: 2
Nullwertzahl : 4
________________________________________

Construction of twins:

Prim number (p is prime und p + 2 is also prime): very difficult
Nullwertzahl (n is Nullwertzahl and n + 4 is also Nullwertzahl): very difficult
_________________________________________

Number of twins up to n:

Prim number: presumably O(n / (ln n)[SUP]2[/SUP])
Nullwertzahlen: presumably O(n / (ln n)[SUP]2[/SUP])
_____________________________________________

Distribution pattern locally:

Prim number: chaotic statistical
Nullwertzahlen: chaotic statistical [U][B]plus Chaos surcharge for self-similarity reflection[/B][/U]
____________________________________________

Distribution pattern global:

Prim number: regularly
Nullwertzahlen: regularly with greater fuzziness because of [U][B]Chaos surcharge for self-similarity reflection[/B][/U]
____________________________________________

Maximum distance between two immediate neighbors:

Prim number: presumably O((ln n)[SUP]2[/SUP])
Nullwertzahl: presumably O((ln n)[SUP]2[/SUP])


Note:

Even if the Riemann hypothesis, which has not yet been proven, should apply, it can be assumed that it can [U][B]only be proven[/B][/U] that the maximum distance between two immediately adjacent prime numbers in the number range up to n is at most O (n[SUP]0.5[/SUP]), since the zeros of the continuation of the Riemannian Zeta function with real part 0.5 have a statistical background noise of C * n ^ 0.5 / ln n and also infinitely often for every constant C, however large, both R (x) - pi (x)> C * x [SUP] 0.5 [/ SUP] / ln x and pi (x) - R (x)> C * x [SUP] 0.5 [/ SUP] / ln x is forced. [U][B]For the Nullwertzahlen plus the chaos surcharge for self-similarity reflection![/B][/U]


Direct comparison of the functions W[SUB]0[/SUB](n) and Pi (n) for the powers of ten from 1 to 12:


W[SUB]0[/SUB](10) = 3
Pi(10) = 4
W[SUB]0[/SUB](10) / Pi(10) = 0.75
_____________________________________________

W[SUB]0[/SUB](100) = 17
Pi(100) = 25
W[SUB]0[/SUB](100) / Pi(100) = 0.68
_____________________________________________

W[SUB]0[/SUB](10[SUP]3[/SUP]) = 108
Pi(10[SUP]3[/SUP]) = 168
W[SUB]0[/SUB](10[SUP]3[/SUP]) / Pi(10[SUP]3[/SUP]) = 0.642857...
_____________________________________________

W[SUB]0[/SUB](10[SUP]4[/SUP]) = 755
Pi(10[SUP]4[/SUP]) = 1229
W[SUB]0[/SUB](10[SUP]4[/SUP]) / Pi(10[SUP]4[/SUP]) = 0.61432...
_____________________________________________

W[SUB]0[/SUB](10[SUP]5[/SUP]) = 5936
Pi(10[SUP]5[/SUP]) = 9592
W[SUB]0[/SUB](10[SUP]5[/SUP]) / Pi(10[SUP]5[/SUP]) = 0.618849...
_____________________________________________

W[SUB]0[/SUB](10[SUP]6[/SUP]) = 48474
Pi(10[SUP]6[/SUP]) = 78498
W[SUB]0[/SUB](10[SUP]6[/SUP]) / Pi(10[SUP]6[/SUP]) = 0.6175...
_____________________________________________

W[SUB]0[/SUB](10[SUP]7[/SUP]) = 406270
Pi(10[SUP]7[/SUP]) = 664579
W[SUB]0[/SUB](10[SUP]7[/SUP]) / Pi(10[SUP]7[/SUP]) = 0.611319...
_____________________________________________

W[SUB]0[/SUB](10[SUP]8[/SUP]) = 3532031
Pi(10[SUP]8[/SUP]) = 5761455
W[SUB]0[/SUB](10[SUP]8[/SUP]) / Pi(10[SUP]8[/SUP]) = 0.61304...
_____________________________________________

W[SUB]0[/SUB](10[SUP]9[/SUP]) = 31295358
Pi(10[SUP]9[/SUP]) = 50847534
W[SUB]0[/SUB](10[SUP]9[/SUP]) / Pi(10[SUP]9[/SUP]) = 0.61547...
_____________________________________________

W[SUB]0[/SUB](10[SUP]10[/SUP]) = 279591668
Pi(10[SUP]10[/SUP]) = 455052511
W[SUB]0[/SUB](10[SUP]10[/SUP]) / Pi(10[SUP]10[/SUP]) = 0.6144...
_____________________________________________

W[SUB]0[/SUB](10[SUP]11[/SUP]) = 2521429242
Pi(10[SUP]11[/SUP]) = 4118054813
W[SUB]0[/SUB](10[SUP]11[/SUP]) / Pi(10[SUP]8[/SUP]) = 0.612286...
_____________________________________________

W[SUB]0[/SUB](10[SUP]12[/SUP]) = 22996137423
Pi(10[SUP]12[/SUP]) = 37607912018
W[SUB]0[/SUB](10[SUP]12[/SUP]) / Pi(10[SUP]12[/SUP]) = 0.61147....

ThomasK 2021-08-18 08:55

You can find our last article on Minimum at the following link, Page 57 - 66:


[URL]https://moodle.phst.at/pluginfile.php/308884/course/section/54892/006d1ba42c_SdW_highlights_201502_ges.pdf[/URL]


The article is in German, but many things should be understandable even without knowledge of the German language.

arbooker 2021-10-19 14:47

Interesting game. Maybe you know this already, but there is a simple proof that the Nullwertzahlen have density 0: any Nullwertzahl [$]n[/$] satisfies [$]n\le2^{2^{\Omega(n)-1}}[/$], so that [$]\Omega(n)>\log\log(n)/\log(2)[/$]. As you pointed out in another post, [$]\Omega(n)[/$] is almost always close to [$]\log\log{n}[/$], so very few [$]n[/$] have so many prime factors. Following the proof of the Hardy-Ramanujan theorem, I think you can push this as far as a proof that [$]W_0(x)=O(x/(\log{x})^\delta)[/$] for some [$]\delta>0[/$], but I don't see how to get [$]\delta=1[/$] from just this.

ThomasK 2021-11-01 23:11

[QUOTE=arbooker;591068]Interesting game. Maybe you know this already, but there is a simple proof that the Nullwertzahlen have density 0: any Nullwertzahl [$]n[/$] satisfies [$]n\le2^{2^{\Omega(n)-1}}[/$], so that [$]\Omega(n)>\log\log(n)/\log(2)[/$]. As you pointed out in another post, [$]\Omega(n)[/$] is almost always close to [$]\log\log{n}[/$], so very few [$]n[/$] have so many prime factors. Following the proof of the Hardy-Ramanujan theorem, I think you can push this as far as a proof that [$]W_0(x)=O(x/(\log{x})^\delta)[/$] for some [$]\delta>0[/$], but I don't see how to get [$]\delta=1[/$] from just this.[/QUOTE]




Thanks very much. That's right; a randomly drawn natural number n has approximately ln ln n + O (1) prime factors, where the standard deviation is O ((ln ln n) ^ 0.5). The number of all natural numbers less than or equal to n that have [U][B]exactly[/B][/U] k prime factors is asyptotically n * (ln ln n) ^ (k-1) / ((ln n) * (k-1)!)



For k = 1, the prime number theorem results as a special case, which says that the number of prime numbers less than or equal to n is asymptotically about n / ln n.

For k = 2, all natural numbers are counted with exactly 2 prime factors, e.g. 4453 = 61 * 73 is a semi-prime number.

The number of all semi-prime numbers less than or equal to n is thus asymptotically n * ln ln n / ln n.
The number of all natural numbers less than or equal to n that have exactly 3 prime factors is thus asymptotically n * (ln ln n) ^ 2 / (ln n * 2)
The number of all natural numbers less than or equal to n that have exactly 4 prime factors is thus asymptotically n * (ln ln n) ^ 3 / (ln n * 6)
The number of all natural numbers less than or equal to n that have exactly 5 prime factors is thus asymptotically n * (ln ln n) ^ 4 / (ln n * 24)

etc.


_________________________


We are now considering extending the minimum total analysis, which was previously performed to 10 ^ 12, to 10 ^ 17. We do not yet believe that we will reach the smallest Fünfwertzahl (five-valued number) that we expect at around 10 ^ 18. Nevertheless, the minimum total analysis up to 10^17 would enable us to make a significantly improved extrapolation.

Anyone who has ideas on how to efficiently carry out a minimum total analysis that runs on 1000 processors at the same time, for example, can post his ideas in this thread.

How big should the basic block be?
How can the algorithm be efficiently parallelized?
Which programming language is best suited for the minimum total analysis up to 10^17?
Should the minimum total analysis be calculated up to 10^17 in a cloud?
How many and, if applicable, which prime numbers should be stored for the minimum total analysis up to 10^17?

ThomasK 2021-12-14 17:20

As I just learned, mathematics professor Andreas Weingartner from Southern Utah University, Cedar City, Utah, USA has proven the following:


lim n-> infinite Wo(n) / (0.612415 .... * x / ln x) = 1


I don't know the proof yet, but on June 30th, 2021 the proof was confirmed on [URL]https://oeis.org/A047836[/URL].

This constant 0.612415 ... we call it the constant of the Nullwertzahlen.

Professor Andreas Weingartner has proven even more.


The following applies: Wo(n) = 0.612415... * n / ln n + O (n / (ln n )^2)

Many thanks to Professor Andreas Weingartner. This is a significant improvement on what we previously knew. So far, we have only conjectured what he has proven.


All times are UTC. The time now is 11:11.

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, Jelsoft Enterprises Ltd.