The dragon Curve sequence

Question

The dragon curve sequence (or the regular paper folding sequence) is a binary sequence. a(n) is given by negation of the bit left of the least significant 1 of n. For example to calculate a(2136) we first convert to binary:

100001011000

We find our least significant bit

100001011000
        ^

Take the bit to its left

100001011000
       ^

And return its negation

0

Task

Given a positive integer as input, output a(n). (You may output by integer or by boolean). You should aim to make your code as small as possible as measured by bytes.

Test Cases

Here are the first 100 entries in order

1 1 0 1 1 0 0 1 1 1 0 0 1 0 0 1 1 1 0 1 1 0 0 0 1 1 0 0 1 0 0 1 1 1 0 1 1 0 0 1 1 1 0 0 1 0 0 0 1 1 0 1 1 0 0 0 1 1 0 0 1 0 0 1 1 1 0 1 1 0 0 1 1 1 0 0 1 0 0 1 1 1 0 1 1 0 0 0 1 1 0 0 1 0 0 0 1 1 0 1

Answer 1

Mathematica 25 Bytes

1/2+JacobiSymbol[-1,#]/2&

Other ways of doing this:

56 bytes

(v:=1-IntegerDigits[#,2,i][[1]];For[i=1,v>0,i++];i++;v)&

58 bytes

1-Nest[Join[#,{0},Reverse[1-#]]&,{0},Floor@Log[2,#]][[#]]&

Answer 2

Python 3, 22 21 bytes

1 byte thanks to ETHproductions.

lambda n:n&2*(n&-n)<1

Try it online!

Bitwise arithmetic ftw.

Answer 3

Retina, 38 34 29 bytes

\d+
$*
+`^(1+)\1$|1111
$1
^1$

Try it online!

Martin and Leaky essentially came up with this idea, for 5 more bytes off!

Converts the input to unary, and then progressively divides the number by 2. Once it can't do that evenly anymore (i.e. the number is odd) it then removes patches of 4 from the input, computing the result of the last operation mod 4. Finally, this checks if the result was 1, which means that digit to the left of the least significant 1 bit was zero. If that is true, the final result is 1, otherwise it is zero.

Answer 4

Jelly, 5 bytes

&N&HṆ

Try it online!

How it works

&N&HṆ  Main link. Argument: n

 N     Negate; yield -n.
&      Bitwise AND; compute n&-n.
       This yields the highest power of 2 that divides n evenly.
   H   Halve; yield n/2.
  &    Bitwise AND; compute n&-n&n/2. This rounds n/2 down if n is odd.
    Ṇ  Take the logical NOT of the result.

Answer 5

Alice, 8 bytes

I2z1xnO@

Try it online!

Takes input as the code point of a Unicode character and outputs the result as a 0x00 or 0x01 byte accordingly.

For testability, here is a decimal I/O version at 12 bytes which uses the exact same algorithm (only I/O is different):

/o
\i@/2z1xn

Try it online!

If Alice was a golfing language and didn't require explicit I/O and program termination, this would clock in at a mere 5 bytes (2z1xn) beating both 05AB1E and Jelly.

Explanation

I    Read input.
2z   Drop all factors of 2 from the input, i.e. divide it by 2 as long
     as its even. This shifts the binary representation to the right
     until there are no more trailing zeros.
1x   Extract the second-least significant bit.
n    Negate it.
O    Output it.
@    Terminate the program.

Answer 6

05AB1E, 6 bytes

b0ܨθ≠

Try it online!

Answer 7

Wise, 28 20 16 bytes

::-~^~-&:[?>]~-^

Try it online!

Explanation

This is a port of Leaky Nun's Python answer. It unfortunately does not work on TIO because TIO's version of the interpreter is a bit outdated.

We start by making 3 copies of our input with ::, we then decrement the top copy by 1. This will flip all the bits up until the first 1. We then xor this with another copy of our input. Since all of the bits up until the first 1 on our input have been flipped this will result in all those bits being 1 on the result. If we then add one ~- to the result we will get a single 1 at the place to the left of our least significant 1. We AND this with the input to get that bit from the input. Now we will have 0 iff that bit was off and a power of 2 iff that bit was on, we can change this into a single 1 or 0 with :[?>]. Once this is done we need only negate the bit ~-^ and we are done.

Answer 8

Haskell, 45 43 39 bytes

6 bytes saved thanks to nimi

f x|d<-div x 2=[f d,mod(1+d)2]!!mod x 2

Try it online!

Answer 9

x86 Machine Code, 17 16 15 bytes:

Assumes an ABI where parameters are pushed on the stack and the return value is in the AL register.

8B 44 24 04 0F BC C8 41 0F BB C8 0F 93 C0 C3

This is disassembled as follows:

_dragoncurve:
  00000000: 8B 44 24 04        mov         eax,dword ptr [esp+4]
  00000004: 0F BC C8           bsf         ecx,eax
  00000007: 41                 inc         ecx
  00000008: 0F BB C8           btc         eax,ecx
  0000000B: 0F 93 C0           setae       al
  0000000E: C3                 ret

Answer 10

Python 2, 19 bytes

lambda n:n&-n&n/2<1

Try it online!

Answer 11

JavaScript (ES6), 17 14 bytes

f=
n=>!(n&-n&n/2)

<input type=number min=0 oninput=o.textContent=f(this.value)><pre id=o>

Edit: Saved 3 bytes by porting @Dennis's answer once I noticed that boolean output was acceptable.

Answer 12

C (gcc), 20 bytes

f(n){n=!(n&-n&n/2);}

Try it online!

Answer 13

INTERCAL, 50 bytes

DOWRITEIN.1DO.1<-!?1~.1'~#1DOREADOUT.1PLEASEGIVEUP

INTERCALs unary operators are quite suitable for this, so I decided to write my first post.

DO WRITE IN .1
DO .1 <- !?1~.1'~#1
DO READ OUT .1
PLEASE GIVE UP

Answer 14

Haskell, 33 bytes

g~(a:b:c)=1:a:0:b:g c
d=g d
(d!!)

Try it online!

Uses 0-indexing.

Answer 15

Jelly, 7 6 bytes

1 byte thanks to Erik the Outgolfer.

Bt0ṖṪṆ

Try it online!

Longer programs

• 7 bytes: Họ¡2&2Ị
• 7 bytes: Bt0ṫ-ḄỊ

Answer 16

Octave, 34 bytes

@(x)~(k=[de2bi(x),0])(find(k,1)+1)

Try it online!

Explanation:

@(x)                               % Anonymous function taking a decimal number as input
    ~....                          % Negate whatever comes next
     (   de2bi(x)   )              % Convert x to a binary array that's conveniently 
                                   % ordered with the least significant bits first
        [de2bi(x),0]               % Append a zero to the end, to avoid out of bound index
     (k=[de2bi(x),0])              % Store the vector as a variable 'k'
                     (find(k,1)    % Find the first '1' in k (the least significant 1-bit)
                               +1  % Add 1 to the index to get the next bit
     (k=[de2bi(x),0])(find(k,1)+1) % Use as index to the vector k to get the correct bit

Answer 17

,,,, 10 9 bytes

::0-&2*&¬

Explanation

Take input as 3 for example.

::0-&2*&1≥
               implicitly push command line argument       [3]
::             duplicate twice                             [3, 3, 3]
  0            push 0 on to the stack                      [3, 3, 3, 0]
   -           pop 0 and 3 and push 0 - 3                  [3, 3, -3]
    &          pop -3 and 3 and push -3 & 3 (bitwise AND)  [3, 1]
     2         push 2 on to the stack                      [3, 1, 2]
      *        pop 2 and 1 and push 2 * 1                  [3, 2]
       &       pop 2 and 3 and push 2 & 3                  [2]
        ¬      pop 2 and push ¬ 2 (logical NOT)            [0]
               implicit output                             []

Answer 18

Haskell, 26 bytes

f n=even$div n$2*gcd(2^n)n

Try it online!

Boolean output.

Answer 19

MATL, 11 10 bytes

t4*YF1)Z.~

Try it online! Or see the first 100 outputs.

Explanation

t    % Implicit input. Duplicate
4*   % Multiply by 4. This ensures that the input is a multiple of 2, and
     % takes into account that bit positions are 1 based
YF   % Exponents of prime factorization
1)   % Get first exponent, which is that of factor 2
Z.   % Get bit of input at that (1-based) position
~    % Negate. Implicit display

Answer 20

Submission:

Python 2, 41 39 bytes

x=input()
while~-x&1:x/=2
print 1-x/2%2

Try it online!

-2 bytes thanks to FryAmTheEggman

Initial Solution:

Python 2, 43 bytes

lambda x:1-int(bin(x)[bin(x).rfind('1')-1])

Try it online!

Answer 21

Befunge-98, 19 bytes

&#;:2%\2/\#;_;@.!%2

Try it online!

&#                       Initial input: Read a number an skip the next command
  ;:2%\2/\#;_;           Main loop: (Direction: East)
   :2%                    Duplicate the current number and read the last bit
      \2/                 Swap the first two items on stack (last bit and number)
                          and divide the number by two => remove last bit
         \                swap last bit and number again
          #;_;            If the last bit is 0, keep going East and jump to the beginning of the loop
                          If the last bit is 1, turn West and jump to the beginning of the loop, but in a different direction.
&#;           @.!%2      End: (Direction: West)
&#                        Jump over the input, wrap around
                 %2       Take the number mod 2 => read the last bit
               .!         Negate the bit and print as a number
              @          Terminate

Answer 22

Pari/GP, 20 bytes

n->kronecker(-1,n)>0

Using the Kronecker symbol.

Try it online!

Answer 23

SCALA, 99(78?) chars, 99(78?) bytes

if(i==0)print(1)else
print(if(('0'+i.toBinaryString).reverse.dropWhile(x=>x=='0')(1)=='1')0 else 1)

where i is the input.

As you can see, I do save 21 bytes if I don't take care of the zero (as the author did in his test case) :

print(if(('0'+i.toBinaryString).reverse.dropWhile(x=>x=='0')(1)=='1')0 else 1)

This is my first codegolf so I hope I did well :)

Try it online! Though it's quite long to compute lol.

Answer 24

C (gcc), 35 31 bytes

f(x){return~x&1?f(x/2):!(x&2);}

Switched to a recursive implementation. Try it online!

Answer 25

Java 8, 17 bytes

n->(n&2*(n&-n))<1

Straightforward port of LeakyNun's Python 3 answer. I'm not familiar enough with bitwise operations and operator precedence to see a shorter solution; maybe there's a way to avoid the extra parentehesis?

Answer 26

Japt, 10 8 9 bytes

!+¢g¢a1 É

Try it online!

Explanation

!+¢   g    a1 É
!+Us2 gUs2 a1 -1 # Implicit input (U) as number
!+               # Return the boolean NOT of
      g          #   the character at index
       Us2       #     the input converted to binary
           a1    #     the index of its last 1
              -1 #     minus 1
      g          #   in string
  Us2            #     the input converted to binary

Answer 27

JavaScript (ES6), 53 34 bytes

a=>eval("for(;~a&1;a/=2);~a>>1&1")

Answer 28

PHP>=7.1, 32 bytes

<?=1^!trim(decbin($argn),0)[-2];

PHP Sandbox Online

PHP, 40 bytes

for($i=$argn;$i%2<1;)$i/=2;echo$i/2%2^1;

Try it online!

PHP, 41 bytes

<?=1^preg_match("#110*$#",decbin($argn));

Try it online!

Answer 29

Common Lisp, 56 bytes

(defun f(n)(if(oddp n)(- 1(mod #1=(ash n -1)2))(f #1#)))

Try it online!

Answer 30

Chip, 93 bytes

HZABCDEFG,t
 ))))))))^~S
H\\\\\\\/v~a
G\\\\\\/v'
F\\\\\/v'
E\\\\/v'
D\\\/v'
C\\/v'
B\/v'
A/-'

Takes input as little endian bytes. (The TIO has a bit of python that does this for you). Gives output as either 0x0 or 0x1. (The TIO uses xxd to inspect the value).

Try it online!

How do it this?

Chip looks at input one byte at a time, so handling multibyte input adds some bulk, but not near as much as I had feared.

Let's go into it:

HZABCDEFG

These are HZ, high bit of the previous byte (if there was one), and A-G, the seven lower bits of the current byte. These are used to locate the lowest set bit of the number.

        ,t
))))))))^~S

When the lowest set bit is found, we have a few things to do. This first chunk says "if we have a set bit (the )'s), then stop Suppressing the output, and terminate after we print the answer.

H\\\\\\\/v~a
G\\\\\\/v'
...
A/-'

Whichever bit of the current byte (A-H) is only preceded by a bunch of zeroes then a one (\ and /: these look at the bits directly north of them; we can trust that all previous bits were zero) is passed through to the wires on the right (v, ', ...), then whichever value it is is inverted and given as the low bit of output (~a).