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.

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

Links

Table of n, a(n) for n=0..51.

Formula

a(n) = 1 + n + A060831(1) + A060831(2) + ... + A060831(n-1).

Crossrefs

Cf. A001227.

Sequence in context: A267529 A005521 A135901 * A011909 A065962 A173722

Adjacent sequences: A124194 A124195 A124196 * A124198 A124199 A124200

Keyword

nonn

Author

John W. Layman, Dec 06 2006

Extensions

Edited and extended by Max Alekseyev, Jan 20 2010

Status

approved