A086435 Maximum number of parts possible in a factorization of n into a product of distinct numbers > 1.

0, 1, 1, 1, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 2, 2, 1, 2, 1, 2, 2, 2, 1, 3, 1, 2, 2, 2, 1, 3, 1, 2, 2, 2, 2, 3, 1, 2, 2, 3, 1, 3, 1, 2, 2, 2, 1, 3, 1, 2, 2, 2, 1, 3, 2, 3, 2, 2, 1, 3, 1, 2, 2, 3, 2, 3, 1, 2, 2, 3, 1, 3, 1, 2, 2, 2, 2, 3, 1, 3, 2, 2, 1, 3, 2, 2, 2, 3, 1, 3, 2, 2, 2, 2, 2, 3, 1, 2, 2, 3, 1, 3, 1, 3, 3

Offset: 1

Author

Eric W. Weisstein, Jul 19 2003

Keywords

• nonn

Comments

For n>1, a((n+1)!) = n is the first occurrence of n in the sequence. This function depends only on the prime signature of n. - Franklin T. Adams-Watters, Dec 19 2006

For integer n and prime p not dividing n, a(n*p) = a(n) + 1. - Max Alekseyev, Apr 23 2010

Examples

			a(6)=2 since 6 may be factored into distinct parts as {{2,3},{6}}, so the largest number of factors possible is 2.
a(8)=2 since 8 may be factored into distinct parts as {{8},{2,4}}, so the largest numbers of factors possible is 2.
		

Links

• Antti Karttunen, Table of n, a(n) for n = 1..10000
• Eric Weisstein's World of Mathematics, Unordered Factorization.
• Index entries for sequences computed from exponents in factorization of n

Crossrefs

Cf. A000142, A025487.

Programs

PARI

{ a(n,m=1) = if(n>m, 1 + vecmax( apply( x->if(x>m,a(n/x,x)), divisors(n) ))) } \\ Max Alekseyev, Jul 16 2009

PARI

{ aopt(n) = local(f,t); f=factor(n)[,2]; t=select(x->x>1,f); a(prod(j=1,#t,prime(j)^t[j])) + #f - #t } /* optimized version */ \\ Max Alekseyev, Apr 23 2010

Extensions

More terms from Max Alekseyev, Apr 23 2010