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.

%I A340069 #102 Jan 09 2021 11:06:21
%S A340069 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,
%T A340069 20,57,37,63,60,79,9,126,91,11,86,29,56,23,54,75,26,51,70,46,47,22,89,
%U A340069 21,93,83,40,61,114,78,38,18,71,87,77,42,124,127,16,254,187,92,151,90,44,58,117
%N 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.
%C A340069 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.
%C A340069 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.
%C A340069 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).
%C A340069 All fixed points n = a(n) are described in A340100 and are a subset of A077436.
%C A340069 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.
%C A340069 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?
%C A340069 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.
%C A340069 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.
%C A340069 a(n) >= A292849(n). This lower bound is responsible for some of the peaks in this sequence.
%H A340069 Thomas Scheuerle, <a href="/A340069/b340069.txt">Table of n, a(n) for n = 0..10000</a>
%H A340069 Thomas Scheuerle, <a href="/A340069/a340069.svg">This sequence shows an extreme chaotic graph</a>.
%H A340069 <a href="/index/Per#IntegerPermutation">Index entries for sequences that are permutations of the natural numbers</a>
%F A340069 a(n) = n if n < 5.
%F A340069 a(2^(2*n)) = 2^(1+n) if n < 5.
%F A340069 a(2^(2*n+1)) = 2^(1+n)+1 if n < 5.
%F A340069 a(3*2^n) = 3*2^(n+1) if n > 0 and < 4.
%o A340069 (MATLAB)
%o A340069 function a = A340069( max_n )
%o A340069     a(1) = 1;
%o A340069     n = 2;
%o A340069     t = 1;
%o A340069     while n <= max_n
%o A340069         % search next number t not yet used in a
%o A340069         while ~isempty(find(a==t, 1))
%o A340069             t = t+1;
%o A340069         end
%o A340069         bits1 = length(find(bitget(t,1:32)== 1));
%o A340069         bits2 = length(find(bitget(t*n,1:32)== 1));
%o A340069         if (bits1 == bits2)
%o A340069             % we found a candidate
%o A340069             a(n) = t;
%o A340069             t = 1;
%o A340069             n = n+1;
%o A340069         else
%o A340069             % number t does not yet fit
%o A340069             t = t+1;
%o A340069         end
%o A340069     end
%o A340069 end
%o A340069 (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
%o A340069 (Python)
%o A340069 def binwt(n): return bin(n).count('1')
%o A340069 def aupto(n):
%o A340069   alst, aset = [], set()
%o A340069   for k in range(n+1):
%o A340069     ak = 0
%o A340069     while True:
%o A340069       while ak in aset: ak += 1
%o A340069       if binwt(ak)==binwt(k*ak): break
%o A340069       ak += 1
%o A340069     alst.append(ak)
%o A340069     aset.add(ak)
%o A340069   return alst
%o A340069 print(aupto(72)) # _Michael S. Branicky_, Jan 02 2021
%Y A340069 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.
%K A340069 nonn,base
%O A340069 0,3
%A A340069 _Thomas Scheuerle_, Dec 28 2020