login
A340669
Permutation of the nonnegative integers formed by negation in complex base i-1.
3
0, 29, 58, 7, 116, 25, 14, 3, 232, 21, 50, 239, 28, 17, 6, 235, 464, 13, 42, 471, 100, 9, 478, 467, 56, 5, 34, 63, 12, 1, 470, 59, 928, 957, 26, 935, 84, 953, 942, 931, 200, 949, 18, 207, 956, 945, 934, 203, 112, 941, 10, 119, 68, 937, 126, 115, 24, 933, 2, 31
OFFSET
0,2
COMMENTS
Complex base i-1 of Khmelnik and Penney uses an integer n>=0 to represent a complex integer z(n) = A318438(n) + A318439(n)*i. a(n) is the negation of z in this representation, so that z(a(n)) = -z(n). Every z is uniquely represented, so this is a self-inverse permutation.
Khmelnik's table 4 is carries applied to z which become states and transitions by bits of n and certain 0<->1 bit flips in n. The result is the transformation in the formulas below. Bit flips may extend into 0-bits above the most significant bit of n causing the bit length of a(n) to be greater than the bit length of n.
LINKS
Solomon I. Khmelnik, Specialized Digital Computer for Operations with Complex Numbers (in Russian), Questions of Radio Electronics, volume 12, number 2, 1964.
Kevin Ryde, Iterations of the Dragon Curve, see index MinusNeg.
Andrey Zabolotskiy, English translation of theorems from Khmelnik, Seqfan mailing list, September 2016.
FORMULA
a(n) is formed by transforming n as follows. Write n in binary with four high 0-bits and consider bits from least to most significant. At a 01 pair (high 0, low 1), apply an 0<->1 flip to three bits immediately above this pair. At a 11 pair, flip one bit immediately above this pair. Repeat, each time seeking the next higher 01 or 11 pair above the bits just flipped.
EXAMPLE
For n=1506, location z(1506) = 11-35*i. Its negation is -(11-35*i) = z(29914) so a(1506) = 29914. And being self-inverse conversely a(29914) = 1506.
In terms of bit flips, in the following "^^" is each 01 or 11 and F marks the bits flipped above them.
n = 1506 = binary 00001 0 1 11 100 01 0
FFF^^ F ^^ FFF ^^
a(n) = 29914 = binary 11101 0 0 11 011 01 0
PROG
(PARI) { a(n) = for(i=0, if(n, logint(n, 2)),
if(bittest(n, i),
if(bittest(n, i+1), n=bitxor(n, 4<<i); i+=2,
n=bitxor(n, 28<<i); i+=4))); n; }
CROSSREFS
KEYWORD
nonn,base
AUTHOR
Kevin Ryde, Jan 15 2021
STATUS
approved