Convert to base i - 1

Question

Given \$ i = \sqrt{-1} \$, a base-\$ (i - 1) \$ binary number \$ N \$ with \$ n \$ binary digits from \$ d_{0} \$ to \$ d_{n - 1} \$ satisfies the following equation.

$$ N = d_{n - 1} (i - 1) ^ {n - 1} + d_{n - 2} (i - 1) ^ {n - 2} + \cdots + d_{1} (i - 1) + d_{0} $$

For example, a decimal number \$ 15 \$ is \$ 100011101 \$ in base-\$ (i - 1) \$ since,

$$ (i - 1) ^ {9 - 1} + (i - 1) ^ {5 - 1} + (i - 1) ^ {4 - 1} + (i - 1) ^ {3 - 1} + (i - 1) ^ {1 - 1} $$

$$ = 16 + (-4) + (2 + 2i) + (-2i) + 1 = 15 $$

This is a list of \$ 0 \$ to \$ 9 \$ converted to base-\$ (i - 1) \$.

0         0
1         1
2      1100
3      1101
4 111010000
5 111010001
6 111011100
7 111011101
8 111000000
9 111000001

Given a decimal integer as input, convert the input to a base-\$ (i - 1) \$ binary number, which is then converted again to decimal as output.

For example,

 15 -> 100011101 -> 285
(in)               (out)

You may assume that the input is always \$ \ge 0 \$, and the output will fit in the range of \$ [0, 2^{31})\$.

---

Test cases

0 -> 0
1 -> 1
2 -> 12
3 -> 13
4 -> 464
5 -> 465
6 -> 476
7 -> 477
8 -> 448
9 -> 449
2007 -> 29367517
9831 -> 232644061

Answer 1

Python, 49 bytes (@xnor)

lambda n:3*int(f"{n+a^a:b}",4)&a+a//12
a=2**34//5

Attempt This Online!

Old Python, 51 bytes

lambda n:3*int(f"{n+a^a:b}",4)&a+a//12
a=0xcccccccc

Attempt This Online!

How

In polar coordinates the base is \$b_k = \sqrt 2^k \times e^{\frac{3ki\pi} 4}\$. From this it is easy to verify $$ \begin{align} 1 &= b_0 & 2 &= b_2+b_3 & -4 &= b_4 & -8 &= b_6+b_7 \\ 16 &= b_8 & 32 &= b_{10}+b_{11} & -64 &= b_{12} & &\ldots \end{align} $$

Display 1

Observations:

1. as the size of the base is \$\sqrt 2\$ we need twice the number of 'bits' than in standard binary.

2. Bits 1, 5, 9, ... are never used. This is encoded by the bitmask 0b ... 1101 1101 1101 = 0xdddddddd = a + a//12

3. Standard bits 2,3,6,7,10,11,... occur with a negative sign. This is encoded by the bitmask 0b ... 1100 1100 1100 = 0xcccccccc = a.

We can do the transformation in two steps: from standard base S = 1,2,4,8,16,32,... to 'alternating' A = 1,2,-4,-8,16,32,... and then from A to final base C (for 'complex').

Step 1, S->A:

Because of observation 3 if any of the bits of a is set in the input n (S bits) we need to borrow from the next higher bit. If that bit is also in a or was already set in n we need to borrow from the next higher bit and so on.

One can check that the right cascade of carries is triggered by simply adding n and a.

One can also check that afterwards the not in a A bits are already correct whereas the in a A bits are all wrong. In other words we need to xor with a and that completes step 1.

Step 2, A->C:

For this we just need to look up the bit pairs from display 1. One way of doing this is to repeat all bits and then mask as explained in observation 2.

Answer 2

APL (Dyalog Extended), 17 bytes

Full program. Counting up from ¯1 (exclusive) check if the binary representation interpreted as base ¯1J1 matches the input.

1+⍣(⎕=¯1J1⊥2⊤⊣)¯1

Try it online!

---

APL (Dyalog Unicode), 28 bytes

{0=⍵:0⋄(16×∇-⌊⍵÷4)+12⊥2 2⊤⍵}

Try it online!

The Python implementation on OEIS can be simplified to

$$ f(n) = \begin{cases} 0 & \text{if } n = 0 \\ 16 f(-\lfloor{n \over 4}\rfloor) + [0,1,12,13][n \bmod 4] & \text{otherwise.} \end{cases} $$

