A096276 Number of partitions of n with a product <=n.
0, 1, 2, 3, 5, 6, 8, 9, 12, 14, 16, 17, 21, 22, 24, 26, 31, 32, 36, 37, 41, 43, 45, 46, 53, 55, 57, 60, 64, 65, 70, 71, 78, 80, 82, 84, 93, 94, 96, 98, 105, 106, 111, 112, 116, 120, 122, 123, 135, 137, 141, 143, 147, 148, 155, 157, 164, 166, 168, 169, 180, 181, 183, 187
Offset: 0
Keywords
Examples
a(6)=8 as we can have 6, 51, 411, 321, 3111, 2211, 21111, 111111, rejecting 42, 33 and 222.
From _Gus Wiseman_, Mar 27 2019: (Start)
The a(1) = 1 through a(8) = 12 partitions:
(1) (2) (3) (4) (5) (6) (7) (8)
(11) (21) (22) (41) (51) (61) (71)
(111) (31) (221) (321) (511) (611)
(211) (311) (411) (3211) (4211)
(1111) (2111) (2211) (4111) (5111)
(11111) (3111) (22111) (22211)
(21111) (31111) (32111)
(111111) (211111) (41111)
(1111111) (221111)
(311111)
(2111111)
(11111111)
(End)
References
- 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
- Alois P. Heinz, Table of n, a(n) for n = 0..10000 (first 1001 terms from T. D. Noe)
- R. E. Canfield, P. Erdős and C. Pomerance, On a Problem of Oppenheim concerning "Factorisatio Numerorum", J. Number Theory 17 (1983), 1-28.
- 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.
- A. Oppenheim, On an Arithmetic Function, Journal of the London Mathematical Society, 1926, 10, Vol. s1-1, Iss. 4, 205-211.
- A. Oppenheim, On an Arithmetic Function (II), Journal of the London Mathematical Society, 1927, 04, Vol. s1-2, Iss. 2, 123-130.
- Csaba Sándor and Maciej Zakarczemny, Equal Sum and Product Problem III, arXiv:2405.11600 [math.NT], 2024.
Programs
-
Maple
g:= proc(n, k) option remember; `if`(n>k, 0, 1)+ `if`(isprime(n), 0, add(`if`(d>k, 0, g(n/d, d)), d=numtheory[divisors](n) minus {1, n})) end: a:= proc(n) option remember; `if`(n=0, 0, a(n-1)+g(n$2)) end: seq(a(n), n=0..100); # Alois P. Heinz, Feb 26 2023 -
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]; Join[{0}, Accumulate[Array[a, 100]]] (* using program from A001055, T. D. Noe, Apr 11 2011 *) Table[Length[Select[IntegerPartitions[n],Times@@#<=n&]],{n,0,20}] (* Gus Wiseman, Mar 27 2019 *) -
PARI
{ bla(n,m,v,z)=v=concat(v,m); if(!n,x=prod(k=1,length(v),v[k]); if (x<=z,c++), for(i=1,min(m,n),bla(n-i,i,v,z))); } q(n)=c=0;for(i=1,n,bla(n-i,i,[],n));print1(c, ", "); for(i=0,40,q(i))
Formula
For n>1, a(n) = a(n-1)+1 iff n is prime.
Partial sums of A001055. - Vladeta Jovovic, Jun 24 2004
a(n) ~ n * exp(2*sqrt(log(n))) / (2*sqrt(Pi) * (log(n))^(3/4)) [Oppenheim, 1927]. - Vaclav Kotesovec, May 23 2020
Extensions
More terms from Vladeta Jovovic, Jun 24 2004
Comments