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

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

Author

John W. Layman, Dec 06 2006

Keywords

• nonn

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

Crossrefs

Cf. A001227.

Formula

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

Extensions

Edited and extended by Max Alekseyev, Jan 20 2010