25
\$\begingroup\$

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
\$\endgroup\$
3
  • 7
    \$\begingroup\$ This is OEIS A066321. \$\endgroup\$
    – pxeger
    Feb 20, 2022 at 10:43
  • 1
    \$\begingroup\$ I think the last case should be 232644061, for your number I get \$-2686+34477i\$ \$\endgroup\$
    – ovs
    Feb 20, 2022 at 11:37
  • \$\begingroup\$ @ovs You're right, 1567356735 was the octal representation.. \$\endgroup\$
    – xiver77
    Feb 20, 2022 at 11:54

16 Answers 16

9
\$\begingroup\$

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.

\$\endgroup\$
9
  • 1
    \$\begingroup\$ The constant a seems to be 2**34//5 \$\endgroup\$
    – xnor
    Feb 20, 2022 at 18:00
  • \$\begingroup\$ It took me so long to understand what's going on, but wonderful idea and wonderful solution! I didn't even imagine this could be done in a non-iterative/recursive way. \$\endgroup\$
    – xiver77
    Feb 22, 2022 at 4:43
  • \$\begingroup\$ Okay, I realized int(f"{n+a^a:b}",4) is iterative by nature, although not apparent in code. At least I couldn't find a non-iterative solution for that function. \$\endgroup\$
    – xiver77
    Feb 22, 2022 at 5:20
  • \$\begingroup\$ @xiver77 Thanks! I'm myself a bit proud of n+a^a and how the key recursive/iterative mechanic is "done in hardware" by the bubbling up of carry bits.At the same time I'm annoyed that the comparatively easy rest (repeat each bit and mask) takes so many bytes. \$\endgroup\$
    – loopy walt
    Feb 22, 2022 at 7:27
  • 1
    \$\begingroup\$ I ported your answer in x86_64 machine code, and it has an impressive estimated throughput of only 2 cycles. I wish there were some practical use of this transformation. \$\endgroup\$
    – xiver77
    Feb 22, 2022 at 10:56
8
\$\begingroup\$

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.

\$\endgroup\$
7
\$\begingroup\$

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
\$\endgroup\$
6
\$\begingroup\$

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.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ -3 bytes: +n%%4%/%2*12+n%%2 -> +n%%4*6-5*n%%2 \$\endgroup\$ Feb 20, 2022 at 20:40
  • \$\begingroup\$ @Polichinelle, nice one - thanks! \$\endgroup\$
    – pajonk
    Feb 20, 2022 at 21:03
5
\$\begingroup\$

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
\$\endgroup\$
4
\$\begingroup\$

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.

\$\endgroup\$
4
\$\begingroup\$

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
\$\endgroup\$
4
+100
\$\begingroup\$

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
\$\endgroup\$
8
  • \$\begingroup\$ Cool stuff! I was wondering whether using the clmul instruction instead can gain anything as it avoids creating the 0x55555555 mask? I don't understand assembly well enough to make a guess. \$\endgroup\$
    – loopy walt
    Feb 22, 2022 at 12:04
  • \$\begingroup\$ @loopywalt clmul is a slower instruction that pdep. A latency of 6 vs 3 means it takes 6 vs 3 cycles to get the result, so pdep with 3 latency produces the result twice as fast. \$\endgroup\$
    – xiver77
    Feb 22, 2022 at 12:19
  • \$\begingroup\$ Also, clmul operates on xmm registers, so you have to move value from a general purpose register to a xmm register and back, making it even slower. \$\endgroup\$
    – xiver77
    Feb 22, 2022 at 12:19
  • \$\begingroup\$ @loopywalt Thank you for the bounty! \$\endgroup\$
    – xiver77
    Mar 9, 2022 at 8:05
  • \$\begingroup\$ You are welcome. And once more: Well done! \$\endgroup\$
    – loopy walt
    Mar 9, 2022 at 8:09
3
\$\begingroup\$

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.)

\$\endgroup\$
3
\$\begingroup\$

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!!!

\$\endgroup\$
6
  • \$\begingroup\$ 45 bytes using ovs's formula \$\endgroup\$
    – AnttiP
    Feb 20, 2022 at 14:24
  • \$\begingroup\$ @AnttiP the 3-n>>2 is nice, I had n//4*-1 which is a byte longer in Python 3. But the [...][n%4] can be golfed quite a bit, 40 bytes is possible \$\endgroup\$
    – ovs
    Feb 20, 2022 at 15:25
  • \$\begingroup\$ @AnttiP Very nice - thanks! :D \$\endgroup\$
    – Noodle9
    Feb 20, 2022 at 15:37
  • \$\begingroup\$ @ovs Are these the 40 bytes you're talking about? \$\endgroup\$
    – AnttiP
    Feb 20, 2022 at 17:45
  • \$\begingroup\$ @AnttiP Fantastic - thanks! :D \$\endgroup\$
    – Noodle9
    Feb 20, 2022 at 19:49
3
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

Charcoal, 28 bytes

NθWθ«F1220⊞υ&θIκ≔±÷θ⁴θ»I↨⮌υ²

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

Nθ

Input n.

Wθ«

Repeat until n is zero.

F1220⊞υ&θIκ

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.)

»I↨⮌υ²

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

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

Vyxal, 9 bytes

λb°‹β?=;ṅ

Try it Online!

Port of Jelly.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.