A295827 a(n) = least odd k > 1 such that n and n*k have the same Hamming weight, or -1 if no such k exists.

-1, -1, 3, -1, 13, 3, 3, -1, 57, 13, 35, 3, 21, 3, 3, -1, 241, 57, 7, 13, 13, 35, 39, 3, 169, 21, 5, 3, 21, 3, 3, -1, 993, 241, 11, 57, 7, 7, 5, 13, 3197, 13, 9, 35, 3, 39, 13, 3, 21, 169, 3, 21, 39, 5, 47, 3, 27, 21, 5, 3, 13, 3, 3, -1, 4033, 993, 491, 241

Offset: 1

Author

Rémy Sigrist, Nov 28 2017

Keywords

• sign
• base

Comments

The Hamming weight of a number n is given by A000120(n).

Apparently, a(n) = -1 iff n = 2^k for some k >= 0.

Apparently, a(2^n + 1) = A020515(n) for any n > 1.

a(2^n - 1) = 3 for any n > 1.

a(n) = 3 iff n = A077459(k) for some k > 1.

This sequence has similarities with A292849: here we want A000120(n*a(n)) = A000120(n), there we want A000120(n*a(n)) = A000120(a(n)).

For any n > 0, if a(n) > 0 then A292849(a(n)) <= n.

Examples

			The first terms, alongside the binary representations of n and of n*a(n), are:
  n     a(n)     bin(n)         bin(n*a(n))
  --    ----     ------         -----------
   1      -1          1                  -1
   2      -1         10                 -10
   3       3         11                1001
   4      -1        100                -100
   5      13        101             1000001
   6       3        110               10010
   7       3        111               10101
   8      -1       1000               -1000
   9      57       1001          1000000001
  10      13       1010            10000010
  11      35       1011           110000001
  12       3       1100              100100
  13      21       1101           100010001
  14       3       1110              101010
  15       3       1111              101101
  16      -1      10000              -10000
  17     241      10001       1000000000001
  18      57      10010         10000000010
  19       7      10011            10000101
  20      13      10100           100000100
		

Links

• Rémy Sigrist, Table of n, a(n) for n = 1..8192
• Rémy Sigrist, Logarithmic scatterplot of the sequence for n=1..2^17 and a(n) < 10^18

Crossrefs

Cf. A000120, A020515, A057168, A077459, A292849.

Programs

Maple

f:= proc(n) local k,w;
  if n = 2^padic:-ordp(n,2) then return -1 fi;
  w:= convert(convert(n,base,2),`+`);
  for k from 3 by 2 do
    if convert(convert(n*k,base,2),`+`)=w then return k fi
  od
end proc:
map(f, [$1..100]); # Robert Israel, Nov 28 2017

Mathematica

Table[SelectFirst[Range[3, 10^4 + 1, 2], SameQ @@ Map[DigitCount[#, 2, 1] &, {n, n #}] &] /. m_ /; MissingQ@ m -> -1, {n, 68}] (* Michael De Vlieger, Nov 28 2017 *)

PARI

A057168(n)=n+bitxor(n, n+n=bitand(n, -n))\n\4+n \\ after M. F. Hasler at A057168
a(n) = n\=2^valuation(n,2); if (n==1, -1, my(w=(n-1)/2); while(1, w=A057168(w); if((2*w+1)%n==0, return((2*w+1)/n))))

Python

def A295827(n):
    if not(n&-n)^n: return -1
    m = n
    while True:
        m = m^((a:=-m&m+1)|(a>>1)) if m&1 else ((m&~(b:=m+(a:=m&-m)))>>a.bit_length())^b
        a, b = divmod(m,n)
        if not b and a&1: return a # Chai Wah Wu, Mar 11 2025

Formula

a(2*n) = a(n) for any n > 0.