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

 

Logo


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

%I M0095 N0032

%S 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,

%T 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,

%U 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

%N The multiplicative partition function: number of ways of factoring n with all factors greater than 1 (a(1) = 1 by convention).

%C From _David W. Wilson_, Feb 28 2009: (Start)

%C By a factorization of n we mean a multiset of integers > 1 whose product is n.

%C For example, 6 is the product of 2 such multisets, {2, 3} and {6}, so a(6) = 2.

%C Similarly 8 is the product of 3 such multisets, {2, 2, 2}, {2, 4} and {8}, so a(8) = 3.

%C 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)

%C a(n) = # { k | A064553(k) = n }. - _Reinhard Zumkeller_, Sep 21 2001; _Benoit Cloitre_ and _N. J. A. Sloane_, May 15 2002

%C Number of members of A025487 with n divisors. - _Matthew Vandermast_, Jul 12 2004

%C 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

%C 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

%D 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 S. R. Finch, Mathematical Constants, Cambridge, 2003, pp. 292-295.

%D 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.

%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%H T. D. Noe, <a href="/A001055/b001055.txt">Table of n, a(n) for n = 1..10000</a>

%H M. Abramowitz and I. A. Stegun, eds., <a href="http://www.convertit.com/Go/ConvertIt/Reference/AMS55.ASP">Handbook of Mathematical Functions</a>, National Bureau of Standards, Applied Math. Series 55, Tenth Printing, 1972 [alternative scanned copy].

%H D. Beckwith, <a href="http://www.jstor.org/stable/2589410">Problem 10669</a>, Amer. Math. Monthly 105 (1998), p. 559.

%H R. E. Canfield, P. Erdős and C. Pomerance, <a href="http://math.dartmouth.edu/~carlp/PDF/paper39.pdf">On a Problem of Oppenheim concerning "Factorisatio Numerorum"</a>, J. Number Theory 17 (1983), 1-28.

%H R. E. Canfield, P. Erdős and C. Pomerance, <a href="http://renyi.hu/~p_erdos/1983-11.pdf">On a Problem of Oppenheim concerning "Factorisatio Numerorum"</a>, J. Number Theory 17 (1983), 1-28. [A second link to the same paper.]

%H Marc Chamberland, Colin Johnson, Alice Nadeau, and Bingxi Wu, <a href="http://www.combinatorics.org/ojs/index.php/eljc/article/view/v20i2p57">Multiplicative Partitions</a>, Electronic Journal of Combinatorics, 20(2) (2013), #P57.

%H S. R. Finch, <a href="/A001055/a001055.pdf">Kalmar's composition constant</a>, Jun 05 2003. [Cached copy, with permission of the author]

%H Shamik Ghosh, <a href="http://arxiv.org/abs/0811.3479">Counting number of factorizations of a natural number</a>, arXiv:0811.3479 [cs.DM], 2008.

%H R. K. Guy and R. J. Nowakowski, <a href="http://www.jstor.org/stable/2975272">Monthly unsolved problems</a>, 1969-1995, Amer. Math. Monthly, 102 (1995), 921-926.

%H Florian Luca, Anirban Mukhopadhyay and Kotyada Srinivas, <a href="http://arxiv.org/abs/0807.0986">On the Oppenheim's "factorisatio numerorum" function</a>, arXiv:0807.0986 [math.NT], 2008.

%H Amarnath Murthy, <a href="http://www.gallup.unm.edu/~smarandache/murthy11.htm">Generalization of Partition Function (Introducing the Smarandache Factor Partition)</a> [Broken link]

%H Amarnath Murthy and Charles Ashbacher, <a href="http://fs.unm.edu/MurthyBook.pdf">Generalized Partitions and Some New Ideas on Number Theory and Smarandache Sequences</a>, Hexis, Phoenix; USA 2005. See Section 1.4.

%H Paul Pollack, <a href="http://dx.doi.org/10.1090/S0002-9939-2012-11254-7">On the parity of the number of multiplicative partitions and related problems</a>, Proc. Amer. Math. Soc. 140 (2012), 3793-3803.

