# The dragon Curve sequence

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


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

• someway related
– nimi
Jun 28, 2017 at 15:30
• The least significant bit of 100001011000 is a 0. Do you mean the least significant 1? Jun 28, 2017 at 15:30

## 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,#]][[#]]&

• Wow! A mathematica answer and it's not builtin only. Have an upvote! Jun 28, 2017 at 20:21
• The only thing that could make this answer even better is an explanation for why and how it works. :P Jun 29, 2017 at 9:10
• @MartinEnder arxiv.org/pdf/1408.5770.pdf See the remark after Example 13. Jun 29, 2017 at 9:22

# Python 3, 22 21 bytes

1 byte thanks to ETHproductions.

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


Try it online!

Bitwise arithmetic ftw.

• "You may output by integer or by boolean" so I guess you don't need the 0+(...)? Jun 28, 2017 at 15:51
• The order of operations here is really confusing me. Could n&1 be put in parentheses? Or is is 1+(n^~-n)<1 that can be put in parentheses? Or is it 1+(n^~-n)... Jun 28, 2017 at 15:51
• oh god what. this is what I was looking for :o nice! Jun 28, 2017 at 15:51
• & has the lowest precedence, so it is 1+(n^~-n) Jun 28, 2017 at 15:51
• Ah, found the precedence table. Now it all makes sense :P Jun 28, 2017 at 15:54

# Retina, 3834 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.

• 31 bytes (should I post it myself?) Jun 28, 2017 at 15:55
• I found a way to avoid the full binary conversion and instead just divide out the factors of 2 and check for equality with 1 (mod 4): tio.run/##K0otycxL/… Jun 28, 2017 at 15:55
• @MartinEnder essentially my algorithm... with 2 bytes off Jun 28, 2017 at 15:55
• @LeakyNun Oh yeah, they're both the same idea. Great minds and stuff... ;) Jun 28, 2017 at 15:56
• I'll edit that in, but if either of you wants to post it I'll revert, as I probably wouldn't have thought of that myself ;) Jun 28, 2017 at 15:59

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


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


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


Try it online!

Uses 0-indexing.

• What does the ~ do in this context? I get that it is a lazy match, but why do you need a lazy match? Jul 17, 2017 at 14:28

# APL (Dyalog Unicode), 24 23 21 bytes

{~⍵[¯1+⌈/⍸⍵]}0,2⊥⍣¯1⊢


Try it online!

Bitwise operations are a bit long in APL, so I went with the method in the question.

-1 byte from dzaima.

## Explanation

{~⍵[¯1+⌈/⍸⍵]}0,2⊥⍣¯1⊢ input n taken on the right
2⊥⍣¯1⊢ n in binary
0,       with 0 prepended in case the LSB is at first index
{           }         do the following to the array ⍵:
⍸⍵           get indices of 1's in ⍵
⌈/             find maximum index
¯1+               subtract 1 from it to get the previous index
⍵[       ]          Find the element at that index in ⍵
~                    bitwise NOT

• 2(⊥⍣¯1)⊢ -> 11⎕dr⊢ and maybe rm 0,
– ngn
Sep 17, 2020 at 18:26
• @ngn 11⎕DR doesn't work because the chunks of 8 bits are in LSByte-first order, which is quite different from the result of 2⊥⍣¯1. Sep 18, 2020 at 0:35
• @Bubbler right, ⎕dr here requires an assumption that the machine is big-endian
– ngn
Sep 18, 2020 at 1:26

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


Try it online!

Boolean output.

32 bytes

(d!!)
d=d%1
~(h:t)%k=k:h:t%(1-k)


Try it online!

Saves one byte off of Anders Kaseorg's recursive-list solution.

# 05AB1E, 6 bytes

b0Ü¨θ≠


Try it online!

# Wise, 2820 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.

# Python 2, 19 bytes

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


Try it online!

6 bytes saved thanks to nimi

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


Try it online!

• You can use div instead of quot.
– nimi
Jun 28, 2017 at 16:48
• Even better: divMod: f x|(d,m)<-divMod x 2=[mod(1+d)2,f d]!!m
– nimi
Jun 28, 2017 at 16:54
• @nimi I don't even understand how that works. You should probably just post it yourself. Jun 28, 2017 at 16:55
• It's still the same algorithm, but just a different way to pick the branch (recursively call f again vs. base case), so feel free to edit it in. |(d,m)<-divMod x 2 is a pattern guard to bind d to div x 2 and m to mod x 2. We use m to index the two element list [...,...]!!m. In case of m==0 we return mod(1+d)2 and in case of m==1 f d.
– nimi
Jun 28, 2017 at 17:07
• Oh, sorry, you have to flip the list elements: [f d,mod(1+d)2]. Try it online!.
– nimi
Jun 28, 2017 at 17:44

# x86 Machine Code, 1716 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

• @PeterTaylor I'm counting the size of the CPU instruction in bytes for my answer; that's a pretty common practice on PPCG for assembly answers. Jun 28, 2017 at 16:30
• I couldn't say how common it is, but it is definitely wrong Jun 28, 2017 at 16:43
• It isn't just pedantic, it's also meaningless. There is no distinction between "machine code" and "assembly code" as far as a computer is concerned. The difference is merely one of interpretation. We assign mnemonics to machine code bytes to make them easier for humans to read. In other words, we ungolf the bytes to make them easier to understand. Jun 28, 2017 at 17:27
• That is irrelevant, @Peter. The assembly code is just a human-readable translation of machine code. They are exactly the same language, just in two different forms/representations. It's no different than TI BASIC, where it is commonly accepted that we count tokens, instead of character bytes, because this is how the system stores them internally. The same would be true with assembly language: the instruction mnemonics are not stored as individual characters, but rather represented as bytes of equivalent machine code. Jun 28, 2017 at 18:10
• Besides, practically speaking, why would anyone ever enter expanded assembly language mnemonics in a code-golf competition, when they could translate them into 100% equivalent machine code, where the entry is guaranteed to be shorter for free? That alone makes a distinction between the two pointless, if not entirely absurd. Jun 28, 2017 at 18:12

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

