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

2021-08-10, 05:01   #12
Happy5214

"Alexander"
Nov 2008
The Alamo City

19×41 Posts

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

2021-08-10, 07:25   #13
axn

Jun 2003

52×211 Posts

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

2021-08-10, 11:43   #14
R. Gerbicz

"Robert Gerbicz"
Oct 2005
Hungary

1,531 Posts

Quote:
 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(n0.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,
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)))
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

Last fiddled with by R. Gerbicz on 2021-08-10 at 11:45

2021-08-10, 12:07   #15
Viliam Furik

"Viliam Furík"
Jul 2018
Martin, Slovakia

2×373 Posts

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

 2021-08-10, 12:58 #16 ThomasK   Aug 2021 2·5 Posts 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. W0(10): 3 W1(10): 6 W2(10): 0 W3(10): 0 W4(10): 0 W0(100): 17 W1(100): 71 W2(100): 11 W3(100): 0 W4(100): 0 W0(103): 108 W1(103): 686 W2(103): 201 W3(103): 4 W4(103): 0 W0(104): 755 W1(104): 6598 W2(104): 2592 W3(104): 54 W4(104): 0 W0(105): 5936 W1(105): 63449 W2(105): 29916 W3(105): 698 W4(105): 0 W0(106): 48474 W1(106): 614400 W2(106): 328988 W3(106): 8137 W4(106): 0 W0(107): 406270 W1(107): 5952657 W2(107): 3550745 W3(107): 90324 W4(107): 3 W0(108): 3532031 W1(108): 58088295 W2(108): 37432690 W3(108): 946964 W4(108): 19 W0(109): 31295358 W1(109): 568932663 W2(109): 390065916 W3(109): 9705879 W4(109): 183 W0(1010): 279591668 W1(1010): 5588087493 W2(1010): 4034529147 W3(1010): 97790090 W4(1010): 1601 W0(1011): 2521429242 W1(1011): 54968844332 W2(1011): 41532029309 W3(1011): 977682518 W4(1011): 14598 W0(1012): 22996137423 W1(1012): 541664112990 W2(1012): 425608837164 W3(1012): 9730782305 W4(1012): 130117 Note: Always the sum is not 10n but 10n - 1, because W (1) is not defined. _____________________________________________________ When we calculated a total analysis up to 1010 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 1010 the proportion of Dreiwertzahlen increases. That is a contradiction. To solve the problem we decided to do the total analysis up to 1012. 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 1024 the Zweiwertzahlen will overtake the Einswertzahlen, i.e. W2(n) > W1(n) for all n > around 1024. 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.
2021-08-10, 22:02   #17
ThomasK

Aug 2021

10102 Posts

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

