cp's OEIS Frontend

A381764 Nearest integer not equal to n with the same Hamming weight (number of 1 bits) as n.

%I A381764 #39 Jun 20 2025 12:40:17
%S A381764 2,1,5,2,6,5,11,4,10,9,13,10,14,13,23,8,18,17,21,18,22,21,27,20,26,25,
%T A381764 29,26,30,29,47,16,34,33,37,34,38,37,43,36,42,41,45,42,46,45,55,40,50,
%U A381764 49,53,50,54,53,59,52,58,57,61,58,62,61,95,32,66,65,69,66
%N A381764 Nearest integer not equal to n with the same Hamming weight (number of 1 bits) as n.
%C A381764 a(n) = integer m nearest to n such that m <> n and A000120(n) = A000120(m).
%C A381764 Theorem: a tie does not occur for n>0, i.e. A057168(n)-n <> n-A243109(n).
%C A381764 Proof: If n is of the form 2^k-1, then there are no smaller numbers with the same Hamming weight as n and a(n) = A057168(n) = (3n+1)/2.
%C A381764 If n is of the form (2^k-1)*2^m for some k,m>0, then n in binary is of the form 11..1100..00 and A057168(n) = 2^(k+m)+2^(k-1)-1, i.e. 100..0011..11 in binary. On the other hand, A243109(n) = (2^(k-1)-1)*2^(m+1)+2^(m-1), i.e. 11..110100..00 in binary. Thus A057168(n)-n = 2^(k-1)-1+2^m >= 2^m and n-A243109(n) = 2^(m-1) < 2^m. There is no tie and a(n) = A243109(n).
%C A381764 If n is not of the form (2^k-1)*2^m, then n in binary is of the form xxx...xxx0yyy...yyy, where xxxxxx and yyyyy are both not all zeros. If yyy...yyy is of the form 2^r-1, then A243109(n) must flip one of the '1' bit in xxx...xxx whereas A057168(n) leaves xxx...xxx unchanged. Thus n-A243109(n) > A057168(n)-n. Otherwise A057168(n) and A243109(n) will not change the bits xxx...xxx and reduces to the problem for yyy...yyy and thus the result follows by induction.
%C A381764 The above also gives a procedure to determine when a(n) = A057168(n) and when a(n) = A243109(n) or more succinctly a(n) = A243109(n) if n is even and a(n) = A057168(n) otherwise.
%H A381764 Robert Israel, <a href="/A381764/b381764.txt">Table of n, a(n) for n = 1..10000</a>
%H A381764 Marc B. Reynolds, <a href="https://marc-b-reynolds.github.io/math/2023/11/09/PopNextPrev.html">Popcount walks: next, previous, toward and nearest</a> (2023).
%F A381764 a(n) = A243109(n) if n is even and a(n) = A057168(n) otherwise.
%F A381764 a(2^k-1) = A055010(k).
%F A381764 For k,m > 0, a((2^k-1)*2^m) = 2^(m-1)*(2^(k+1)-3).
%e A381764 For n = 2, A057168(2) = 4 and A243109(2) = 1 and 1 is closer to 2 than 4, thus a(2) = 1.
%p A381764 f:= proc(n) local t,k,d;
%p A381764   if n::even then d:=-1 else d:= 1 fi;
%p A381764   t:= convert(convert(n,base,2),`+`);
%p A381764   for k from n+d by d do
%p A381764     if convert(convert(k,base,2),`+`) = t then return k fi
%p A381764   od
%p A381764 end proc:
%p A381764 map(f, [$1..100]); # _Robert Israel_, Jun 20 2025
%o A381764 (Python)
%o A381764 def A381764(n): return n^((a:=-n&n+1)|(a>>1))
%Y A381764 Cf. A000120, A055010, A057168, A243109.
%K A381764 nonn
%O A381764 1,1
%A A381764 _Chai Wah Wu_, Mar 06 2025