cp's OEIS Frontend

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

%I A316353 #50 May 30 2021 07:49:48
%S A316353 0,1,1,1,3,4,4,5,5,14,16,19,21,24,27,30,72,84,94,108,120,136,150,169,
%T A316353 185,427,480,540,603,674,748,831,918,1014,1115,1226,2702,3009,3331,
%U A316353 3692,4070,4494,4935,5427,5942,6510,7104,7760,8442,18138,19928,21873,23961,26226,28652
%N A316353 Number of partitions of positive integer n such that all parts are less than the square root of n.
%C A316353 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.
%H A316353 Alois P. Heinz, <a href="/A316353/b316353.txt">Table of n, a(n) for n = 1..20000</a> (first 123 terms from Robert G. Wilson v)
%F A316353 log(a(n)) ~ log(A258268) * sqrt(n) - log(n). - _Vaclav Kotesovec_, May 30 2021
%e A316353 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.
%e A316353 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).
%p A316353 b:= proc(n, i) option remember; `if`(n=0, 1,
%p A316353       `if`(i<1, 0, b(n, i-1)+b(n-i, min(n-i, i))))
%p A316353     end:
%p A316353 a:= n-> b(n, (r-> `if`(r*r>=n, r-1, r))(isqrt(n))):
%p A316353 seq(a(n), n=1..100);  # _Alois P. Heinz_, Aug 02 2018
%t A316353 Table[With[{s = Sqrt@ n}, Count[IntegerPartitions[n], _?(AllTrue[#, # < s &] &)]], {n, 53}] (* _Michael De Vlieger_, Jul 22 2018 *)
%t A316353 f[n_] := Length@ IntegerPartitions[n, All, Range@ Sqrt[n - 1]]; Array[f, 50] (* _Robert G. Wilson v_, Jul 24 2018 *)
%t A316353 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]]]];
%t A316353 a[n_] := b[n, Function[r, If[r*r >= n, r - 1, r]][Floor[Sqrt[n]]]];
%t A316353 Array[a, 100] (* _Jean-François Alcover_, May 30 2021, after _Alois P. Heinz_ *)
%o A316353 (PARI) a(n) = my(nb = 0); forpart(p=n, nb++, sqrtint(n)-issquare(n)); nb; \\ _Michel Marcus_, Jul 15 2018
%Y A316353 Cf. A000041 (the partition numbers), A097356 (with 'no greater' rather than less).
%K A316353 nonn
%O A316353 1,5
%A A316353 _Richard Locke Peterson_, Jun 29 2018
%E A316353 More terms from _Michel Marcus_, Jul 15 2018