[seqfan] Re: Injectivity of a(n) = n^2 - XOR(n^2, n)

[hv at crypt.org]

Let L(n) be the index of the least significant bit set in n, so that
L(n) = k <=> n == 2^k (mod 2^{k+1}). I assume negative integers are
represented in twos-complement form, so that L(-1) = L(1) = 0, and
that L(0) is set to some unique value such as -1.

We have XOR(a, b) = a + b - 2 AND(a, b), so a(n) = -n + 2 AND(n^2, n).

Informally: if L(AND(n^2, n)) = k, then there could potentially be a
collision at n' = n + 2^{k+1} if L(AND(n'^2, n')) > k, but n and n' are
identical for the first k bits, and so are n^2 and n'^2, so that
collision does not exist.

I conjecture that L(XOR(n, n')) = L(XOR(a(n), a(n'))) for all n, n' - ie
that the first bit at which n and n' differ is also the first bit at
which a(n) and a(n') differ - which would be ample to show injectivity
(and extend it also to negative n).

Hugo

David Radcliffe <dradcliffe at gmail.com> wrote:
:Sequence A174375 <https://oeis.org/A174375> is defined by the equation a(n)
:= n^2 - XOR(n^2, n), where XOR is bitwise exclusive OR. (In other words,
:XOR is binary addition without carries.)
:
:Computer experiments suggest that this sequence is injective. In fact,
:there are no repeated values among the first 10^8 terms. This is quite
:surprising to me, because it doesn't "look" injective -- the graph
:resembles a Sierpinski triangle on its side.
:
:Can anyone prove that this sequence is injective?
:
:- David Radcliffe
:
:--
:Seqfan Mailing list - http://list.seqfan.eu/