cp's OEIS Frontend

A340669 Permutation of the nonnegative integers formed by negation in complex base i-1.

%I A340669 #24 Oct 20 2024 11:41:25
%S A340669 0,29,58,7,116,25,14,3,232,21,50,239,28,17,6,235,464,13,42,471,100,9,
%T A340669 478,467,56,5,34,63,12,1,470,59,928,957,26,935,84,953,942,931,200,949,
%U A340669 18,207,956,945,934,203,112,941,10,119,68,937,126,115,24,933,2,31
%N A340669 Permutation of the nonnegative integers formed by negation in complex base i-1.
%C A340669 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.
%C A340669 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.
%H A340669 Kevin Ryde, <a href="/A340669/b340669.txt">Table of n, a(n) for n = 0..8192</a>
%H A340669 Joerg Arndt, <a href="https://jjj.de/fxt/demo/bits/index.html#radix-m1pi">The fxt demos: bit wizardry. radix(-1+i)</a>
%H A340669 Solomon I. Khmelnik, <a href="http://lib.izdatelstwo.com/Papers2/s4.djvu">Specialized Digital Computer for Operations with Complex Numbers</a> (in Russian), Questions of Radio Electronics, volume 12, number 2, 1964.
%H A340669 Kevin Ryde, <a href="http://user42.tuxfamily.org/dragon/index.html">Iterations of the Dragon Curve</a>, see index MinusNeg.
%H A340669 Andrey Zabolotskiy, <a href="/A340669/a340669.txt">English translation of theorems from Khmelnik</a>, Seqfan mailing list, September 2016.
%H A340669 Andrey Zabolotskiy, <a href="https://pastebin.com/raw/uHJW13zf">Python Code by bit flips or conversion</a> and <a href="https://pastebin.com/raw/aCnECyj8">Python Code by Khmelnik's Pi and Beta</a>, September 2016.
%F A340669 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.
%e A340669 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.
%e A340669 In terms of bit flips, in the following "^^" is each 01 or 11 and F marks the bits flipped above them.
%e A340669   n    =  1506 = binary  00001 0 1 11 100 01 0
%e A340669                          FFF^^   F ^^ FFF ^^
%e A340669   a(n) = 29914 = binary  11101 0 0 11 011 01 0
%o A340669 (PARI) { a(n) = for(i=0,if(n,logint(n,2)),
%o A340669   if(bittest(n,i),
%o A340669     if(bittest(n,i+1), n=bitxor(n,4<<i); i+=2,
%o A340669                        n=bitxor(n,28<<i); i+=4))); n; }
%Y A340669 Cf. A318438, A318439, A340670.
%K A340669 nonn,base
%O A340669 0,2
%A A340669 _Kevin Ryde_, Jan 15 2021