A340351 -id:A340351 - 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.

A340441 Square array, read by ascending antidiagonals, where row n gives all odd solutions k > 1 and n > 0 to A000120(2n+1) = A000120((2n+1)*k), A000120 is the Hamming weight.

Original entry on oeis.org

3, 13, 11, 3, 205, 43, 57, 5, 3277, 171, 35, 3641, 7, 52429, 683, 21, 47, 233017, 19, 838861, 2731, 3, 79, 99, 14913081, 23, 13421773, 10923, 241, 5, 197, 187, 954437177, 37, 214748365, 43691, 7, 61681, 7, 325, 419, 61083979321, 39, 3435973837, 174763

Offset: 1

Thomas Scheuerle, Jan 07 2021

Solutions to related equation A000120(k) = A000120(k*n) are A340351.

			Five initial terms of rows 1-5 are listed below:
   1:  3,   11,     43,       171,       683, ...
   2: 13,  205,   3277,     52429,    838861, ...
   3:  3,    5,      7,        19,        23, ...
   4: 57, 3641, 233017,  14913081, 954437177, ...
   5: 35,   47,      99,      187,       419, ...
T(3,4) = 19 because: (3*2+1) in binary is 111 and (3*2+1)*19 = 133 in binary is 10000101, both have 3 bits set to 1.

Pontus von Brömssen, Antidiagonals n = 1..100, flattened

Cf. A000120, A340351, A340069.

Cf. A263132 (superset of 1st row), A007583 (1st row), A299960 (2nd row).

If 2*n = 2^j, then T(n, m) = (1+2^(j+2*j*m))/(2*n+1) for m > 0. In particular:
  T(1, m) = (1+2^(1+2*m))/3 = A007583(m),
  T(2, m) = (1+2^(2+4*m))/5 = A299960(m),
  T(4, m) = (1+2^(3+6*m))/9.
The third row consists of all numbers of the form (1+2^(1+b*3)+2^(2+c*3))/7, where b and c are natural numbers >= 0 and b+c > 0.
The seventh row consists of all numbers of the form (1+2^(1+b*2)+2^(2+c*2)+2^(3+d*2))/15 where b, c, and d are natural numbers >= 0 and b+c+d > 1.

More terms from Pontus von Brömssen, Jan 08 2021

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

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

Original entry on oeis.org

1, 1, 2, 1, 2, 4, 1, 2, 3, 8, 1, 2, 4, 4, 16, 1, 2, 4, 8, 6, 32, 1, 2, 3, 8, 16, 8, 64, 1, 2, 3, 4, 13, 32, 11, 128, 1, 2, 4, 4, 6, 16, 64, 12, 256, 1, 2, 2, 8, 5, 8, 26, 128, 16, 512, 1, 2, 4, 8, 16, 6, 11, 32, 256, 22, 1024

Offset: 1

Thomas Scheuerle, Jan 11 2021

Solutions to related equation A000120(k) = A000120(k*n) are A340351.

The same sequence without leading ones and only odd solutions is A340441.

			Eight initial terms of rows 1-8 are listed below:
   1: 1, 2, 4, 8, 16, 32, 64, 128, ...
   2: 1, 2, 3, 4,  6,  8, 11,  12, ...
   3: 1, 2, 4, 8, 16, 32, 64, 128, ...
   4: 1, 2, 4, 8, 13, 16, 26,  32, ...
   5: 1, 2, 3, 4,  6,  8, 11,  12, ...
   6: 1, 2, 3, 4,  5,  6,  7,   8, ...
   7: 1, 2, 4, 8, 16, 32, 64, 128, ...
   8: 1, 2, 4, 8, 16, 32, 57,  64, ...
T(3,4) = 8 because: (3+1) in binary is 100 and (3*1)*8 = 32 in binary is 100000, both have 1 bit set to 1.

Cf. A000120, A340351, A340069, A340441.

Cf. A263132 (superset of 1st row), A007583 (1st row), A299960 (2nd row).

T(2n, ...)   = 2^{0,1,2,...}, 2^{0,1,2,...} * row n of A340441.
T(4n+1, ...) = 2^{0,1,2,...}, 2^{0,1,2,...} * row n of A340441.
T(2^n, ...)  = 2^{0,1,2,...}.

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

A340441 Square array, read by ascending antidiagonals, where row n gives all odd solutions k > 1 and n > 0 to A000120(2n+1) = A000120((2n+1)*k), A000120 is the Hamming weight.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions

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

Views

Author

Keywords

Comments

Crossrefs

Programs

MATLAB

PARI

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

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

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

A340441 Square array, read by ascending antidiagonals, where row n gives all odd solutions k > 1 and n > 0 to A000120(2*n+1) = A000120((2*n+1)*k), A000120 is the Hamming weight.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions

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

Views

Author

Keywords

Comments

Crossrefs

Programs

MATLAB

PARI

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

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

A340441 Square array, read by ascending antidiagonals, where row n gives all odd solutions k > 1 and n > 0 to A000120(2n+1) = A000120((2n+1)*k), A000120 is the Hamming weight.