A274089 -id:A274089 - cp's OEIS frontend

A002960 The square sieve.

2, 5, 8, 12, 17, 22, 28, 34, 41, 48, 56, 65, 74, 84, 94, 105, 116, 128, 140, 153, 166, 180, 194, 209, 224, 240, 257, 274, 292, 310, 329, 348, 368, 388, 409, 430, 452, 474, 497, 520, 544, 568, 593, 618, 644, 670, 697, 724, 752, 780, 809, 838, 868, 898, 929, 960, 992, 1025, 1058, 1092, 1126, 1161, 1196

Offset: 1

N. J. A. Sloane

nonn

See example for the construction used.

Conjecture: The first differences are given by A274089 (omitting the first two terms 1 and 2). - Alisa Ediger, Jun 04 2016

			Start with
  1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,...
Remove all square-th terms, 1,4,9,16,... to get
  2,3,5,6,7,8,10,11,12,13,14,15,17,18,19,20,21,22,23,...
Return 2 as the first term in the sequence and remove it to get
  3,5,6,7,8,10,11,12,13,14,15,17,18,19,20,21,22,23,...
Remove the 1st,4th,9th,16th,... terms to get
  5,6,8,10,11,12,14,15,17,18,19,20,22,23,...
Return 5 as the next term in the sequence and remove it to get
  6,8,10,11,12,14,15,17,18,19,20,22,23,...
Remove the 1st,4th,9th,16th,... terms to get
  8,10,12,14,15,17,19,20,22,23,...
Return 8 as the next term in the sequence and remove it to get
  10,12,14,15,17,19,20,22,23,...
Remove the 1st,4th,9th,16th,... terms to get
  12,14,15,19,20,22,23,...
etc. - _Sean A. Irvine_, Dec 10 2014

David L. Silverman, Problem #116, The Square Sieve, J. Rec. Math., 4 (1971), 288-289.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Sean A. Irvine, Table of n, a(n) for n = 1..1000
Index entries for sequences generated by sieves

Cf A274089.

sieve:= L -> subsop(seq(i^2=NULL, i=1..floor(sqrt(nops(L)))),L):
A:= [$1..10^5]:
for n from 1 do
  A:= sieve(A);
  if nops(A) = 0 then break fi;
  R[n]:= A[1];
  A:= subsop(1=NULL,A);
od:
seq(R[i],i=1..n-1); # Robert Israel, Dec 11 2014

First /@ NestWhileList[Function[w, {First@ #, Rest@ #} &@ Delete[Last@ w, #] &@ Map[{#} &, Reverse@ Range[Floor@ Sqrt@ Length[Last@ w]]^2]], {0, Range@ 1200}, Length@ Last@ # > 1 &] (* Michael De Vlieger, Jun 05 2016 *)

Conjecture: a(n) = a(n-1) + 1 + floor(sqrt(a(n-1) + 1 + floor(sqrt(a(n-1))))); a(1) = 2. - Gionata Neri, Jun 22 2015

Conjecture: a(n) = 2^(x-1)*(2^(x-1)+y-1) + floor((y+1)^2/4), where y = n+1+x-2^x and x = floor(log_2(n+1+floor(log_2(n)))). - Gionata Neri, Jul 05 2015

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.

Original entry on oeis.org

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

Thomas Scheuerle, Sep 26 2022

nonn

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.

			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.

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

Cf. A274089, A347301, A352178, A357574.

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

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.

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

Original entry on oeis.org

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, 54, 56, 59, 62, 65, 68, 71, 74, 77, 80, 83, 86, 89, 92, 95, 98, 101, 104, 107, 110, 113, 116, 119, 122, 125, 128, 131, 134, 137, 140, 143, 146, 150, 153, 157, 160, 164, 167

Offset: 1

Thomas Scheuerle, Oct 04 2022

nonn

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].
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.
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).

			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.

Thomas Scheuerle, a(n+1) - a(n) for n = 1..500
Max A. Alekseyev, On computing sets of integers with maximum number of pairs summing to powers of 2, arXiv:2303.02872 [math.CO], 2023.

Cf. A020515, A129868, A274089, A347301, A352178, A357409.

function a = A357574( max_n )
    a(1) = 0; 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) = c;
    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

a(n) <= A352178(n).

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.

Edited by Max Alekseyev, Mar 09 2023

A274004 First differences of A002960.

Original entry on oeis.org

3, 3, 4, 5, 5, 6, 6, 7, 7, 8, 9, 9, 10, 10, 11, 11, 12, 12, 13, 13, 14, 14, 15, 15, 16, 17, 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

Offset: 1

Alisa Ediger, Jun 06 2016

nonn

The squared sieve sequence (A002960) increases by one, beginning with three, every two integers except a difference of 2^n appears only once. This is the sequence of first differences. This has not yet been proven in the general case.

Cf. A002960, A274089.

Rest@ Differences@ Map[First, NestWhileList[Function[w, {First@ #, Rest@ #} &@ Delete[Last@ w, #] &@ Map[{#} &, Reverse@ Range[Floor@ Sqrt@ Length[Last@ w]]^2]], {0, Range@ 1200}, Length@ Last@ # > 1 &]] (* Michael De Vlieger, Aug 10 2016 *)

Conjecture: a(n) = A274089(n+2). - Omar E. Pol, Aug 10 2016

cp's OEIS Frontend

A002960 The square sieve.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

MATLAB

Formula

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

MATLAB

Formula

Extensions

A274004 First differences of A002960.

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

Formula