|
| |
|
|
A359536
|
|
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.
|
|
1
|
|
|
|
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, 15, 16, 16, 16, 16, 17, 17, 17, 18, 19, 19, 19, 19, 20, 21, 21, 22, 23, 24, 24, 24, 25, 25, 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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
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
|
|
|
|
FORMULA
|
a(2^k) = 2^(k-1) for k >= 1.
(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
|
|
|
|
STATUS
|
approved
|
| |
|
|
