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 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
^{n} for all n > = 3, since W (10
^{n}) = 0 for all n > = 3. The length of the push block is n
^{0.5}. In the total analysis up to 10
^{12}, the basic block was given from 2 to 10
^{6}. The first push block ranged from 10
^{6} + 1 to 2 * 10
^{6}, the second push block from 2 * 10
^{6} + 1 to 3 * 10
^{6}, the nth push block from n * 10 ^ 6 + 1 to (n + 1) * 10 ^ 6 and the last push block from (10
^{6}  1) * 10
^{6} to 10
^{6} * 10
^{6}. 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> = (n1) / 2 if n is odd