login
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
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. [Note that 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. - Noam D. Elkies, Dec 05 2009
FORMULA
a(n) = 1 + n + A060831(1) + A060831(2) + ... + A060831(n-1).
CROSSREFS
Cf. A001227.
Sequence in context: A267529 A005521 A135901 * A011909 A065962 A173722
KEYWORD
nonn
AUTHOR
John W. Layman, Dec 06 2006
EXTENSIONS
Edited and extended by Max Alekseyev, Jan 20 2010
STATUS
approved