A359536 - OEIS

%I #28 Mar 04 2023 15:22:58

%S 1,1,1,2,2,2,3,4,4,4,4,5,6,6,7,8,8,8,8,9,9,9,10,11,12,12,12,13,14,14,

%T 15,16,16,16,16,17,17,17,18,19,19,19,19,20,21,21,22,23,24,24,24,25,25,

%U 25,26,27,28,28,28,29,30,30,31,32,32,32,32,33,33,33,34,35,35,35,35,36,37,37,38,39,39

%N a(n) is the size of the largest subset of {0,1,...,n} such that the sum of two (not necessarily distinct) elements is never a power of 2.

%C a(n) is the independence number of the graph with vertices all members of {0,1,...,n} that are not powers of 2, and edges (i,j) when i+j is a power of 2.

%C The greedy algorithm for constructing a set A with these properties (starting with 0 and then adding an integer to A iff it is not a power of 2 and does not sum to a power of 2 with a smaller integer already in A, i.e., {0,3,6,7,11,12,14,...}) is maximal in that |A intersect [0,n]| = a(n). It follows that t is in A iff a(t-1) < a(t). There are no 4 consecutive integers in A and no 4 consecutive integers not in A. - _Sarosh Adenwalla_, Feb 16 2023

%H Robert Israel, <a href="/A359536/b359536.txt">Table of n, a(n) for n = 0..250</a>

%H Mathematics StackExchange, <a href="https://math.stackexchange.com/questions/1016014/largest-subset-with-no-pair-summing-to-power-of-two/1016099#4611729">Largest subset with no pair summing to power of two</a>.

%F a(2^k) = 2^(k-1) for k >= 1.

%F a(n) <= A110654(n) for n >= 1.

%F From _Sarosh Adenwalla_, Feb 16 2023: (Start)

%F (n + 1 - floor(log_2(n)))/2 <= a(n) <= A110654(n) for n >= 1. The upper bound is achieved iff n > 0 can be written as the difference of two powers of 2 and the lower bound is achieved iff n = floor(2^s/3) for s >= 2.

%F Letting r = 2^(floor(log_2(n))+1) - n then a(n) = (n-r)/2 + a(r-1). a(n) can be calculated by repeatedly applying this at most floor(log_2(n)) times.

%F For every integer c >= -1, there are infinitely many n such that a(n) = (n-c)/2.

%F For 0 <= c < 2^(k-1), a(2^k+c) = 2^(k-1) - 1 + a(c) and for 0 < c <= 2^(k-1), a(2^k-c) = 2^(k-1) - c + a(c-1). (End)

%e a(7) = 4 with a suitable subset being {0, 3, 6, 7}.

%p f:= proc(n) uses GraphTheory; local G,V,E,i,d;

%p   V:= {$0..n} minus {seq(2^i,i=0..ilog2(n))};

%p   E:= select(s -> s subset V, {seq(seq({i,2^d-i},i=max(0,2^d-n) .. min(2^(d-1),n)),d=1..1+ilog2(n))});

%p   G:= Graph(convert(V,list),E);

%p   IndependenceNumber(G);

%p end proc:

%p map(f, [$0..80]);

%Y Cf. A110654.

%K nonn

%O 0,4

%A _Robert Israel_, Jan 04 2023