A379015 a(n) is the reversed non-adjacent form (NAF) representation of n.

0, 1, 1, -3, 1, 5, -3, -7, 1, 9, 5, -19, -3, 13, -7, -15, 1, 17, 9, -11, 5, 21, -19, -35, -3, 29, 13, -39, -7, 25, -15, -31, 1, 33, 17, -23, 9, 41, -11, -27, 5, 37, 21, -83, -19, 45, -35, -67, -3, 61, 29, -51, 13, 77, -39, -71, -7, 57, 25, -79, -15, 49, -31, -63

Offset: 0

Author

Darío Clavijo, Dec 13 2024

Keywords

• sign
• base

Comments

Fixed points exist when the non-adjacent form is palindromic.

Examples

			For n=7 a(7) = -7 because:
7 to NAF encoding read from least to most significant bit: [-1, 0, 0, 1]
Reversed: [1, 0, 0, -1]
NAF to integer: -7.
		

Links

• Rémy Sigrist, Table of n, a(n) for n = 0..10000
• Wikipedia, Non-adjacent form.

Crossrefs

Cf. A000079, A004767, A016813, A091067, A091072, A334913.

Programs

Mathematica

a[n_]:=Module[{E=n,r=0},While[E>0,If[OddQ[E],Module[{Zi=2-Mod[E,4]},E-=Zi;r+=Zi;]];E=Floor[E/2];r*=2;];Floor[r/2]];Table[a[n],{n,0,63}] (* James C. McMahon, Dec 26 2024 *)

PARI

a(n) = { my (r = 0, d); while (n, if (n%2, d = 2 - (n % 4); r += d; n -= d;); r *= 2; n \= 2;); return (r \ 2); } \\ Rémy Sigrist, Dec 28 2024

Python

def a(n):
    E, r = n, 0
    while E:
        if E & 1:
            Zi = 2 - (E & 3)
            E -= Zi
            r += Zi
        E >>= 1
        r <<= 1
    return r >> 1
print([a(n) for n in range(0,64)])

Formula

a(2^k) = 1.

a(A091072(n)) > 0 iff a(n) is in A016813.

a(A091067(n)) < 0 iff abs(a(n)) is in A004767.

Extensions

a(0) = 0 prepended by Rémy Sigrist, Dec 28 2024