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,2

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.

Links

Table of n, a(n) for n=1..69.

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

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.

Example

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.

Prog

(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

Crossrefs

Cf. A274089, A347301, A352178, A357574.

Sequence in context: A020888 A196393 A274089 * A086335 A123387 A123070

Adjacent sequences: A357406 A357407 A357408 * A357410 A357411 A357412

Keyword

nonn

Author

Thomas Scheuerle, Sep 26 2022

Status

approved