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,3

Comments

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.

Links

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

Formula

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.

Prog

(MATLAB)
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
(PARI) 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
(Python)
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

Crossrefs

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.

Sequence in context: A006875 A064554 A290641 * A265352 A265368 A239972

Adjacent sequences: A340066 A340067 A340068 * A340070 A340071 A340072

Keyword

nonn,base

Author

Thomas Scheuerle, Dec 28 2020

Status

approved