A292849 -id:A292849 - cp's OEIS frontend

A340349 a(n) is the smallest k such that A292849(k) = 2n-1.

1, 3, 13, 5, 57, 35, 21, 9, 241, 219, 49, 45, 169, 83, 73, 17, 993, 59, 941, 53, 3197, 51, 185, 93, 209, 81, 349, 85, 41, 89, 105, 33, 4033, 491, 4749, 247, 449, 227, 429, 363, 3249, 401, 193, 259, 233, 107, 117, 189, 697249, 1355, 173, 517, 473, 1091, 101, 231, 725, 305

Offset: 1

Thomas Scheuerle, Jan 05 2021

This implies that a(n)=k is a solution to A000120(2*n-1) = A000120((2*n-1)*k), where A000120 is the Hamming weight. If no such number exists we define a(n) = 2.
Does this sequence consist only of odd numbers? It appears so.
This will be the case if A292849 contains all odd numbers, because a(n) will then never become 2.
A292849 must contain all odd numbers if two conditions are satisfied:
First: For every odd number 2n-1 there must be an odd k > 1 that satisfies A000120(2n-1) = A000120((2n-1)*k). To prove that this condition is satisfied, it may be helpful that if k*m = 2^j+r, we know that A000120(k*m) = A063787(r) and for each Hamming weight there exists an r such that A063787(r) = A063787(r+1). This allows us to choose r such that the Hamming weight becomes A000120(m) = A063787(r). For a given r, k*m = 2^j+r may have no solutions if k or m are divisors of r, but there may still exist a solution for k*m = 2^j+r+1. Of course this is not a complete proof.
Second: For every n there needs to be a number k such that 2n-1 is the smallest solution to A000120(2n-1) = A000120((2n-1)*k). This is satisfied if no row in A340441 is a subset of a previous row.
No odd number can appear more than once in this sequence, but not all odd numbers will appear, so this sequence is not a permutation of the odd numbers.
This sequence can be constructed from A340441. Start with a(1) = 1, then a(n) is the least number in row n-1 of A340441 that has not already appeared in A340441.

Cf. A000120, A292849, A340069, A263132, A077459, A295827, A340441, A340351 table of multiplications.

function a = A340349(maxA292849)
c = A340351(maxA292849,1);
n = 1; run = 1;
while run == 1
     i = find(c==(n*2)-1);
     if ~isempty(i);
         a(n) = i(1);
         n = n+1;
     else
         run = 0;
     end
end
end
function a = A340351(max_n,max_m)
    for n = 1:max_n
        m = 1; k = 1;
        while m < max_m+1
            c = length(find(bitget(k,1:32)== 1));
            if c == length(find(bitget(n*k,1:32)== 1))
                a(n,m) = k;
                m = m+1;
            end
            k = k +1;
        end
    end
end

f(n) = my(k=1); while ((hammingweight(k)) != hammingweight(k*n), k++); k; \\ A292849
a(n) = my(k=1); while(f(k) != 2*n-1, k++); k; \\ Michel Marcus, Jan 09 2021

A340069 a(n) is the smallest number k not yet used such that the number of 1-bits in the binary representation of k equals the number of 1-bits in the binary representation of k*n.

Original entry on oeis.org

0, 1, 2, 3, 4, 7, 6, 14, 5, 15, 27, 12, 24, 10, 19, 30, 8, 31, 43, 28, 39, 13, 35, 45, 48, 62, 20, 57, 37, 63, 60, 79, 9, 126, 91, 11, 86, 29, 56, 23, 54, 75, 26, 51, 70, 46, 47, 22, 89, 21, 93, 83, 40, 61, 114, 78, 38, 18, 71, 87, 77, 42, 124, 127, 16, 254, 187, 92, 151, 90, 44, 58, 117

Offset: 0

Thomas Scheuerle, Dec 28 2020

I would call this sequence "the evil beast" because it shows many patterns, but for each pattern there seems to be a value of n at which the rules change suddenly or some unexpected exceptions occur.
If n is a power of 2 any number satisfies the condition as the number of 1-bits does not change by multiplication by a power of 2. Because of this every number eventually has a chance to appear in this sequence; this proves that this sequence is a permutation of the nonnegative integers.
This sequence may have applications in finding small pairs of b and c such that A000120(b)=A000120(c*b), because A000120(a(n))=A000120(a(n)*n).
All fixed points n = a(n) are described in A340100 and are a subset of A077436.
In the range n = 0..100000 the largest value a(n) is 131072 = a(32769), but the smallest value in the range n = 30000..40000 is a(32768) = 137.
If A000120(b)=A000120(c*b) then A000120(b*2^d)=A000120(c*b*2^d); this causes some patterns in this sequence which may be valid in a limited range of n. Can we find one which is valid for a large range of values of n?
If a(n) is a power of two, then n is a power of two as well. But if n is a power of two, a(n) is not always a power of two.
In equations of the form A000120(c)=A000120(c*b) for all A000120(c)=2 we find all solutions for b as b=0, b=2^d or b=(2^d)*(1+2^(((c-1)/2)+e*(c-1)))/c, if c is odd. For even c divide c by largest possible power of two. An example for c=3 is b=A263132.
a(n) >= A292849(n). This lower bound is responsible for some of the peaks in this sequence.

