Minimum (Number Theory Game)

[Happy5214]

Originally Posted by henryzz

The following may or may not be optimal(likely not)
106 / 2
53 - 1
52 / 4
13 - 1
12 / 3
4 / 2

Originally Posted by Viliam Furik

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

Tied for the best?

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

[axn]

Originally Posted by Happy5214

Tied for the best?

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

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]

Originally Posted by ThomasK

The best algorithms for the minimum total analysis up to n have the running time O (n * ln n) and the memory requirement O(n^0.5).

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,

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

The counts for [2,10^6] if you could check: [the counts for the given [2,1000] is good]

W() count
0   48474
1   614400
2   328988
3   8137
4   0
5   0

[Viliam Furik]

Originally Posted by Happy5214

Tied for the best?

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

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

[ThomasK]

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₀(10): 3
W₁(10): 6
W₂(10): 0
W₃(10): 0
W₄(10): 0


W₀(100): 17
W₁(100): 71
W₂(100): 11
W₃(100): 0
W₄(100): 0


W₀(10³): 108
W₁(10³): 686
W₂(10³): 201
W₃(10³): 4
W₄(10³): 0


W₀(10⁴): 755
W₁(10⁴): 6598
W₂(10⁴): 2592
W₃(10⁴): 54
W₄(10⁴): 0


W₀(10⁵): 5936
W₁(10⁵): 63449
W₂(10⁵): 29916
W₃(10⁵): 698
W₄(10⁵): 0


W₀(10⁶): 48474
W₁(10⁶): 614400
W₂(10⁶): 328988
W₃(10⁶): 8137
W₄(10⁶): 0


W₀(10⁷): 406270
W₁(10⁷): 5952657
W₂(10⁷): 3550745
W₃(10⁷): 90324
W₄(10⁷): 3


W₀(10⁸): 3532031
W₁(10⁸): 58088295
W₂(10⁸): 37432690
W₃(10⁸): 946964
W₄(10⁸): 19


W₀(10⁹): 31295358
W₁(10⁹): 568932663
W₂(10⁹): 390065916
W₃(10⁹): 9705879
W₄(10⁹): 183


W₀(10¹⁰): 279591668
W₁(10¹⁰): 5588087493
W₂(10¹⁰): 4034529147
W₃(10¹⁰): 97790090
W₄(10¹⁰): 1601


W₀(10¹¹): 2521429242
W₁(10¹¹): 54968844332
W₂(10¹¹): 41532029309
W₃(10¹¹): 977682518
W₄(10¹¹): 14598


W₀(10¹²): 22996137423
W₁(10¹²): 541664112990
W₂(10¹²): 425608837164
W₃(10¹²): 9730782305
W₄(10¹²): 130117


Note: Always the sum is not 10ⁿ but 10ⁿ - 1, because W (1) is not defined.


_____________________________________________________


When we calculated a total analysis up to 10¹⁰ 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¹⁰ the proportion of Dreiwertzahlen increases.

That is a contradiction. To solve the problem we decided to do the total analysis up to 10¹².

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²⁴ the Zweiwertzahlen will overtake the Einswertzahlen, i.e. W₂(n) > W₁(n) for all n > around 10²⁴.

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]

Originally Posted by R. Gerbicz

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.



(...)

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^0.5. The values ​​of all numbers from 2 to at least n^0.5 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ⁿ for all n > = 3, since W (10ⁿ) = 0 for all n > = 3. The length of the push block is n^0.5. In the total analysis up to 10¹², the basic block was given from 2 to 10⁶. The first push block ranged from 10⁶ + 1 to 2 * 10⁶, the second push block from 2 * 10⁶ + 1 to 3 * 10⁶, the nth push block from n * 10 ^ 6 + 1 to (n + 1) * 10 ^ 6 and the last push block from (10⁶ - 1) * 10⁶ to 10⁶ * 10⁶. 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^k) = 0 for all k> = ln n / ln 2 - 1 if n is even
W (n^k) = 1 for all k> = (n-1) / 2 if n is odd

[ThomasK]

Theorem of value restriction of sufficiently large potencies:

n is a natural number with n >= 2


Then applies

W (n^k) = 0 for all k > = ln n / ln 2 - 1 if n is even
W (n^k) = 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^k) = 0 for all k = 1, 2, 3, 4, ....(Powers of 4 included)
W(3^k) = 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^k = 2^k * (n/2)^k. In the worst case, n / 2 is a prime number.

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


Second case: n is odd

n² - 1 = (n + 1)(n - 1) = 2² * (n + 1) / 2 * (n - 1) / 2
n⁴ - 1 = (n² + 1)(n² - 1) = (n² + 1)(n + 1)(n - 1)

In general

n^{(2^j)} - 1 = (n^{(2^(j-1))} + 1)(n^{(2^(j-1))} - 1) =
2^(j+1) * (n^{(2^(j-1))} + 1) / 2 * (n^{(2^(j-2))} + 1) / 2 * ... * (n^{(2^1)} + 1) / 2 * (n + 1) / 2 * (n - 1) / 2

Let us first take the case that k = 2^j is a power of 2. Then we subtract one from n^k and get n^k - 1, which costs us a move. From the above factorization of n^{(2^j)} - 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^{(2^j)} - 1 is a Nullwertzahl if 2^(j+1) >= (n - 1) / 2, from which 2^j > = (n - 1) / 4 follows.

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


