login
a(n) is the number of subsets of {1, 2, ..., n} with product of all entries <= n^2 + n.
1

%I #44 Apr 05 2024 08:16:36

%S 0,2,4,8,14,26,40,58,84,114,148,194,242,306,370,454,532,624,736,848,

%T 986,1120,1274,1438,1618,1800,1994,2220,2446,2700,2950,3222,3526,3830,

%U 4142,4516,4832,5214,5590,6020,6440,6860,7356,7830,8336,8816,9420,9934,10532,11118,11740,12396,13022,13702

%N a(n) is the number of subsets of {1, 2, ..., n} with product of all entries <= n^2 + n.

%C All terms are even.

%C The subsets that are counted for a(n) are also counted for a(n+1) the use of which eases the computation of the first terms as double counting can be avoided. - _David A. Corneth_, Apr 05 2024

%H David A. Corneth, <a href="/A298880/b298880.txt">Table of n, a(n) for n = 0..10000</a> (first 501 terms from Robert Israel)

%e The first nontrivial case is when n = 4 and a(4) = 14. There are 2^4 = 16 subsets of {1, 2, 3, 4}. The subsets {2, 3, 4} and {1, 2, 3, 4} do not meet the condition that the product of the entries are less than or equal to n^2 + n = (4^4 + 4 = 20. There are 14 subsets of {1, 2, 3, 4} whose entries have a product less than 20.

%p P:= proc(n,p) option remember;

%p if n=1 and p>1 then return 0 fi;

%p if p mod n = 0 then procname(n-1,p) + procname(n-1,p/n)

%p else procname(n-1,p)

%p fi

%p end proc:

%p P(1,1):= 2:

%p P(0,0):= 0:

%p [seq(add(P(n,p),p=1..n^2+n),n=0..100)]; # _Robert Israel_, Mar 06 2018

%t P[n_, p_] := P[n, p] = If[n == 1 && p > 1, 0, If[Mod[p, n] == 0, P[n-1, p] + P[n-1, p/n], P[n-1, p]]]; P[1, 1] = 2; P[0, 0] = 0;

%t a[n_] := Sum[P[n, p], {p, 1, n^2 + n}];

%t a /@ Range[0, 100] (* _Jean-François Alcover_, Oct 26 2020, after _Robert Israel_ *)

%o (SageMath) [len([S for S in Subsets( n) if mul(S)<=n^2+n]) for n in range(15)]

%o (PARI)

%o first(n) = {

%o n--;

%o maxn = n;

%o u = n^2 + n;

%o res = vector(n);

%o process(1, 1);

%o for(i = 2, #res,

%o res[i]+=res[i-1]

%o );

%o return(concat(0, 2*res))

%o }

%o process(p, n) = {

%o my(i, s);

%o s = (sqrtint(4*p+1)>>1);

%o while(s*(s+1) < p,

%o s++

%o );

%o res[max(n, s)]++;

%o for(i = n+1, min(maxn, u \ p),

%o process(p*i, i)

%o );

%o } \\ _David A. Corneth_, Apr 05 2024

%K nonn

%O 0,2

%A _Adrienne Crookshank_, Feb 27 2018

%E More terms from _Robert Israel_, Mar 06 2018