|
| |
|
|
A124197
|
|
Number of subsets S of {1,2,3,...,n}, including the empty subset, such that if x and y are in S with x<y and x+y even, then (x+y)/2 is also in S.
|
|
0
| |
|
|
1, 2, 4, 7, 12, 18, 26, 36, 48, 61, 77, 95, 115, 137, 161, 187, 217, 248, 281, 317, 355, 395, 439, 485, 533, 583, 636, 691, 750, 811, 874, 941, 1010, 1080, 1154, 1230, 1310, 1393, 1478, 1565, 1656, 1749, 1844, 1943, 2044, 2147, 2256, 2367, 2480, 2595, 2713, 2834
(list; graph; refs; listen; history; internal format)
|
|
|
|
OFFSET
| 0,2
|
|
|
COMMENTS
| The second differences of this sequence give A001227, the number of odd divisors of n.
The sequence appeared in Problem B3 on the 2009 Putnam exam, which asked one to find all n for which the second difference equals 1. The second difference is the number of such subsets of {1,2,...,n+1} that contain both 1 and n+1. One such subset is {1,2,...,n+1}, and if n has an odd factor d>1 then the arithmetic progression {1,d+1,2d+1,...,n+1} works as well; hence the second difference is 1 iff n is a power of 2. [NB the Putnam problem uses n+1 for our n.] This also means that the conjectural formula for the second difference is a lower bound. To prove the conjecture, note that consecutive elements of S alternate in parity (else S contains their average); thus if x,s,y are consecutive elements then x+y is even, so s=(x+y)/2, which means that S is a finite arithmetic progression with odd common difference. Since conversely any such arithmetic progression works, we are done. [From Noam D. Elkies (elkies(AT)math.harvard.edu), Dec 05 2009]
|
|
|
FORMULA
| a(n) = 1 + n + A060831(1) + A060831(2) + ... + A060831(n-1)
|
|
|
CROSSREFS
| Cf. A001227.
Sequence in context: A011910 A005521 A135901 * A011909 A065962 A173722
Adjacent sequences: A124194 A124195 A124196 * A124198 A124199 A124200
|
|
|
KEYWORD
| nonn
|
|
|
AUTHOR
| John W. Layman (layman(AT)math.vt.edu), Dec 06 2006
|
|
|
EXTENSIONS
| Edited and extended by Max Alekseyev (maxale(AT)gmail.com), Jan 20 2010
|
| |
|
|
