A167439 Length of the longest partition of n into distinct parts, with each part divisible by the next one.

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

Author

Max Alekseyev, Nov 13 2009, Nov 15 2009

Keywords

• nonn

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)

Crossrefs

Cf. A122651, A167439, A167865, A167866.

Programs

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 }

Formula

a(n) = max{ A167866(n), A167866(n-1) + 1 }.