# C (gcc), 20 bytes

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


Try it online!

• This doesn't actually "work"; you are relying on a quirk of the code generator for one particular version of the compiler targeting one particular architecture, where intermediate calculations are done in the same register that is used for return values. Enabling any type of optimization, changing the target architecture, or using a different version of GCC will break this. You might as well just say "the garbage on my stack contains the right output when there is a full moon on October 13th". Jun 29, 2017 at 10:22
• While everything you say is true and code like this never be used in production code, we define languages by their implementations for the purposes of code golf. Without additional flags, this works in all recent versions of gcc and tcc, and it only has to work in one version to be considered valid. Jun 29, 2017 at 14:41
• "we define languages by their implementations for the purposes of code golf" Wait, what? So every compiler flag and every version of GCC defines a different language? You realize that's crazy, right? The C language standard is what defines the language. Jun 30, 2017 at 10:31
• Not here. If there was a C standard but no implementation, we wouldn't even consider it a language. As I said before, the compiler defines the language. As a result, relying on undefined behavior is allowed. A different set of flags isn't considered a different language, but unless you add them to your byte count, all answers use standard compilation flags. Jun 30, 2017 at 15:18
• Wow. That's nuts. I mean, I could understand if you were saying that implementation-defined behavior is allowed, but undefined behavior is not defined by the implementation. It is literally undefined. The implementation is allowed to do random things each time. And this notion of "standard compilation flags" is something that you just invented. My standard compilation flags include several that break your code. And I hardly think the optimizer is non-standard. Well, clearly this site is not for me. Jun 30, 2017 at 15:22

# 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


# Jelly, 7 6 bytes

1 byte thanks to Erik the Outgolfer.

Bt0ṖṪṆ


Try it online!

## Longer programs

• Hmm...well, you can just do ṖṪṆ (as my deleted answer) instead of ṫ-ḄỊ. Jun 28, 2017 at 15:31
• Another one for your 7-byte list: BUḌDḊḢ¬ Jun 28, 2017 at 16:26

# 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


# ,,,, 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                             []


# 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

• How come I never heard of de2bi... :O Jun 29, 2017 at 20:53

# tinylisp, 71 bytes

(load library
(q((x)(not(nth(c 0(to-base 2 x))(last-index(to-base 2 x)1


Anonymous function that takes a number and returns 0 or 1. Try it online!

### Ungolfed/explanation

Surprisingly, tinylisp's library lets us implement the spec almost directly.

(load library)

(lambda (x)                   ; Anonymous function with one argument
(not                        ; Logical negation of
(nth                      ; The element of _ at index __:
(cons 0 (to-base 2 x))  ; The binary representation of x with a 0 prepended
(last-index             ; Index of the last occurrence
(to-base 2 x)         ; in the binary representation of x
1)))))                ; of 1


Prepending a 0 handles the "previous bit" logic by shifting all elements down one spot, and it keeps us from walking off the left end of the list when there is only a single 1 bit.

# 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

# Python 2, 43 bytes

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


Try it online!

• So which one is your submission? Jun 28, 2017 at 15:44
• @LeakyNun The first one because it's shorter; the second one was my original submission. Should I post them separately? Jun 28, 2017 at 15:46
• ~-x&1 works for the while condition instead, I think. Jun 28, 2017 at 15:47
• (I forget the username); I rejected your edit because edits to golf other people's code is not advised on PPCG. You can post suggestions (btw, thanks @FryAmTheEggman), but please do not make golfing edits. Thanks! Jun 28, 2017 at 15:49
• @StewieGriffin Ah yes, thanks. Unfortunately I can't ping the user because the edit was rejected. Jun 28, 2017 at 15:58

# 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


# Pari/GP, 20 bytes

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


Using the Kronecker symbol.

Try it online!

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

• Welcome to the site! Jun 28, 2017 at 18:48

# C (gcc), 35 31 bytes

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


Switched to a recursive implementation. Try it online!

# 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?

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

# APL (Dyalog Extended), 12 bytes

1≠¯1⊥2↑⍸∘⌽∘⊤


Try it online!

Took the idea of using ⍸ from Razetime's answer.

### How it works

1≠¯1⊥2↑⍸∘⌽∘⊤  ⍝ Input: n
⊤  ⍝ Binary representation of n
⌽∘   ⍝ Reverse
⍸∘     ⍝ Get indices of ones, in increasing order
⍝   LSB index (l) comes first, and the next number is l+1
⍝   iff the bit on the left of LSB is also 1
2↑       ⍝ Take first two numbers, filling with 0 if too short
¯1⊥         ⍝ From [a, b] compute -a + b
1≠            ⍝ Is it not equal to 1?


Equivalent non-extended program:

# APL (Dyalog Unicode), 17 bytes

1≠¯1⊥2↑∘⍸∘⌽2∘⊥⍣¯1


Try it online!

# K (ngn/k), 12 bytes

~1=-/|-2#&2\


• 2\ convert input to base-2
• -2#& get the last two indices containing 1's
• -/| subtract the smaller index from the larger one
• ~1=` if the last truthy index isn't preceded by another truthy value, return 0. otherwise, return 1