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)

 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

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.

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.

[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

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

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

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.

[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?

All times are UTC. The time now is 04:52.