Thomas Scheuerle, Table of n, a(n) for n = 0..10000
Thomas Scheuerle, This sequence shows an extreme chaotic graph.
Index entries for sequences that are permutations of the natural numbers

Cf. A000120, A077436, A340100, A263132 (numbers such that A000120(3)=A000120(3*m)), A077459 (numbers such that A000120(m)=A000120(3*m)), A292849 (the least m such that A000120(n*m) = A000120(m)), A340351.

function a = A340069( max_n )
    a(1) = 1;
    n = 2;
    t = 1;
    while n <= max_n
        % search next number t not yet used in a
        while ~isempty(find(a==t, 1))
            t = t+1;
        end
        bits1 = length(find(bitget(t,1:32)== 1));
        bits2 = length(find(bitget(t*n,1:32)== 1));
        if (bits1 == bits2)
            % we found a candidate
            a(n) = t;
            t = 1;
            n = n+1;
        else
            % number t does not yet fit
            t = t+1;
        end
    end
end

lista(nn) = {my(va = vector(nn, k, -1)); for (n=0, nn-1, my(k=0); while(! ((hammingweight(k*n) == hammingweight(k)) && !(#select(x->(x==k), va))), k++); va[n+1] = k;); va;} \\ Michel Marcus, Dec 30 2020

def binwt(n): return bin(n).count('1')
def aupto(n):
  alst, aset = [], set()
  for k in range(n+1):
    ak = 0
    while True:
      while ak in aset: ak += 1
      if binwt(ak)==binwt(k*ak): break
      ak += 1
    alst.append(ak)
    aset.add(ak)
  return alst
print(aupto(72)) # Michael S. Branicky, Jan 02 2021

a(n) = n if n < 5.
a(2^(2*n)) = 2^(1+n) if n < 5.
a(2^(2*n+1)) = 2^(1+n)+1 if n < 5.
a(3*2^n) = 3*2^(n+1) if n > 0 and < 4.

A340351 Square array, read by descending antidiagonals, where row n gives all solutions k > 0 to A000120(k)=A000120(k*n), A000120 is the Hamming weight.

Original entry on oeis.org

1, 2, 1, 3, 2, 3, 4, 3, 6, 1, 5, 4, 7, 2, 7, 6, 5, 12, 3, 14, 3, 7, 6, 14, 4, 15, 6, 7, 8, 7, 15, 5, 27, 7, 14, 1, 9, 8, 24, 6, 28, 12, 15, 2, 15, 10, 9, 28, 7, 30, 14, 19, 3, 30, 7, 11, 10, 30, 8, 31, 15, 28, 4, 31, 14, 3, 12, 11, 31, 9, 39, 24, 30, 5, 43, 15, 6, 3, 13, 12

Offset: 1

Thomas Scheuerle, Jan 05 2021

Square array is read by descending antidiagonals, as A(1,1), A(1,2), A(2,1), A(1,3), A(2,2), A(3,1), etc.
Rows at positions 2^k are 1, 2, 3, ..., (A000027). Row 2n is equal to row n.
Values are different from those in A115872, because we use multiplication with carry here.

			Eight initial terms of rows 1 - 8 are listed below:
   1:  1,  2,  3,   4,   5,   6,   7,   8, ...
   2:  1,  2,  3,   4,   5,   6,   7,   8, ...
   3:  3,  6,  7,  12,  14,  15,  24,  28, ...
   4:  1,  2,  3,   4,   5,   6,   7,   8, ...
   5:  7, 14, 15,  27,  28,  30,  31,  39, ...
   6:  3,  6,  7,  12,  14,  15,  24,  28, ...
   7:  7, 14, 15,  19,  28,  30,  31,  37, ...
   8:  1,  2,  3,   4,   5,   6,   7,   8, ...
a(6,3) = 7 because: 7 in binary is 111 and 6*7 = 42 in binary is 101001, both have 3 bits set to 1.

Cf. A000120, A292849 (1st column), A340069, A077459 (3rd row).

function [a] = A340351(max_n)
    for n = 1:max_n
        m = 1;
        k = 1;
        while m < max_n
            c = length(find(bitget(k,1:32)== 1));
            if c == length(find(bitget(n*k,1:32)== 1))
                a(n,m) = k;
                m = m+1;
            end
            k = k +1;
        end
    end
end

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.

Original entry on oeis.org

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

A381934 a(n) is the least k > 1 such that the binary expansions of n and n*k have the same number of nonleading zeros.

Original entry on oeis.org

2, 3, 3, 5, 3, 6, 5, 9, 3, 5, 6, 5, 5, 19, 9, 17, 3, 5, 5, 3, 6, 9, 5, 11, 5, 7, 19, 301, 9, 35, 17, 33, 3, 5, 5, 3, 5, 5, 3, 3, 6, 5, 9, 5, 5, 17, 11, 305, 5, 7, 7, 15, 19, 3, 301, 9, 9, 71, 35, 13, 17, 67, 33, 65, 3, 5, 5, 3, 5, 5, 3, 3, 5, 10, 5, 10, 3, 6

Offset: 0

Rémy Sigrist, Mar 10 2025

This sequence is well defined (see A381935).

			The first terms, alongside the binary expansions of n and n*a(n), are:
  n   a(n)  bin(n)  bin(n*a(n))
  --  ----  ------  -----------
   0     2       0            0
   1     3       1           11
   2     3      10          110
   3     5      11         1111
   4     3     100         1100
   5     6     101        11110
   6     5     110        11110
   7     9     111       111111
   8     3    1000        11000
   9     5    1001       101101
  10     6    1010       111100
  11     5    1011       110111
  12     5    1100       111100
  13    19    1101     11110111
  14     9    1110      1111110
  15    17    1111     11111111
  16     3   10000       110000

Rémy Sigrist, Table of n, a(n) for n = 0..8192
Rémy Sigrist, PARI program

Cf. A023416, A292849, A295827, A352217, A381935.

PARI
```
\\ See Links section.
```

a(2^n) = 3.

a(2^n - 1) = 2^n + 1.

A292895 a(n) is the least positive k such that the Hamming weight of k equals the Hamming weight of k + n.

Original entry on oeis.org

1, 1, 2, 1, 4, 5, 2, 1, 8, 3, 10, 6, 4, 5, 2, 1, 16, 3, 6, 5, 20, 3, 12, 10, 8, 9, 10, 6, 4, 5, 2, 1, 32, 3, 6, 5, 12, 3, 10, 9, 40, 11, 6, 5, 24, 3, 20, 18, 16, 7, 18, 17, 20, 12, 12, 10, 8, 9, 10, 6, 4, 5, 2, 1, 64, 3, 6, 5, 12, 3, 10, 9, 24, 11, 6, 5, 20, 3, 18, 17, 80, 7, 22, 14, 12, 13, 10, 9, 48

Offset: 0

Rémy Sigrist and Altug Alkan, Sep 26 2017

Inspired by A292849.
The Hamming weight of a number n is given by A000120(n).
Let b(n) be the smallest t such that a(t) = n. Initial values of b(n) are 0, 2, 9, 4, 5, 11, 49, 8, 25, 10, 41, 22, 85, 83, 225, 16, 51, 47, 177, 20, ... See the logarithmic line graph of first 10^3 terms of b(n) sequence in Links section.
Apparently, n = a(n) iff n belongs to A094958. - Rémy Sigrist, Oct 02 2017

			a(49) = 7 since A000120(7) = A000120(7 + 49) and 7 is the least number with this property.

Rémy Sigrist, Table of n, a(n) for n = 0..16384
Altug Alkan, A logarithmic scatterplot of a(n) for n <= 10^6
Altug Alkan, A logarithmic line graph of b(n) for n <= 10^3

Cf. A000120, A094958, A292849.

N:= 1000: # to get all terms before the first where n+a(n)>N
H:= Array(0..N, t -> convert(convert(t,base,2),`+`)):
f:= proc(n) local k;
  for k from 1 to N-n do
    if H[k]=H[k+n] then return k fi
  od:
0
end proc:
R:= NULL:
for n from 0 do
v:= f(n);
if v = 0 then break fi;
  R:= R, v;
od:
R; # Robert Israel, Sep 27 2017

h[n_] := First@ DigitCount[n, 2]; a[n_] := Block[{k=1}, While[h[k] != h[k + n], k++]; k]; Array[a, 90] (* Giovanni Resta, Sep 28 2017 *)

a(n) = {my(k=1); while ((hammingweight(k)) != hammingweight(n+k), k++); k; }

a(n) <= n for n >= 1.
a(2*n) = 2*a(n) for n >= 1.
a(2^m) = 2^m and a(5*2^m) = 5*2^m for m >= 0.
a(2^m - 1) = 1 for m >= 0.
a(2^m + 1) = 3 and a(2^m - 3) = 5 for m >= 3.
a(2^m + 3) = 5 for m >= 4.
a((2^m - 1)^2) = 2^m - 1 for m >= 1.
a(2^(m + 2) + 2^m - 1) = 2^m + 1 m >= 1.
a((2^m + 1)^2) = 7 for m >= 3.

cp's OEIS Frontend

A340349 a(n) is the smallest k such that A292849(k) = 2n-1.

Views

Author

Keywords

Comments

Crossrefs

Programs

MATLAB

PARI

A340069 a(n) is the smallest number k not yet used such that the number of 1-bits in the binary representation of k equals the number of 1-bits in the binary representation of k*n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

MATLAB

PARI

Python

Formula

A340351 Square array, read by descending antidiagonals, where row n gives all solutions k > 0 to A000120(k)=A000120(k*n), A000120 is the Hamming weight.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

MATLAB

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

A381934 a(n) is the least k > 1 such that the binary expansions of n and n*k have the same number of nonleading zeros.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A292895 a(n) is the least positive k such that the Hamming weight of k equals the Hamming weight of k + n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula