A357409 a(n) is the maximum number of positive numbers in a set of n consecutive positive or negative odd numbers such that the number of pairs that add to a power of 2 is maximal.

1, 2, 3, 3, 4, 5, 5, 6, 6, 7, 7, 8, 9, 9, 10, 10, 11, 11, 12, 12, 13, 13, 14, 14, 15, 15, 17, 18, 18, 19, 19, 20, 20, 21, 21, 22, 22, 23, 23, 24, 24, 25, 25, 26, 26, 27, 27, 28, 28, 29, 29, 30, 30, 31, 31, 32, 33, 33, 34, 34, 35, 35, 36, 36, 37, 37, 38, 38, 39

Offset: 1

Author

Thomas Scheuerle, Sep 26 2022

Keywords

• nonn

Comments

For this sequence we check the sums for all possible pairs between two distinct members of a set of consecutive odd numbers, we count as valid results of the form 2^m, valid sums are obviously >= 1.

The related sequence A357574 counts the pairs that add to a power of 2.

For sequences of consecutive odd numbers the maximum number of pairs that add to a power of 2 will never be obtained if the sequence starts with numbers greater than 1. Obviously for sequences of all negative numbers, we will not obtain any valid pair.

It appears likely that an optimal solution for A352178 will contain only odd numbers as a mix of odd and even numbers would lead to two unconnected graphs. Let us now assume A352178(k) has an optimal solution in odd numbers only, then there exists a least m such that a(k+m) uses a superset of the same solution pairs used in A352178(k). It would be interesting to know if m has a bound in relation to k.

Examples

			a(5) = 4 because {1, 3, 5, 7, 9} has four valid pairs: 1+3, 1+7, 3+5, 7+9. But {-1, 1, 3, 5, 7} has only four positive numbers and five valid pairs: 1+3, 1+7, 3+5, 3-1, 5-1, and there is no other set of consecutive numbers with 4 sums being a power of 2.
		

Links

• Thomas Scheuerle, The first differences of the first 501 elements of this sequence.

Crossrefs

Cf. A274089, A347301, A352178, A357574.

Programs

MATLAB

function a = A357409( max_n )
    a(1) = 1; q = [];
    for n = 1:max_n
        c = 0;
        for k = 0:n
            s = (2*([0:n]-k))+1;
            r = countpowtwo(s);
            if c < r
                c = r;
                q = s;
            end
        end
        a(n+1) = length(find(q > 0));
    end
end
function c = countpowtwo(s)
    M = repmat(s,[length(s),1]);
    M = M+M';
    M(M<=0) = 7;
    M = bitand(M,M-1);
    M = M + eye(size(M));
    c = length(find(M == 0))/2;
end

Formula

Conjecture: a(n) = A274089(n) + 2^t - 1, where t is the number of solutions k > 0 to the inequality n >= 2^(2*(k+1) + 1) - 2^(k+1) - 1. For n < 27, (2^t - 1) is 0, it is 1 for 27 <= n < 119, and it is 3 for 119 <= n < 495.