cp's OEIS Frontend

A357574 a(n) is the maximum number of pairs that sum to a power of 2 in a set of n consecutive odd numbers.

%I A357574 #43 Mar 10 2023 09:10:58
%S A357574 0,1,2,4,5,7,9,11,13,15,17,19,21,24,26,29,31,34,36,39,41,44,46,49,51,
%T A357574 54,56,59,62,65,68,71,74,77,80,83,86,89,92,95,98,101,104,107,110,113,
%U A357574 116,119,122,125,128,131,134,137,140,143,146,150,153,157,160,164,167
%N A357574 a(n) is the maximum number of pairs that sum to a power of 2 in a set of n consecutive odd numbers.
%C A357574 An optimal set delivering a(n) pairs summing to powers of 2 can be formed by n-A357409(n) first negative odd numbers and A357409(n) first positive odd numbers, that is, by the odd numbers in the interval [-2*(n-A357409(n))+1, 2*A357409(n)-1].
%C A357574 a(n) is in many cases equal to A347301(n) but there are some deviations: a(3) = 2 but A347301(3) = 3, a(29) = 62 but A347301(29) = 61, a(31) = 68 but A347301(32) = 67, a(33) = 74 but A347301(33) = 73, ... . Hence it appears that a(n) may be used as an improved lower bound for A352178(n) in many cases.
%C A357574 Conjecture: a(n+1) - a(n) = k, if n is even then A129868(k-1) < n < A129868(k), if n is odd then A020515(k) <= n < A020515(k+1).
%H A357574 Thomas Scheuerle, <a href="/A357574/a357574.png">a(n+1) - a(n) for n = 1..500</a>
%H A357574 Max A. Alekseyev, <a href="https://arxiv.org/abs/2303.02872">On computing sets of integers with maximum number of pairs summing to powers of 2</a>, arXiv:2303.02872 [math.CO], 2023.
%F A357574 a(n) <= A352178(n).
%F A357574 a(n) >= n-1. This would be the maximum value that could be attained for a set of only positive odd numbers and size n.
%e A357574 a(5) = 5 because A357409(5) = 4, for which the corresponding set {-1, 1, 3, 5, 7} produces 5 powers of 2: 1+3, 1+7, 3+5, 3-1, 5-1.
%o A357574 (MATLAB)
%o A357574 function a = A357574( max_n )
%o A357574     a(1) = 0; q = [];
%o A357574     for n = 1:max_n
%o A357574         c = 0;
%o A357574         for k = 0:n
%o A357574             s = (2*([0:n]-k))+1;
%o A357574             r = countpowtwo(s);
%o A357574             if c < r
%o A357574                 c = r;
%o A357574                 q = s;
%o A357574             end
%o A357574         end
%o A357574         a(n+1) = c;
%o A357574     end
%o A357574 end
%o A357574 function c = countpowtwo(s)
%o A357574     M = repmat(s, [length(s), 1]);
%o A357574     M = M+M';
%o A357574     M(M<=0) = 7;
%o A357574     M = bitand(M, M-1);
%o A357574     M = M + eye(size(M));
%o A357574     c = length(find(M == 0))/2;
%o A357574 end
%Y A357574 Cf. A020515, A129868, A274089, A347301, A352178, A357409.
%K A357574 nonn
%O A357574 1,3
%A A357574 _Thomas Scheuerle_, Oct 04 2022
%E A357574 Edited by _Max Alekseyev_, Mar 09 2023