|
|
A188793
|
|
Start with 1 and 5, then repeatedly adjoin the smallest number that is greater than the last term and not equal to the sum of a subset of the existing terms.
|
|
0
|
|
|
1, 5, 7, 9, 11, 29, 31, 89, 91, 269, 271, 809, 811, 2429, 2431, 7289, 7291, 21869, 21871, 65609, 65611, 196829, 196831, 590489, 590491, 1771469, 1771471, 5314409, 5314411, 15943229, 15943231, 47829689, 47829691, 143489069, 143489071, 430467209, 430467211
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,2
|
|
COMMENTS
|
All terms after a(3) are of the form 10*3^k +/- 1.
The fact that, after a(3), a term is in this sequence if and only if it is of the form 10*3^k +/- 1 can be proved by induction:
Suppose the sequence contains subsets that sum to every number from 5 to 10*3^k + 3, excluding 10*3^k - 1, 10*3^k, and 10*3^k + 1 (this is easily verified in the k = 0 case with the sequence 1, 5, 7). Then 10*3^k - 1 is added to the sequence, 10*3^k is not added to the sequence (because 10*3^k - 1 + 1 = 10*3^k), and 10*3^k + 1 is added to the sequence (because 2 is not a sum of a subset of terms).
After these two new terms have been added to the sequence, there are subset sums for:
(1) any number from 5 to 10*3^k + 3 (by inductive hypothesis),
(2) any number from (10*3^k - 1) + 5 = 10*3^k + 4 to (10*3^k - 1) + 10*3^k + 3 = 20*3^k + 2 (excluding 20*3^k - 2, 20*3^k - 1, and 20*3^k, because we added 10*3^k - 1 to the sequence),
(3) any number from (10*3^k + 1) + 5 = 10*3^k + 6 to (10*3^k + 1) + 10*3^k + 3 = 20*3^k + 4 (excluding 20*3^k, 20*3^k + 1, and 20*3^k + 2, because we added 10*3^k + 1 to the sequence),
(4) 20*3^k ( = (10*3^k - 1) + (10*3^k + 1)), and
(5) any number from 5 + (10*3^k - 1) + (10*3^k + 1) = 20*3^k + 5 to (10*3^k + 3) + (10*3^k - 1) + (10*3^k + 1) = 30*3^k + 3 = 10*3^(k+1) + 3, excluding 10*3^(k+1) - 1, 10*3^(k+1), and 10*3^(k+1) + 1.
It follows that the sequence now contains subsets that sum to every number from 5 to 10*3^(k+1) + 3, excluding 10*3^(k+1) - 1, 10*3^(k+1), and 10*3^(k+1) + 1, which completes the induction. (End)
|
|
REFERENCES
|
|
|
LINKS
|
|
|
FORMULA
|
a(2h) = 10*3^(h-2) - 1 for h >= 2.
a(2h+1) = 10*3^(h-2) + 1 for h >= 2. (End)
G.f.: x*(1 + 6*x + 9*x^2 - 2*x^3 - 16*x^4 - 8*x^5)/((1 + x)*(1 - 3*x^2)). - Bruno Berselli, Sep 03 2016
|
|
EXAMPLE
|
6 = 1+5, but 7 isn't there. 8 = 7+1, but 9 isn't there,
10 = 9+1, but 11 isn't there. 12 = 7+5, 13 = 7+5+1,
14 = 9+5, 15 = 9+5+1, 16 = 9+7, 17 = 9+7+1, 18 = 11+7, ...
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,easy
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|