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

0, 2, 4, 8, 14, 26, 40, 58, 84, 114, 148, 194, 242, 306, 370, 454, 532, 624, 736, 848, 986, 1120, 1274, 1438, 1618, 1800, 1994, 2220, 2446, 2700, 2950, 3222, 3526, 3830, 4142, 4516, 4832, 5214, 5590, 6020, 6440, 6860, 7356, 7830, 8336, 8816, 9420, 9934, 10532, 11118, 11740, 12396, 13022, 13702

Offset

0,2

Comments

All terms are even.

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

Links

David A. Corneth, Table of n, a(n) for n = 0..10000 (first 501 terms from Robert Israel)

Example

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.

Maple

P:= proc(n, p) option remember;
  if n=1 and p>1 then return 0 fi;
  if p mod n = 0 then procname(n-1, p) + procname(n-1, p/n)
  else procname(n-1, p)
  fi
end proc:
P(1, 1):= 2:
P(0, 0):= 0:
[seq(add(P(n, p), p=1..n^2+n), n=0..100)]; # Robert Israel, Mar 06 2018

Mathematica

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;
a[n_] := Sum[P[n, p], {p, 1, n^2 + n}];
a /@ Range[0, 100] (* Jean-François Alcover, Oct 26 2020, after Robert Israel *)

Prog

(SageMath) [len([S for S in Subsets( n) if mul(S)<=n^2+n]) for n in range(15)]
(PARI)
first(n) = {
	n--;
	maxn = n;
	u = n^2 + n;
	res = vector(n);
	process(1, 1);
	for(i = 2, #res,
		res[i]+=res[i-1]
	);
	return(concat(0, 2*res))
}
process(p, n) = {
	my(i, s);
	s = (sqrtint(4*p+1)>>1);
	while(s*(s+1) < p,
		s++
	);
	res[max(n, s)]++;
	for(i = n+1, min(maxn, u \ p),
		process(p*i, i)
	); 	
} \\ David A. Corneth, Apr 05 2024

Crossrefs

Sequence in context: A164149 A164148 A065492 * A208483 A284735 A006777

Adjacent sequences: A298877 A298878 A298879 * A298881 A298882 A298883

Keyword

nonn

Author

Adrienne Crookshank, Feb 27 2018

Extensions

More terms from Robert Israel, Mar 06 2018

Status

approved