A077459 -id:A077459 - cp's OEIS frontend

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.

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.

A162215 a(n) is the smallest multiple of n that is greater than 2n and contains the same number of 1's in its binary representation as n contains.

Original entry on oeis.org

4, 8, 9, 16, 20, 18, 21, 32, 36, 40, 44, 36, 52, 42, 45, 64, 68, 72, 76, 80, 84, 88, 92, 72, 100, 104, 108, 84, 116, 90, 93, 128, 132, 136, 140, 144, 148, 152, 156, 160, 164, 168, 172, 176, 135, 184, 188, 144, 196, 200, 153, 208, 212, 216, 220, 168, 228, 232, 236

Offset: 1

Leroy Quet, Jun 28 2009

a(n) = 3n only if n is in sequence A077459. Otherwise, a(n) = 4n.

			15 in binary is 1111, which contains four 1's as binary digits. 15*3 = 45, which is 101101 in binary. This also contains four 1's. So a(15) = 3*15 = 45.

Michael De Vlieger, Table of n, a(n) for n = 1..10000

Cf. A077459.

A000120 := proc(n) add(d,d=convert(n,base,2)) ; end: A162215 := proc(n) local k; for k from 3 do if A000120(k*n)= A000120(n) then RETURN(k*n) ; fi; od: end: seq(A162215(n),n=1..80) ; # R. J. Mathar, Jul 04 2009

Array[Block[{k = 3, d = DigitCount[#, 2, 1]}, While[DigitCount[k #, 2, 1] != d, k++]; k #] &, 59] (* Michael De Vlieger, Feb 24 2019 *)

a(4) corrected and sequence extended by R. J. Mathar, Jul 04 2009

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

Original entry on oeis.org

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

A381754 Numbers k such that k and 3*k have the same number of zeros in their binary expansions.

Original entry on oeis.org

0, 1, 2, 4, 8, 16, 19, 32, 35, 38, 39, 53, 64, 67, 70, 71, 76, 78, 79, 101, 105, 106, 117, 128, 131, 134, 135, 140, 142, 143, 152, 156, 158, 159, 197, 201, 202, 209, 210, 212, 229, 233, 234, 245, 256, 259, 262, 263, 268, 270, 271, 280, 284, 286, 287, 301, 304

Offset: 1

Barak Manos, Mar 06 2025

If n is in the sequence, so is 2n, hence the sequence is infinite. - Charles R Greathouse IV, Mar 06 2025

This sequence corresponds to the numbers m such that A381934(m) <= 3. - Rémy Sigrist, Mar 12 2025

Robert Israel, Table of n, a(n) for n = 1..10000

Cf. A023416, A077459, A381934.

filter:= proc(n) numboccur(0,convert(n,base,2)) = numboccur(0,convert(3*n,base,2)) end proc:
select(filter, [$0..400]); # Robert Israel, Apr 07 2025

Select[Range[0, 320], Equal @@ DigitCount[{#, 3*#}, 2, 0] &] (* Amiram Eldar, Mar 06 2025 *)

nz(n) = if(n == 0, 1, 1+logint(n, 2) - hammingweight(n))
is(n)=nz(n)==nz(3*n) \\ Charles R Greathouse IV, Mar 06 2025

def ok(n): return bin(n).count('0') == bin(n * 3).count('0')

cp's OEIS Frontend

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

A162215 a(n) is the smallest multiple of n that is greater than 2n and contains the same number of 1's in its binary representation as n contains.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Extensions

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

Views

Author

Keywords

Comments

Crossrefs

Programs

MATLAB

PARI

A381754 Numbers k such that k and 3*k have the same number of zeros in their binary expansions.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python