%H Marko Riedel, <a href="http://math.stackexchange.com/questions/629406/how-can-we-compute-the-multiplicative-partition-function">Calculating the multiplicative partition function in Maple with the Polya Enumeration Theorem.</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/UnorderedFactorization.html">Unordered Factorization</a>

%H Wikipedia, <a href="http://en.wikipedia.org/wiki/Multiplicative_partition">Multiplicative Partition Function</a>

%H <a href="/index/Cor#core">Index entries for "core" sequences</a>

%F The asymptotic behavior of this sequence was studied by Canfield, Erdős & Pomerance and Luca, Mukhopadhyay, & Srinivas. - _Jonathan Vos Post_, Jul 07 2008

%F Dirichlet g.f.: Product_{k>=2} 1/(1 - 1/k^s).

%F If n = p^k for a prime p, a(n) = partitions(k) = A000041(k).

%F 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)

%F a(A002110(n)) = A000110(n).

%e 1: 1, a(1) = 1

%e 2: 2, a(2) = 1

%e 3: 3, a(3) = 1

%e 4: 4 = 2*2, a(4) = 2

%e 6: 6 = 2*3, a(6) = 2

%e 8: 8 = 2*4 = 2*2*2, a(8) = 3

%e etc.

%p with(numtheory):

%p T := proc(n::integer, m::integer)

%p local A, summe, d:

%p if isprime(n) then

%p if n <= m then

%p return 1;

%p end if:

%p return 0 ;

%p end if:

%p A := divisors(n) minus {n, 1}:

%p for d in A do

%p if d > m then

%p A := A minus {d}:

%p end if:

%p end do:

%p summe := add(T(n/d,d),d=A) ;

%p if n <=m then

%p summe := summe + 1:

%p end if:

%p summe ;

%p end proc:

%p A001055 := n -> T(n, n):

%p [seq(A001055(n), n=1..100)]; # _Reinhard Zumkeller_ and Ulrich Schimke (ulrschimke(AT)aol.com)

%t 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 *)

%o (PARI) /* factorizations of n with factors <= m (n,m positive integers) */

%o 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}

%o A001055(n) = fcnt(n,n) \\ _Michael B. Porter_, Oct 29 2009

%o (Haskell)

%o a001055 = (map last a066032_tabl !!) . (subtract 1)

%o -- _Reinhard Zumkeller_, Oct 01 2012

%o (PARI code using Dirichlet g.f., based on Somos's code for A007896, from _N. J. A. Sloane_, May 26 2014)

%o {a(n) = my(A, v, w, m);

%o if(

%o n<1, 0,

%o \\ define unit vector v = [1, 0, 0, ...] of length n

%o v = vector(n, k, k==1);

%o for(k=2, n,

%o m = #digits(n, k) - 1;

%o \\ expand 1/(1-x)^k out far enough

%o A = (1 - x)^ -1 + x * O(x^m);

%o \\ w = zero vector of length n

%o w = vector(n);

%o \\ convert A to a vector

%o for(i=0, m, w[k^i] = polcoeff(A, i));

%o \\ build the answer

%o v = dirmul(v, w)

%o );

%o v[n]

%o )

%o };

%o \\ produce the sequence

%o vector(100,n,a(n))

%o (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

%o (Python)

%o from sympy import divisors, isprime

%o def T(n, m):

%o if isprime(n): return 1 if n<=m else 0

%o A=filter(lambda d: d<=m, divisors(n)[1:-1])

%o s=sum([T(n/d, d) for d in A])

%o return s + 1 if n<=m else s

%o def a(n): return T(n, n)

%o print map(a, xrange(1, 106)) # _Indranil Ghosh_, Aug 19 2017

%Y A045782 gives the range of a(n).

%Y For records see A033833, A033834.

%Y Cf. A002033, A045778, A050322, A050336, A064553, A064554, A064555, A077565, A051731, A005171, A097296, A190938, A216599, A216600, A216601, A216602.

%K nonn,easy,nice,core

%O 1,4

%A _N. J. A. Sloane_

%E Incorrect assertion about asymptotic behavior deleted by _N. J. A. Sloane_, Jun 08 2009

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 22 12:46 EDT 2019. Contains 321421 sequences. (Running on oeis4.)