

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)


84



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]


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.
D. Beckwith, Problem 10669, Amer. Math. Monthly 105 (1998), p. 559.
S. R. Finch, Mathematical Constants, Cambridge, 2003, pp. 292295.
R. K. Guy and R. J. Nowakowski, Monthly unsolved problems, 19691995, Amer. Math. Monthly, 102 (1995), 921926.
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, 2012; http://www.math.uga.edu/~pollack/facts.pdf
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).


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].
R. E. Canfield, P. Erdos and C. Pomerance, On a Problem of Oppenheim concerning "Factorisatio Numerorum", J. Number Theory 17 (1983), 128.
R. E. Canfield, P. Erdos and C. Pomerance, On a Problem of Oppenheim concerning "Factorisatio Numerorum", J. Number Theory 17 (1983), 128. [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
Shamik Ghosh, Counting number of factorizations of a natural number
Florian Luca, Anirban Mukhopadhyay and Kotyada Srinivas, On the Oppenheim's "factorisatio numerorum" function
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.
Marko Riedel, Calculating the multiplicative partition function in Maple with the Polya Enumeration Theorem.
Eric Weisstein's World of Mathematics, Unordered Factorization
Wikipedia, Multiplicative Partition Function
Index entries for "core" sequences


FORMULA

The asymptotic behavior of this sequence was studied by Canfield, Erdos and Pomerance and Luca et al.  Jonathan Vos Post, Jul 07 2008
Dirichlet g.f.: prod{n = 2 to inf}(1/(11/n^s)).
If n = prime^k, a(n) = partitions(k) = A000041(k).
Since A001055 (n) is the right diagonal of A066032 the given recursive formula for A066032 applies (see Maple program).  Reinhard Zumkeller and ulrschimke(AT)aol.com


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 i, A, summe, d: if isprime(n) then: if n <= m then RETURN(1) fi: RETURN(0): fi:
A := divisors(n) minus {n, 1}: for d in A do: if d > m then A := A minus {d}: fi: od: summe := 0: for d in A do: summe := summe + T(n/d, d): od: if n <=m then summe := summe + 1: fi: RETURN(summe): end: A001055 := n > T(n, n): [seq(A001055(n), n=1..100)]; # Reinhard Zumkeller and 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[100] (* c[n, r] is the number of factorizations of n with factors <= r.  Dean Hickerson Oct 28 2002 *)


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
(Haskell)
a001055 = (map last a066032_tabl !!) . (subtract 1)
 Reinhard Zumkeller, Oct 01 2012


CROSSREFS

A045782 gives the range of a(n).
a(p^k)=A000041. a(A002110)=A000110.
For records see A033833, A033834.
Cf. A000041, A002033, A045778, A050322, A050336, A064553, A064554, A064555, A077565, A051731, A005171, A097296, A190938, A216599, A216600, A216601, A216602.
Sequence in context: A033273 A034836 A218320 * A129138 A112970 A112971
Adjacent sequences: A001052 A001053 A001054 * A001056 A001057 A001058


KEYWORD

nonn,easy,nice,core


AUTHOR

N. J. A. Sloane.


EXTENSIONS

Incorrect assertion about asymptotic behavior deleted by N. J. A. Sloane, Jun 08 2009


STATUS

approved



