login
This site is supported by donations to The OEIS Foundation.

 

Logo

Annual Appeal: Today, Nov 11 2014, is the 4th anniversary of the launch of the new OEIS web site. 70,000 sequences have been added in these four years, all edited by volunteers. Please make a donation (tax deductible in the US) to help keep the OEIS running.

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)
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. 292-295.

R. K. Guy and R. J. Nowakowski, Monthly unsolved problems, 1969-1995, Amer. Math. Monthly, 102 (1995), 921-926.

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).

LINKS

T. D. Noe, Table of n, a(n) for n = 1..10000

Paul Pollack, On the parity of the number of multiplicative partitions and related problems, 2012.

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), 1-28.

R. E. Canfield, P. Erdos 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

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/(1-1/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

(PARI code using Dirichlet g.f., based om Somos's code for A007896, from N. J. A. Sloane, May 26 2014)

{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))

(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 */

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

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

Content is available under The OEIS End-User License Agreement .

Last modified November 24 15:00 EST 2014. Contains 249899 sequences.