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(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): pn 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[n1]+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 PARIGp,
Code:
F(E)={W=vector(2^E,n,E);
W[1]=W[2]=0;
for(e=1,E1,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[n1]+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