|
%I M0095 N0032 #163 May 11 2023 12:22:12
%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 prime signatures 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).
%D 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).
%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="https://doi.org/10.1016/0022-314X(83)90002-1">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 John F. Hughes and J. O. Shallit, <a href="https://www.jstor.org/stable/2975729">On the Number of Multiplicative Partitions</a>, American Mathematical Monthly 90(7) (1983), 468-471.
%H Cao Hui-Zhong and Ku Tung-Hsin, <a href="http://www.math.bas.bg/infres/MathBalk/MB-04/MB-04-325-328.pdf">On the Enumeration Function of Multiplicative Partitions</a>, Math. Balkanica, Vol. 4 (1990), Fasc. 3-4.
%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 Pankaj Jyoti Mahanta, <a href="https://arxiv.org/abs/2010.07353">On the number of partitions of n whose product of the summands is at most n</a>, arXiv:2010.07353 [math.CO], 2020.
%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 *)
%t T[_, 1] = T[1, _] = 1;
%t T[n_, m_] := T[n, m] = DivisorSum[n, Boole[1 < # <= m] * T[n/#, #]&];
%t a[n_] := T[n, n];
%t a /@ Range[100] (* _Jean-François Alcover_, Jan 03 2020 *)
%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 (PARI) \\ code using Dirichlet g.f., based on Somos's code for A007896
%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)) \\ _N. J. A. Sloane_, May 26 2014
%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 (Haskell)
%o a001055 = (map last a066032_tabl !!) . (subtract 1)
%o -- _Reinhard Zumkeller_, Oct 01 2012
%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([a(n) for n in range(1, 106)]) # _Indranil Ghosh_, Aug 19 2017
%o (Java)
%o public class MultiPart {
%o public static void main(String[] argV) {
%o for (int i=1;i<=100;++i) System.out.println(1+getDivisors(2,i));
%o }
%o public static int getDivisors(int min,int n) {
%o int total = 0;
%o for (int i=min;i<n;++i)
%o if (n%i==0 && n/i>=i) { ++total; if (n/i>i) total+=getDivisors(i,n/i); }
%o return total;
%o }
%o } \\ _Scott R. Shannon_, Aug 21 2019
%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.
%Y Row sums of A316439 (for n>1).
%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
|