Last fiddled with by ThomasK on 2021-08-10 at 22:05

 2021-08-12, 13:02 #18 ThomasK   Aug 2021 2×5 Posts Theorem of value restriction of sufficiently large potencies: n is a natural number with n >= 2 Then applies W (nk) = 0 for all k > = ln n / ln 2 - 1 if n is even W (nk) = 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(2k) = 0 for all k = 1, 2, 3, 4, ....(Powers of 4 included) W(3k) = 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 nk = 2k * (n/2)k. In the worst case, n / 2 is a prime number. But if n / 2 <= 2k, you can divide each away n / 2 in the first k steps and get the Nullwertzahl 2k. A sufficient condition for nk to be a Nullwertzahl is therefore 2k > = n / 2 or k > = ln (n / 2) / ln 2 = ln n / ln 2 - 1. Second case: n is odd n2 - 1 = (n + 1)(n - 1) = 22 * (n + 1) / 2 * (n - 1) / 2 n4 - 1 = (n2 + 1)(n2 - 1) = (n2 + 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 = 2j is a power of 2. Then we subtract one from nk and get nk - 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 2j > = (n - 1) / 4 follows. In the general case that k is not a power of 2, we divide n from nk away until the remaining exponent is a power of 2 that is 2j. The original exponent k must shrink by half at most. So if k > = (n - 1) / 2, then 2j > = (n - 1) / 4. So it follows that W (nk) = 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 W0, the set of all Einswertzahlen with W1, the set of all Zweiwertzahlen with W2, the set of all Dreiwertzahlen with W3, the set of all Vierwertzahlen with W4, and the set of all k-valued numbers with Wk. 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 Wk 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 1012, but we took a random look at the distribution of the numbers above 1012. The following table shows the number of Nullwertzahlen up to the Vierwertzahlen in the first milliard above 1012, 1013 and 1014. 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 1018. W0(1012 + 109) - W0(1012): 22129699 W1(1012 + 109) - W1(1012): 538366808 W2(1012 + 109) - W2(1012): 429800315 W3(1012 + 109) - W3(1012): 9703057 W4(1012 + 109) - W4(1012): 121 W0(1013 + 109) - W0(1013): 20455311 W1(1013 + 109) - W1(1013): 531664281 W2(1013 + 109) - W2(1013): 438266115 W3(1013 + 109) - W3(1013): 9614183 W4(1013 + 109) - W4(1013): 110 W0(1014 + 109) - W0(1014): 19015775 W1(1014 + 109) - W1(1014): 525804423 W2(1014 + 109) - W2(1014): 445685370 W3(1014 + 109) - W3(1014): 9494338 W4(1014 + 109) - W4(1014): 94 In the next Posting we will compare the Nullwertzahlen with the prime numbers. The comparison of the functions W0(n) and pi (n) is very interesting.
 2021-08-17, 00:34 #19 ThomasK   Aug 2021 10102 Posts 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 W0(x). Pi (x) is the number of prime numbers less than or equal to x and W0(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)2) Nullwertzahlen: presumably O(n / (ln n)2) _____________________________________________ 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)2) Nullwertzahl: presumably O((ln n)2) 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 (n0.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 W0(n) and Pi (n) for the powers of ten from 1 to 12: W0(10) = 3 Pi(10) = 4 W0(10) / Pi(10) = 0.75 _____________________________________________ W0(100) = 17 Pi(100) = 25 W0(100) / Pi(100) = 0.68 _____________________________________________ W0(103) = 108 Pi(103) = 168 W0(103) / Pi(103) = 0.642857... _____________________________________________ W0(104) = 755 Pi(104) = 1229 W0(104) / Pi(104) = 0.61432... _____________________________________________ W0(105) = 5936 Pi(105) = 9592 W0(105) / Pi(105) = 0.618849... _____________________________________________ W0(106) = 48474 Pi(106) = 78498 W0(106) / Pi(106) = 0.6175... _____________________________________________ W0(107) = 406270 Pi(107) = 664579 W0(107) / Pi(107) = 0.611319... _____________________________________________ W0(108) = 3532031 Pi(108) = 5761455 W0(108) / Pi(108) = 0.61304... _____________________________________________ W0(109) = 31295358 Pi(109) = 50847534 W0(109) / Pi(109) = 0.61547... _____________________________________________ W0(1010) = 279591668 Pi(1010) = 455052511 W0(1010) / Pi(1010) = 0.6144... _____________________________________________ W0(1011) = 2521429242 Pi(1011) = 4118054813 W0(1011) / Pi(108) = 0.612286... _____________________________________________ W0(1012) = 22996137423 Pi(1012) = 37607912018 W0(1012) / Pi(1012) = 0.61147....
 2021-08-18, 08:55 #20 ThomasK   Aug 2021 2·5 Posts 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.
 2021-10-19, 14:47 #21 arbooker     "Andrew Booker" Mar 2013 3·29 Posts 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.
2021-11-01, 23:11   #22
ThomasK

Aug 2021

2×5 Posts

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

 Thread Tools

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

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

Fri Jan 28 11:29:31 UTC 2022 up 189 days, 5:58, 2 users, load averages: 1.37, 1.63, 1.50

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

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

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

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