|
%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
|
