A316353 Number of partitions of positive integer n such that all parts are less than the square root of n.

0, 1, 1, 1, 3, 4, 4, 5, 5, 14, 16, 19, 21, 24, 27, 30, 72, 84, 94, 108, 120, 136, 150, 169, 185, 427, 480, 540, 603, 674, 748, 831, 918, 1014, 1115, 1226, 2702, 3009, 3331, 3692, 4070, 4494, 4935, 5427, 5942, 6510, 7104, 7760, 8442, 18138, 19928, 21873, 23961, 26226, 28652

Offset: 1

Author

Richard Locke Peterson, Jun 29 2018

Keywords

• nonn

Comments

This sequence itself is not a semigroup, but the set of all the partitions enumerated by this sequence does form a semigroup (actually a subsemigroup of the set of all partitions) with the following binary operation: let alpha = the partition (a,b,c,... [this is of course a finite list]) be the partition of the number N1 [that is, a + b + c + ... = N1] and let ALPHA = (A,B,C,...) be the partition of N2. Then the binary operation given by alpha*ALPHA = (a,b,c,...)*(A,B,C,...) = (aA,aB,aC,...,bA,bB,bC,...,cA,cB,cC,...) is a partition of the integer N1*N2. Furthermore, since any part x of alpha is less than the square root of N1, and likewise for any part Y of ALPHA, then the part xY is less than the square root of N1*N2, so the set is a subsemigroup of the semigroup of all partitions under the given operation. If the sole partition (1) of 1 is adjoined, the semigroup becomes a monoid.

Examples

			a(3)=1, since the partition (1,1,1) is the only partition of 3 with all parts less than the square root of 3 ~ 1.73.
a(6)=4, since there are only 4 allowable partitions: (1,1,1,1,1,1,1), (1,1,1,1,2), (1,1,2,2), and (2,2,2).
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 1..20000 (first 123 terms from Robert G. Wilson v)

Crossrefs

Cf. A000041 (the partition numbers), A097356 (with 'no greater' rather than less).

Programs

Maple

b:= proc(n, i) option remember; `if`(n=0, 1,
      `if`(i<1, 0, b(n, i-1)+b(n-i, min(n-i, i))))
    end:
a:= n-> b(n, (r-> `if`(r*r>=n, r-1, r))(isqrt(n))):
seq(a(n), n=1..100);  # Alois P. Heinz, Aug 02 2018

Mathematica

Table[With[{s = Sqrt@ n}, Count[IntegerPartitions[n], ?(AllTrue[#, # < s &] &)]], {n, 53}] (* _Michael De Vlieger, Jul 22 2018 *)
f[n_] := Length@ IntegerPartitions[n, All, Range@ Sqrt[n - 1]]; Array[f, 50] (* Robert G. Wilson v, Jul 24 2018 *)
b[n_, i_] := b[n, i] = If[n == 0, 1, If[i < 1, 0, b[n, i - 1] + b[n - i, Min[n - i, i]]]];
a[n_] := b[n, Function[r, If[r*r >= n, r - 1, r]][Floor[Sqrt[n]]]];
Array[a, 100] (* Jean-François Alcover, May 30 2021, after Alois P. Heinz *)

PARI

a(n) = my(nb = 0); forpart(p=n, nb++, sqrtint(n)-issquare(n)); nb; \\ Michel Marcus, Jul 15 2018

Formula

log(a(n)) ~ log(A258268) * sqrt(n) - log(n). - Vaclav Kotesovec, May 30 2021

Extensions

More terms from Michel Marcus, Jul 15 2018