cp's OEIS Frontend

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 and x+y even, then (x+y)/2 is also in S.

%I A124197 #9 Feb 24 2018 02:56:24
%S A124197 1,2,4,7,12,18,26,36,48,61,77,95,115,137,161,187,217,248,281,317,355,
%T A124197 395,439,485,533,583,636,691,750,811,874,941,1010,1080,1154,1230,1310,
%U A124197 1393,1478,1565,1656,1749,1844,1943,2044,2147,2256,2367,2480,2595,2713,2834
%N 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.
%C A124197 The second differences of this sequence give A001227, the number of odd divisors of n.
%C A124197 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
%F A124197 a(n) = 1 + n + A060831(1) + A060831(2) + ... + A060831(n-1).
%Y A124197 Cf. A001227.
%K A124197 nonn
%O A124197 0,2
%A A124197 _John W. Layman_, Dec 06 2006
%E A124197 Edited and extended by _Max Alekseyev_, Jan 20 2010