Thread: Minimum (Number Theory Game) View Single Post 2021-08-10, 22:02   #17

Aug 2021

10002 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  