Thread: Minimum (Number Theory Game) View Single Post
2021-08-10, 11:43   #14
R. Gerbicz

"Robert Gerbicz"
Oct 2005
Hungary

7·229 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