12⊥2 2⊤⍵ is a short way of expressing the mod-4 mapping using the base conversion primitives, everything else should map 1-to-1 to the mathematical notation.

Answer 3

JavaScript (Node.js), 33 bytes

Implementation of the formula mentioned in my other answer. Borrowed the 3-n>>2 from a comment by AnttiP.

f=n=>n&&1-(n&3)&13^1|f(3-n>>2)<<4

Try it online!

The (n&3) could be n%4 in Python, but Javascript handles negative dividends differently.

While one could have come up with the magic formula 1-(n&3)&13^1 by hand, I used Lynn's pysearch to find it.

(n&3)	1-(n&3)	1-(n&3)&13	1-(n&3)&13^1
0	1	1	0
1	0	0	1
2	-1	13	12
3	-2	12	13

Answer 4

R, 54 51 bytes

Or R>=4.1, 44 bytes by replacing the word function with a \.

Edit: -3 bytes thanks to Polichinelle.

f=function(n)`if`(n,16*f(-(n%/%4))+n%%4*6-5*n%%2,0)

Try it online!

Based on formula found by @ovs.

Answer 5

Jelly, 8 bytes

Bḅ-ı=ʋ1#

Try it online!

Let \$f(n)\$ be the function described in the question. We use the fact that \$f(n) \ge n\$ for al \$n = 0,1,2,...\$ to save a couple of bytes.

How it works

Bḅ-ı=ʋ1# - Main link. Takes n on the left
     ʋ   - Group the last 4 links into a dyad g(k, n):
B        -   Convert k to binary
 ḅ-ı     -   Convert this to base -ı (-1+1j)
    =    -   Does this equal n?
      1# - Find the first k ≥ n, such that g(k,n) is true

Answer 6

JavaScript, 42 bytes

f=(x,y=0)=>x|y&&x+y&1|2*f(1-y-x>>1,x-y>>1)

Try it online!

f(x,y) produces the base-\$(-1-i)\$ representation of \$ x+iy \$ (which is identical to the base-\$(-1+i)\$ representation for real numbers) reinterpreted as binary, for integers \$x,y\$.

x|y is zero iff x and y are both zero; the && short-circuits to produce zero in that case. Otherwise, x+y&1 gives the ones digit of the base-\$(-1-i)\$ representation of \$ x+iy \$ (since all higher digits contribute an even amount to x+y), and the recursive call produces the rest of the digits.

Answer 7

Factor, 82 78 bytes

