A174094 Number of ways to choose n positive integers less than or equal to 2n such that none of the n integers divides another.

1, 2, 2, 3, 5, 4, 6, 12, 10, 14, 26, 26, 34, 68, 48, 72, 120, 120, 168, 336, 264, 396, 792, 624, 816, 1632, 1632, 2208, 3616, 3616, 5056, 10112, 6592, 9888, 19776, 19776, 24384, 48768, 48768, 73152, 112320, 76032, 114048, 228096, 190080, 264960, 529920

Offset: 0

Author

David Brown, Mar 07 2010

Keywords

• nonn

Comments

a(n) >= 2^(1+floor((n-1)/3)). - Robert Israel, Aug 25 2015

Examples

			a(1) = 2 because we can choose {1}, {2}.
a(2) = 2 because we can choose {2, 3}, {3, 4}.
a(3) = 3 because we can choose {2, 3, 5}, {3, 4, 5}, {4, 5, 6}.
		

References

• F. Caldarola, G. d'Atri, M.Pellegrini, Combinatorics on n-sets: Arithmetic properties and numerical results. In: Sergeyev Y., Kvasov D. (eds) Numerical Computations: Theory and Algorithms. NUMTA 2019. Lecture Notes in Computer Science, vol. 11973. Springer, Cham, 389-401.

Links

• Bertram Felgenhauer, Table of n, a(n) for n = 0..3400 (terms 1..100 from Marco Pellegrini)
• C. Bindi, L. Bussoli, M. Grazzini, M. Pellegrini, G. Pirillo, M. A. Pirillo, and A. Troise, Su un risultato di uno studente di Erdös, Periodico di matematiche 1 (2016), Vol 8, No 1 (2016): Serie XII Anno CXXVI. [Broken link]
• Bertram Felgenhauer, Haskell program for computing A174094.
• Hong Liu, Péter Pál Pach, and Richárd Palincza, The number of maximum primitive sets of integers, arXiv:1805.06341 [math.CO], 2018.
• Richárd Palincza, Counting type and extremal problems from Arithmetic Combinatorics, Ph. D. Thesis, Budapest Univ. Tech. Econ. (Hungary, 2024).
• Sujith Vijay, On large primitive subsets of {1,2,...,2n}, arXiv:1804.01740 [math.CO], 2018.

Crossrefs

The smallest n integers possible is A174063.

Programs

Maple

F:= proc(S,m)
  option remember;
  local s,S1,S2;
  if nops(S) < m then return 0 fi;
  if m = 1 then return nops(S) fi;
  s:= min(S);
  S1:= S minus {s};
  S2:= S minus {seq(j*s,j=1..floor(max(S)/s))};
  F(S1, m) + F(S2, m-1);
end proc;
seq(F({$1..2*n},n), n=1..37); # Robert Israel, Aug 25 2015

Mathematica

F[S_List, m_] := F[S, m] = Module[{s, S1, S2}, If[Length[S]Jean-François Alcover, Jul 10 2018, after Robert Israel *)

Extensions

More terms from David Brown, Mar 14 2010

a(30)-a(46) from Ray Chandler, Mar 19 2010

a(0)=1 prepended by Alois P. Heinz, Jun 24 2022