login
A167439
Length of the longest partition of n into distinct parts, with each part divisible by the next one.
4
0, 1, 1, 2, 2, 2, 2, 3, 2, 3, 3, 3, 2, 3, 3, 4, 3, 3, 3, 4, 3, 4, 4, 4, 2, 3, 3, 4, 4, 4, 4, 5, 3, 4, 4, 4, 4, 4, 4, 5, 4, 4, 4, 5, 4, 5, 5, 5, 3, 4, 4, 4, 4, 4, 4, 5, 4, 5, 5, 5, 4, 5, 5, 6, 5, 4, 4, 5, 4, 5, 5, 5, 4, 5, 4, 5, 5, 5, 5, 6, 4, 5, 5, 5, 4, 5, 5, 6, 5, 5, 5, 6, 5, 6, 6, 6, 5, 4, 4, 5, 5, 5, 4, 5, 4
OFFSET
0,4
COMMENTS
a(n) > sqrt(log(n))/2.
REFERENCES
V. A. Sadovnichiy, A. A. Grigoryan and S. V. Konyagin (1987), "Problems of mathematical olympiads for university students". Section 4.1, problem 25. (in Russian)
FORMULA
a(n) = max{ A167866(n), A167866(n-1) + 1 }.
PROG
(PARI) { a(n, m=0) = local(r=0); if(n==0, return(0)); fordiv(n, d, if(d<=m, next); r=max(r, 1+a((n-d)\d, 1)) ); r }
CROSSREFS
KEYWORD
nonn
AUTHOR
Max Alekseyev, Nov 13 2009, Nov 15 2009
STATUS
approved