:: f ( m -- n ) m [ 0 ] [ 4 / ⌊ neg f 16 * m 4 rem "\0
\r"nth + ] if-zero ;

Try it online!

This is a direct implementation of the recursive formula given by @ovs.

And for posterity, my original answer:

Factor + lists.lazy math.unicode, 85 bytes

[ 0 lfrom [ >bin reverse 49 swap indices C{ -1 1 } swap n^v Σ = ] with lfilter car ]

Try it online!

Explanation

Tries every number starting from 0 until it finds a match, in a brute force way. Slow for the larger inputs, but should theoretically eventually finish.

• 0 lfrom [ ... = ] with lfilter car Apply ... to every number >= 0 until it equals the input. For instance, for input 15 and n=285...

                 ! 15 285
>bin             ! 15 "100011101"
reverse          ! 15 "101110001"
49               ! 15 "101110001" 49
swap             ! 15 49 "101110001"
indices          ! 15 V{ 0 2 3 4 8 }            (get indices of the 1s)
C{ -1 1 }        ! 15 V{ 0 2 3 4 8 } C{ -1 1 }  (i-1)
swap             ! 15 C{ -1 1 } V{ 0 2 3 4 8 }
n^v              ! 15 V{ 1 C{ 0 -2 } C{ 2 2 } -4 16 }
Σ                ! 15 15                        (sum)
=                ! t

Answer 8

x86_64 machine code, 31 bytes (or 27 bytes)

\x81\xc7\xcc\xcc\x00\x00\x81\xf7\xcc\xcc\x00\x00\xb8\x55\x55\x55\x55\xc4\xe2
\x43\xf5\xc0\x8d\x04\x40\x25\xdd\xdd\xdd\xdd\xc3

Try it online!

assembly

add edi, 0xcccc
xor edi, 0xcccc
mov eax, 0x55555555
pdep eax, edi, eax
lea eax, [rax + rax * 2]
and eax, 0xdddddddd
ret

This is a port of the amazing solution from @loopywalt. See his post for a detailed explanation of the algorithm. pdep is an interesting instruction which solves a problem that otherwise needs some sort of loop or a look-up table. It executes in constant time fast on any Intel hardware that supports it, but on AMD chips before Zen3, it was a slow microcoded instruction with variable latency.

The sequence of 6 instructions has a blazing estimated throughput of 2 cycles.

The first two instructions can be modified to save 4 bytes, but it will run a bit slower.

mov ax, 0xcccc
add edi, eax
xor edi, eax

Answer 9

JavaScript (Node.js), 33 32 bytes

f=n=>n&&f(3-n>>2)*16|6*(n&2)|n&1

Try it online!

This is another implementation of the \$n\rightarrow \lfloor{n/4}\rfloor\$ recurrence given in the OEIS. (I saved a byte by changing -(n>>2) to 3-n>>2, as suggested by @AnttiP and others.)

Answer 10

Python 3, ^{65 45} 40 bytes

f=lambda n:n and(n&2)*6+n%2+16*f(3-n>>2)

Try it online!

Saved a whopping 20 25 bytes thanks to AnttiP!!!

Answer 11

Husk, 16 14 bytes

B16mo?I+10εB_4

Try it online!

Converts to base -4, replaces digits 0, 1, 2, 3 with 0, 1, 12 & 13, and converts back from base 16.

Answer 12

Charcoal, 28 bytes

ＮθＷθ«Ｆ1220⊞υ＆θＩκ≔±÷θ⁴θ»Ｉ↨⮌υ²

Try it online! Link is to verbose version of code. Explanation:

Ｎθ

Input n.

Ｗθ«

Repeat until n is zero.

Ｆ1220⊞υ＆θＩκ

Create four more "bits" in the "base 2" representation of n using the digits 0221 bitwise anded with the current value. This results in 0000, 0001, 0220 (i.e. 1100) and 0221 (i.e. 1101) (although the bits are actually pushed in reverse order so that they accumulate correctly).

≔±÷θ⁴θ

Integer divide q by 4 and negate it. (Sadly this is not the same as integer dividing q by -4, otherwise I could use negative base conversion.)

»Ｉ↨⮌υ²

Convert the "bits" from "base 2" and output the result.

Answer 13

Pari/GP, 33 bytes

f(n)=if(n,16*f(n\-4)+n%4*6-n%2*5)

Try it online!

A port of @pajonk's R answer.

Answer 14

05AB1E, 12 bytes

4(вεD2@ì}16β

Port of @DominicVanEssen's Husk answer, so make sure to upvote him as well!

Try it online or verify all test cases.

Explanation:

4(в      # Convert the (implicit) base-10 input-integer to base-(-4) as list
   ε     # Map over each integer in the list
    D    #  Duplicate it
     2@  #  Check if it's >= 2
       ì #  Prepend that 0/1 to the integer
   }16β  # After the map: convert the list from base-16 to a base-10 integer
         # (which is output implicitly as result)

Two equal-bytes alternatives for εD2@ì} could be D2@T*+ or D2@søJ, but I haven't been able to find anything shorter for this.

Answer 15

Python, 48 bytes

f=lambda n:16*f(-(n//4))+6*(n&2)+n%2 if n else 0

This is a recursive function that takes advantage of the fact that because (i-1)^4 = -4, then every 4 bits of the output corresponds to a base -4 number.

f(-(n//4)) makes the recursive call for the base -4 representation of n except the last digit. Unfortunately, the inner parentheses are necessary. Multiplying by 16 shifts left 4 binary digits to make room for the last digit.

6*(n&2)+n%2 is a golfed way to encode the last base -4 digit:

• 00 → 0000
• 01 → 0001
• 10 → 1100
• 11 → 1101

The last bit of the input (n%2 or n&1) corresponds directly to the last digit of the output, while the first bit of the input (n&2), corresponds to either 000 (decimal 0) or 110 (decimal 6). Unfortunately, the parentheses in n&2 are necessary because of operator precedence.

if n else 0 handles the base case of the recursion.

Answer 16

Vyxal, 9 bytes

λb°‹β?=;ṅ

Try it Online!

Port of Jelly.