A131754 Size of the largest subset of {1,2,...,n} such that no two distinct elements differ by a perfect square > 1.

1, 2, 3, 4, 4, 4, 4, 4, 5, 5, 6, 6, 6, 7, 8, 8, 8, 8, 8, 8, 9, 10, 10, 10, 10, 10, 10, 11, 11, 11, 11, 11, 11, 11, 12, 13, 13, 13, 13, 13, 14, 15, 15, 15, 15, 15, 15, 16, 17, 17, 17, 17, 17, 17, 18, 19, 19, 19, 19, 19, 19, 20, 20, 20, 20, 20, 20, 21, 21, 21, 21, 21, 21, 21, 22, 23, 24, 24, 24, 24, 24

Offset

1,2

Links

Fausto A. C. Cariboni, Table of n, a(n) for n = 1..270 (terms n = 1..165 from Robert Israel)

Fausto A. C. Cariboni, Sets of maximal span that yield a(n) for n = 2..270, Nov 18 2018.

Maple

f:= proc(n) uses GraphTheory; IndependenceNumber(Graph(n,
   {seq(seq({i, i+x^2}, x=2..floor(sqrt(n-i))), i=1..n)}));
end proc:
map(f, [$1..58]); # Robert Israel, Mar 20 2017

Prog

(MATLAB with CPLEX)
function [v, X] = A131754(n)
A = sparse(0, n);
rownum = 0;
for i =1:n
  for x =2:floor(sqrt(n-i))
    rownum = rownum+1;
    A(rownum, [i, i+x^2]) = 1;
  end
end
prob.f = -ones(n, 1);
prob.Aineq = A;
prob.bineq = ones(rownum, 1);
prob.ctype = char(ones(1, n)*'B');
cplex = Cplex(prob);
cplex.DisplayFunc = [];
cplex.solve();
if cplex.Solution.status == 101
  v = -cplex.Solution.objval;
  x = cplex.Solution.x;
  X = find(x > 0.5);
end
end

Crossrefs

Cf. A100719, A131752, A131753.

Sequence in context: A029127 A195851 A369149 * A287422 A120510 A029117

Adjacent sequences: A131751 A131752 A131753 * A131755 A131756 A131757

Keyword

nonn

Author

Olivier Gérard, Sep 17 2007

Extensions

More terms from Robert Israel, Mar 20 2017

Status

approved