cp's OEIS Frontend

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.

%I A295827 #24 Mar 11 2025 17:30:48
%S A295827 -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,
%T A295827 21,5,3,21,3,3,-1,993,241,11,57,7,7,5,13,3197,13,9,35,3,39,13,3,21,
%U A295827 169,3,21,39,5,47,3,27,21,5,3,13,3,3,-1,4033,993,491,241
%N 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.
%C A295827 The Hamming weight of a number n is given by A000120(n).
%C A295827 Apparently, a(n) = -1 iff n = 2^k for some k >= 0.
%C A295827 Apparently, a(2^n + 1) = A020515(n) for any n > 1.
%C A295827 a(2^n - 1) = 3 for any n > 1.
%C A295827 a(n) = 3 iff n = A077459(k) for some k > 1.
%C A295827 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)).
%C A295827 For any n > 0, if a(n) > 0 then A292849(a(n)) <= n.
%H A295827 Rémy Sigrist, <a href="/A295827/b295827.txt">Table of n, a(n) for n = 1..8192</a>
%H A295827 Rémy Sigrist, <a href="/A295827/a295827.png">Logarithmic scatterplot of the sequence for n=1..2^17 and a(n) < 10^18</a>
%F A295827 a(2*n) = a(n) for any n > 0.
%e A295827 The first terms, alongside the binary representations of n and of n*a(n), are:
%e A295827   n     a(n)     bin(n)         bin(n*a(n))
%e A295827   --    ----     ------         -----------
%e A295827    1      -1          1                  -1
%e A295827    2      -1         10                 -10
%e A295827    3       3         11                1001
%e A295827    4      -1        100                -100
%e A295827    5      13        101             1000001
%e A295827    6       3        110               10010
%e A295827    7       3        111               10101
%e A295827    8      -1       1000               -1000
%e A295827    9      57       1001          1000000001
%e A295827   10      13       1010            10000010
%e A295827   11      35       1011           110000001
%e A295827   12       3       1100              100100
%e A295827   13      21       1101           100010001
%e A295827   14       3       1110              101010
%e A295827   15       3       1111              101101
%e A295827   16      -1      10000              -10000
%e A295827   17     241      10001       1000000000001
%e A295827   18      57      10010         10000000010
%e A295827   19       7      10011            10000101
%e A295827   20      13      10100           100000100
%p A295827 f:= proc(n) local k,w;
%p A295827   if n = 2^padic:-ordp(n,2) then return -1 fi;
%p A295827   w:= convert(convert(n,base,2),`+`);
%p A295827   for k from 3 by 2 do
%p A295827     if convert(convert(n*k,base,2),`+`)=w then return k fi
%p A295827   od
%p A295827 end proc:
%p A295827 map(f, [$1..100]); # _Robert Israel_, Nov 28 2017
%t A295827 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 *)
%o A295827 (PARI) A057168(n)=n+bitxor(n, n+n=bitand(n, -n))\n\4+n \\ after _M. F. Hasler_ at A057168
%o A295827 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))))
%o A295827 (Python)
%o A295827 def A295827(n):
%o A295827     if not(n&-n)^n: return -1
%o A295827     m = n
%o A295827     while True:
%o A295827         m = m^((a:=-m&m+1)|(a>>1)) if m&1 else ((m&~(b:=m+(a:=m&-m)))>>a.bit_length())^b
%o A295827         a, b = divmod(m,n)
%o A295827         if not b and a&1: return a # _Chai Wah Wu_, Mar 11 2025
%Y A295827 Cf. A000120, A020515, A057168, A077459, A292849.
%K A295827 sign,base
%O A295827 1,3
%A A295827 _Rémy Sigrist_, Nov 28 2017