login
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.
6
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.
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
KEYWORD
nonn,base
AUTHOR
Thomas Scheuerle, Dec 28 2020
STATUS
approved