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

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, 29, 26, 30, 29, 47, 16, 34, 33, 37, 34, 38, 37, 43, 36, 42, 41, 45, 42, 46, 45, 55, 40, 50, 49, 53, 50, 54, 53, 59, 52, 58, 57, 61, 58, 62, 61, 95, 32, 66, 65, 69, 66

Offset: 1

Author

Chai Wah Wu, Mar 06 2025

Keywords

• nonn

Comments

a(n) = integer m nearest to n such that m <> n and A000120(n) = A000120(m).

Theorem: a tie does not occur for n>0, i.e. A057168(n)-n <> n-A243109(n).

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.

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).

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.

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.

Examples

			For n = 2, A057168(2) = 4 and A243109(2) = 1 and 1 is closer to 2 than 4, thus a(2) = 1.
		

Links

• Robert Israel, Table of n, a(n) for n = 1..10000
• Marc B. Reynolds, Popcount walks: next, previous, toward and nearest (2023).

Crossrefs

Cf. A000120, A055010, A057168, A243109.

Programs

Maple

f:= proc(n) local t,k,d;
  if n::even then d:=-1 else d:= 1 fi;
  t:= convert(convert(n,base,2),`+`);
  for k from n+d by d do
    if convert(convert(k,base,2),`+`) = t then return k fi
  od
end proc:
map(f, [$1..100]); # Robert Israel, Jun 20 2025

Python

def A381764(n): return n^((a:=-n&n+1)|(a>>1))

Formula

a(n) = A243109(n) if n is even and a(n) = A057168(n) otherwise.

a(2^k-1) = A055010(k).

For k,m > 0, a((2^k-1)*2^m) = 2^(m-1)*(2^(k+1)-3).