The OEIS is supported by the many generous donors to the OEIS Foundation. Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A001055 The multiplicative partition function: number of ways of factoring n with all factors greater than 1 (a(1) = 1 by convention). (Formerly M0095 N0032) 692
 1, 1, 1, 2, 1, 2, 1, 3, 2, 2, 1, 4, 1, 2, 2, 5, 1, 4, 1, 4, 2, 2, 1, 7, 2, 2, 3, 4, 1, 5, 1, 7, 2, 2, 2, 9, 1, 2, 2, 7, 1, 5, 1, 4, 4, 2, 1, 12, 2, 4, 2, 4, 1, 7, 2, 7, 2, 2, 1, 11, 1, 2, 4, 11, 2, 5, 1, 4, 2, 5, 1, 16, 1, 2, 4, 4, 2, 5, 1, 12, 5, 2, 1, 11, 2, 2, 2, 7, 1, 11, 2, 4, 2, 2, 2, 19, 1, 4, 4, 9, 1, 5, 1 (list; graph; refs; listen; history; text; internal format)
 OFFSET 1,4 COMMENTS From David W. Wilson, Feb 28 2009: (Start) By a factorization of n we mean a multiset of integers > 1 whose product is n. For example, 6 is the product of 2 such multisets, {2, 3} and {6}, so a(6) = 2. Similarly 8 is the product of 3 such multisets, {2, 2, 2}, {2, 4} and {8}, so a(8) = 3. 1 is the product of 1 such multiset, namely the empty multiset {}, whose product is by definition the multiplicative identity 1. Hence a(1) = 1. (End) a(n) = # { k | A064553(k) = n }. - Reinhard Zumkeller, Sep 21 2001; Benoit Cloitre and N. J. A. Sloane, May 15 2002 Number of members of A025487 with n divisors. - Matthew Vandermast, Jul 12 2004 See sequence A162247 for a list of the factorizations of n and a program for generating the factorizations for any n. - T. D. Noe, Jun 28 2009 So a(n) gives the number of different sorts of prime signature that can be found among the integers that have n divisors. - Michel Marcus, Nov 11 2015 REFERENCES M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards Applied Math. Series 55, 1964 (and various reprintings), p. 844. S. R. Finch, Mathematical Constants, Cambridge, 2003, pp. 292-295. Amarnath Murthy and Charles Ashbacher, Generalized Partitions and Some New Ideas on Number Theory and Smarandache Sequences, Hexis, Phoenix; USA 2005. See Section 1.4. N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence). N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence). G. Tenenbaum, Introduction to analytic and probabilistic number theory, Cambridge University Press, 1995, p. 198, exercise 9 (in the third edition 2015, p. 296, exercise 211). LINKS T. D. Noe, Table of n, a(n) for n = 1..10000 M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards, Applied Math. Series 55, Tenth Printing, 1972 [alternative scanned copy]. D. Beckwith, Problem 10669, Amer. Math. Monthly 105 (1998), p. 559. R. E. Canfield, P. Erdős and C. Pomerance, On a Problem of Oppenheim concerning "Factorisatio Numerorum", J. Number Theory 17 (1983), 1-28. R. E. Canfield, P. Erdős and C. Pomerance, On a Problem of Oppenheim concerning "Factorisatio Numerorum", J. Number Theory 17 (1983), 1-28. [A second link to the same paper.] Marc Chamberland, Colin Johnson, Alice Nadeau, and Bingxi Wu, Multiplicative Partitions, Electronic Journal of Combinatorics, 20(2) (2013), #P57. S. R. Finch, Kalmar's composition constant, Jun 05 2003. [Cached copy, with permission of the author] Shamik Ghosh, Counting number of factorizations of a natural number, arXiv:0811.3479 [cs.DM], 2008. R. K. Guy and R. J. Nowakowski, Monthly unsolved problems, 1969-1995, Amer. Math. Monthly, 102 (1995), 921-926. John F. Hughes and J. O. Shallit, On the Number of Multiplicative Partitions, American Mathematical Monthly 90(7) (1983), 468-471. Cao Hui-Zhong and Ku Tung-Hsin, On the Enumeration Function of Multiplicative Partitions, Math. Balkanica, Vol. 4 (1990), Fasc. 3-4. Florian Luca, Anirban Mukhopadhyay and Kotyada Srinivas, On the Oppenheim's "factorisatio numerorum" function, arXiv:0807.0986 [math.NT], 2008. Pankaj Jyoti Mahanta, On the number of partitions of n whose product of the summands is at most n, arXiv:2010.07353 [math.CO], 2020. Amarnath Murthy, Generalization of Partition Function (Introducing the Smarandache Factor Partition) [Broken link] Amarnath Murthy and Charles Ashbacher, Generalized Partitions and Some New Ideas on Number Theory and Smarandache Sequences, Hexis, Phoenix; USA 2005. See Section 1.4. Paul Pollack, On the parity of the number of multiplicative partitions and related problems, Proc. Amer. Math. Soc. 140 (2012), 3793-3803. Eric Weisstein's World of Mathematics, Unordered Factorization Wikipedia, Multiplicative Partition Function FORMULA The asymptotic behavior of this sequence was studied by Canfield, Erdős & Pomerance and Luca, Mukhopadhyay, & Srinivas. - Jonathan Vos Post, Jul 07 2008 Dirichlet g.f.: Product_{k>=2} 1/(1 - 1/k^s). If n = p^k for a prime p, a(n) = partitions(k) = A000041(k). Since the sequence a(n) is the right diagonal of A066032, the given recursive formula for A066032 applies (see Maple program). - Reinhard Zumkeller and Ulrich Schimke (ulrschimke(AT)aol.com) a(A002110(n)) = A000110(n). EXAMPLE 1: 1, a(1) = 1 2: 2, a(2) = 1 3: 3, a(3) = 1 4: 4 = 2*2, a(4) = 2 6: 6 = 2*3, a(6) = 2 8: 8 = 2*4 = 2*2*2, a(8) = 3 etc. MAPLE with(numtheory): T := proc(n::integer, m::integer)         local A, summe, d:         if isprime(n) then                 if n <= m then                         return 1;                 end if:                 return 0 ;         end if:         A := divisors(n) minus {n, 1}:         for d in A do                 if d > m then                         A := A minus {d}:                 end if:         end do:         summe := add(T(n/d, d), d=A) ;         if n <=m then                 summe := summe + 1:         end if:         summe ; end proc: A001055 := n -> T(n, n): [seq(A001055(n), n=1..100)]; # Reinhard Zumkeller and Ulrich Schimke (ulrschimke(AT)aol.com) MATHEMATICA c[1, r_] := c[1, r]=1; c[n_, r_] := c[n, r] = Module[{ds, i}, ds = Select[Divisors[n], 1 < # <= r &]; Sum[c[n/ds[[i]], ds[[i]]], {i, 1, Length[ds]}]]; a[n_] := c[n, n]; a/@Range (* c[n, r] is the number of factorizations of n with factors <= r. - Dean Hickerson, Oct 28 2002 *) T[_, 1] = T[1, _] = 1; T[n_, m_] := T[n, m] = DivisorSum[n, Boole[1 < # <= m] * T[n/#, #]&]; a[n_] := T[n, n]; a /@ Range (* Jean-François Alcover, Jan 03 2020 *) PROG (PARI) /* factorizations of n with factors <= m (n, m positive integers) */ fcnt(n, m) = {local(s); s=0; if(n == 1, s=1, fordiv(n, d, if(d > 1 & d <= m, s=s+fcnt(n/d, d)))); s} A001055(n) = fcnt(n, n) \\ Michael B. Porter, Oct 29 2009 (PARI) \\ code using Dirichlet g.f., based on Somos's code for A007896 {a(n) = my(A, v, w, m); if( n<1, 0, \\ define unit vector v = [1, 0, 0, ...] of length n v = vector(n, k, k==1); for(k=2, n, m = #digits(n, k) - 1; \\ expand 1/(1-x)^k out far enough A = (1 - x)^ -1 + x * O(x^m); \\ w = zero vector of length n w = vector(n); \\ convert A to a vector for(i=0, m, w[k^i] = polcoeff(A, i)); \\ build the answer v = dirmul(v, w) ); v[n] ) }; \\ produce the sequence vector(100, n, a(n)) \\ N. J. A. Sloane, May 26 2014 (PARI) v=vector(100, k, k==1); for(n=2, #v, v+=dirmul(v, vector(#v, k, (k>1) && n^valuation(k, n)==k)) ); v \\ Max Alekseyev, Jul 16 2014 (Haskell) a001055 = (map last a066032_tabl !!) . (subtract 1) -- Reinhard Zumkeller, Oct 01 2012 (Python) from sympy import divisors, isprime def T(n, m):     if isprime(n): return 1 if n<=m else 0     A=filter(lambda d: d<=m, divisors(n)[1:-1])     s=sum(T(n//d, d) for d in A)     return s + 1 if n<=m else s def a(n): return T(n, n) print([a(n) for n in range(1, 106)]) # Indranil Ghosh, Aug 19 2017 (Java) public class MultiPart {     public static void main(String[] argV) {         for (int i=1; i<=100; ++i) System.out.println(1+getDivisors(2, i));     }     public static int getDivisors(int min, int n) {         int total = 0;         for (int i=min; i=i) { ++total; if (n/i>i) total+=getDivisors(i, n/i); }         return total;     } } \\ Scott R. Shannon, Aug 21 2019 CROSSREFS A045782 gives the range of a(n). For records see A033833, A033834. Cf. A002033, A045778, A050322, A050336, A064553, A064554, A064555, A077565, A051731, A005171, A097296, A190938, A216599, A216600, A216601, A216602. Row sums of A316439 (for n>1). Sequence in context: A355030 A305254 A252665 * A335079 A337093 A320266 Adjacent sequences:  A001052 A001053 A001054 * A001056 A001057 A001058 KEYWORD nonn,easy,nice,core AUTHOR EXTENSIONS Incorrect assertion about asymptotic behavior deleted by N. J. A. Sloane, Jun 08 2009 STATUS approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified September 24 18:11 EDT 2022. Contains 356949 sequences. (Running on oeis4.)