OFFSET
0,4
COMMENTS
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.
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
LINKS
Robert Israel, Table of n, a(n) for n = 0..250
Mathematics StackExchange, Largest subset with no pair summing to power of two.
FORMULA
a(2^k) = 2^(k-1) for k >= 1.
a(n) <= A110654(n) for n >= 1.
From Sarosh Adenwalla, Feb 16 2023: (Start)
(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.
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.
For every integer c >= -1, there are infinitely many n such that a(n) = (n-c)/2.
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)
EXAMPLE
a(7) = 4 with a suitable subset being {0, 3, 6, 7}.
MAPLE
f:= proc(n) uses GraphTheory; local G, V, E, i, d;
V:= {$0..n} minus {seq(2^i, i=0..ilog2(n))};
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))});
G:= Graph(convert(V, list), E);
IndependenceNumber(G);
end proc:
map(f, [$0..80]);
CROSSREFS
KEYWORD
nonn
AUTHOR
Robert Israel, Jan 04 2023
STATUS
approved