A020515 -id:A020515 - cp's OEIS frontend

A295827 a(n) = least odd k > 1 such that n and n*k have the same Hamming weight, or -1 if no such k exists.

-1, -1, 3, -1, 13, 3, 3, -1, 57, 13, 35, 3, 21, 3, 3, -1, 241, 57, 7, 13, 13, 35, 39, 3, 169, 21, 5, 3, 21, 3, 3, -1, 993, 241, 11, 57, 7, 7, 5, 13, 3197, 13, 9, 35, 3, 39, 13, 3, 21, 169, 3, 21, 39, 5, 47, 3, 27, 21, 5, 3, 13, 3, 3, -1, 4033, 993, 491, 241

Offset: 1

Rémy Sigrist, Nov 28 2017

The Hamming weight of a number n is given by A000120(n).
Apparently, a(n) = -1 iff n = 2^k for some k >= 0.
Apparently, a(2^n + 1) = A020515(n) for any n > 1.
a(2^n - 1) = 3 for any n > 1.
a(n) = 3 iff n = A077459(k) for some k > 1.
This sequence has similarities with A292849: here we want A000120(n*a(n)) = A000120(n), there we want A000120(n*a(n)) = A000120(a(n)).
For any n > 0, if a(n) > 0 then A292849(a(n)) <= n.

			The first terms, alongside the binary representations of n and of n*a(n), are:
  n     a(n)     bin(n)         bin(n*a(n))
  --    ----     ------         -----------
   1      -1          1                  -1
   2      -1         10                 -10
   3       3         11                1001
   4      -1        100                -100
   5      13        101             1000001
   6       3        110               10010
   7       3        111               10101
   8      -1       1000               -1000
   9      57       1001          1000000001
  10      13       1010            10000010
  11      35       1011           110000001
  12       3       1100              100100
  13      21       1101           100010001
  14       3       1110              101010
  15       3       1111              101101
  16      -1      10000              -10000
  17     241      10001       1000000000001
  18      57      10010         10000000010
  19       7      10011            10000101
  20      13      10100           100000100

Rémy Sigrist, Table of n, a(n) for n = 1..8192
Rémy Sigrist, Logarithmic scatterplot of the sequence for n=1..2^17 and a(n) < 10^18

Cf. A000120, A020515, A057168, A077459, A292849.

f:= proc(n) local k,w;
  if n = 2^padic:-ordp(n,2) then return -1 fi;
  w:= convert(convert(n,base,2),`+`);
  for k from 3 by 2 do
    if convert(convert(n*k,base,2),`+`)=w then return k fi
  od
end proc:
map(f, [$1..100]); # Robert Israel, Nov 28 2017

Table[SelectFirst[Range[3, 10^4 + 1, 2], SameQ @@ Map[DigitCount[#, 2, 1] &, {n, n #}] &] /. m_ /; MissingQ@ m -> -1, {n, 68}] (* Michael De Vlieger, Nov 28 2017 *)

A057168(n)=n+bitxor(n, n+n=bitand(n, -n))\n\4+n \\ after M. F. Hasler at A057168
a(n) = n\=2^valuation(n,2); if (n==1, -1, my(w=(n-1)/2); while(1, w=A057168(w); if((2*w+1)%n==0, return((2*w+1)/n))))

def A295827(n):
    if not(n&-n)^n: return -1
    m = n
    while True:
        m = m^((a:=-m&m+1)|(a>>1)) if m&1 else ((m&~(b:=m+(a:=m&-m)))>>a.bit_length())^b
        a, b = divmod(m,n)
        if not b and a&1: return a # Chai Wah Wu, Mar 11 2025

a(2*n) = a(n) for any n > 0.

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

A369901 Proth numbers h*2^k+1, with odd h < 2^k, ordered first by k then by h.

Original entry on oeis.org

3, 5, 13, 9, 25, 41, 57, 17, 49, 81, 113, 145, 177, 209, 241, 33, 97, 161, 225, 289, 353, 417, 481, 545, 609, 673, 737, 801, 865, 929, 993, 65, 193, 321, 449, 577, 705, 833, 961, 1089, 1217, 1345, 1473, 1601, 1729, 1857, 1985, 2113, 2241, 2369, 2497, 2625, 2753, 2881

Offset: 1

Daniel Sturm, Feb 05 2024

			Displayed as an irregular triangle:
  3;
  5, 13;
  9, 25, 41, 57;
  17, 49, 81, 113, 145, 177, 209, 241;
  ...

Daniel Sturm, Table of n, a(n) for n = 1..1023
David A. Corneth, PARI program.
E. Proth, Théorèmes sur les nombres premiers, Comptes rendus hebdomadaires des séances de l'Académie des sciences, 1878, p. 926.
Wikipedia, Proth Primes.

Cf. A080075 (Proth numbers).

Cf. A000051 (1st column), A020515 (right diagonal).

PARI
```
\\ See PARI link
```

def A369901(n):
    b = n.bit_length() - 1
    c = n - 2**b
    return (2*c+1)*2**(b+1)+1

a(2^b+c) = (2c+1)*2^(b+1)+1 for 0 <= c < 2^b. [Corrected by Thomas Ordowski, Aug 11 2025]

a(n) = (2n+1-2^m)*2^m+1 = (2n+1)*2^m-4^m+1, where m = floor(log_2(2n+1)). - Thomas Ordowski, Aug 11 2025

More terms from David A. Corneth, Feb 05 2024

cp's OEIS Frontend

A295827 a(n) = least odd k > 1 such that n and n*k have the same Hamming weight, or -1 if no such k exists.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python

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

A369901 Proth numbers h*2^k+1, with odd h < 2^k, ordered first by k then by h.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

Python

Formula

Extensions