With this the Theorem of value restriction of sufficiently large potencies is completely proved!


__________________________________________________________


This theorem has far-reaching consequences in Minimum theory.

We denote the set of all Nullwertzahlen with W₀, the set of all Einswertzahlen with W₁, the set of all Zweiwertzahlen with W₂, the set of all Dreiwertzahlen with W₃, the set of all Vierwertzahlen with W₄, and the set of all k-valued numbers with W_k.

If every sufficiently large power of EVERY even natural number is a Nullwertzahl and every sufficiently large power of EVERY odd natural number is a Einswertzahl, then the conjecture that the density of the set of all Numbers W_k is 0 is false!

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¹², but we took a random look at the distribution of the numbers above 10¹². The following table shows the number of Nullwertzahlen up to the Vierwertzahlen in the first milliard above 10¹², 10¹³ and 10¹⁴.

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


W₀(10¹² + 10⁹) - W₀(10¹²): 22129699
W₁(10¹² + 10⁹) - W₁(10¹²): 538366808
W₂(10¹² + 10⁹) - W₂(10¹²): 429800315
W₃(10¹² + 10⁹) - W₃(10¹²): 9703057
W₄(10¹² + 10⁹) - W₄(10¹²): 121

W₀(10¹³ + 10⁹) - W₀(10¹³): 20455311
W₁(10¹³ + 10⁹) - W₁(10¹³): 531664281
W₂(10¹³ + 10⁹) - W₂(10¹³): 438266115
W₃(10¹³ + 10⁹) - W₃(10¹³): 9614183
W₄(10¹³ + 10⁹) - W₄(10¹³): 110

W₀(10¹⁴ + 10⁹) - W₀(10¹⁴): 19015775
W₁(10¹⁴ + 10⁹) - W₁(10¹⁴): 525804423
W₂(10¹⁴ + 10⁹) - W₂(10¹⁴): 445685370
W₃(10¹⁴ + 10⁹) - W₃(10¹⁴): 9494338
W₄(10¹⁴ + 10⁹) - W₄(10¹⁴): 94


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

[ThomasK]

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₀(x).

Pi (x) is the number of prime numbers less than or equal to x and W₀(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)²)
Nullwertzahlen: presumably O(n / (ln n)²)
_____________________________________________

Distribution pattern locally:

Prim number: chaotic statistical
Nullwertzahlen: chaotic statistical plus Chaos surcharge for self-similarity reflection
____________________________________________

Distribution pattern global:

Prim number: regularly
Nullwertzahlen: regularly with greater fuzziness because of Chaos surcharge for self-similarity reflection
____________________________________________

Maximum distance between two immediate neighbors:

Prim number: presumably O((ln n)²)
Nullwertzahl: presumably O((ln n)²)


Note:

Even if the Riemann hypothesis, which has not yet been proven, should apply, it can be assumed that it can only be proven that the maximum distance between two immediately adjacent prime numbers in the number range up to n is at most O (n^0.5), 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. For the Nullwertzahlen plus the chaos surcharge for self-similarity reflection!


Direct comparison of the functions W₀(n) and Pi (n) for the powers of ten from 1 to 12:


W₀(10) = 3
Pi(10) = 4
W₀(10) / Pi(10) = 0.75
_____________________________________________

W₀(100) = 17
Pi(100) = 25
W₀(100) / Pi(100) = 0.68
_____________________________________________

W₀(10³) = 108
Pi(10³) = 168
W₀(10³) / Pi(10³) = 0.642857...
_____________________________________________

W₀(10⁴) = 755
Pi(10⁴) = 1229
W₀(10⁴) / Pi(10⁴) = 0.61432...
_____________________________________________

W₀(10⁵) = 5936
Pi(10⁵) = 9592
W₀(10⁵) / Pi(10⁵) = 0.618849...
_____________________________________________

W₀(10⁶) = 48474
Pi(10⁶) = 78498
W₀(10⁶) / Pi(10⁶) = 0.6175...
_____________________________________________

W₀(10⁷) = 406270
Pi(10⁷) = 664579
W₀(10⁷) / Pi(10⁷) = 0.611319...
_____________________________________________

W₀(10⁸) = 3532031
Pi(10⁸) = 5761455
W₀(10⁸) / Pi(10⁸) = 0.61304...
_____________________________________________

W₀(10⁹) = 31295358
Pi(10⁹) = 50847534
W₀(10⁹) / Pi(10⁹) = 0.61547...
_____________________________________________

W₀(10¹⁰) = 279591668
Pi(10¹⁰) = 455052511
W₀(10¹⁰) / Pi(10¹⁰) = 0.6144...
_____________________________________________

W₀(10¹¹) = 2521429242
Pi(10¹¹) = 4118054813
W₀(10¹¹) / Pi(10⁸) = 0.612286...
_____________________________________________

W₀(10¹²) = 22996137423
Pi(10¹²) = 37607912018
W₀(10¹²) / Pi(10¹²) = 0.61147....

[ThomasK]

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


https://moodle.phst.at/pluginfile.ph...201502_ges.pdf


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

[arbooker]

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]

Originally Posted by arbooker

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.

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