23
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ someway related \$\endgroup\$ – nimi Jun 28 '17 at 15:30
  • 9
    \$\begingroup\$ The least significant bit of 100001011000 is a 0. Do you mean the least significant 1? \$\endgroup\$ – scatter Jun 28 '17 at 15:30

30 Answers 30

16
\$\begingroup\$

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,#]][[#]]&
\$\endgroup\$
  • 3
    \$\begingroup\$ Wow! A mathematica answer and it's not builtin only. Have an upvote! \$\endgroup\$ – KeyWeeUsr Jun 28 '17 at 20:21
  • 2
    \$\begingroup\$ The only thing that could make this answer even better is an explanation for why and how it works. :P \$\endgroup\$ – Martin Ender Jun 29 '17 at 9:10
  • 2
    \$\begingroup\$ @MartinEnder arxiv.org/pdf/1408.5770.pdf See the remark after Example 13. \$\endgroup\$ – alephalpha Jun 29 '17 at 9:22
7
\$\begingroup\$

Python 3, 22 21 bytes

1 byte thanks to ETHproductions.

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

Try it online!

Bitwise arithmetic ftw.

\$\endgroup\$
  • 2
    \$\begingroup\$ "You may output by integer or by boolean" so I guess you don't need the 0+(...)? \$\endgroup\$ – Martin Ender Jun 28 '17 at 15:51
  • \$\begingroup\$ 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)... \$\endgroup\$ – ETHproductions Jun 28 '17 at 15:51
  • \$\begingroup\$ oh god what. this is what I was looking for :o nice! \$\endgroup\$ – HyperNeutrino Jun 28 '17 at 15:51
  • \$\begingroup\$ & has the lowest precedence, so it is 1+(n^~-n) \$\endgroup\$ – Leaky Nun Jun 28 '17 at 15:51
  • \$\begingroup\$ Ah, found the precedence table. Now it all makes sense :P \$\endgroup\$ – ETHproductions Jun 28 '17 at 15:54
6
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ 31 bytes (should I post it myself?) \$\endgroup\$ – Leaky Nun Jun 28 '17 at 15:55
  • \$\begingroup\$ 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/… \$\endgroup\$ – Martin Ender Jun 28 '17 at 15:55
  • \$\begingroup\$ @MartinEnder essentially my algorithm... with 2 bytes off \$\endgroup\$ – Leaky Nun Jun 28 '17 at 15:55
  • \$\begingroup\$ @LeakyNun Oh yeah, they're both the same idea. Great minds and stuff... ;) \$\endgroup\$ – Martin Ender Jun 28 '17 at 15:56
  • \$\begingroup\$ 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 ;) \$\endgroup\$ – FryAmTheEggman Jun 28 '17 at 15:59
6
\$\begingroup\$

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

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

05AB1E, 6 bytes

b0ܨθ≠

Try it online!

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

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.

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

Python 2, 19 bytes

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

Try it online!

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

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!

\$\endgroup\$
  • \$\begingroup\$ You can use div instead of quot. \$\endgroup\$ – nimi Jun 28 '17 at 16:48
  • \$\begingroup\$ Even better: divMod: f x|(d,m)<-divMod x 2=[mod(1+d)2,f d]!!m \$\endgroup\$ – nimi Jun 28 '17 at 16:54
  • \$\begingroup\$ @nimi I don't even understand how that works. You should probably just post it yourself. \$\endgroup\$ – Wheat Wizard Jun 28 '17 at 16:55
  • \$\begingroup\$ 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. \$\endgroup\$ – nimi Jun 28 '17 at 17:07
  • 1
    \$\begingroup\$ Oh, sorry, you have to flip the list elements: [f d,mod(1+d)2]. Try it online!. \$\endgroup\$ – nimi Jun 28 '17 at 17:44
3
\$\begingroup\$

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
\$\endgroup\$
  • 1
    \$\begingroup\$ @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. \$\endgroup\$ – Govind Parmar Jun 28 '17 at 16:30
  • 1
    \$\begingroup\$ I couldn't say how common it is, but it is definitely wrong \$\endgroup\$ – Peter Taylor Jun 28 '17 at 16:43
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – Cody Gray Jun 28 '17 at 17:27
  • 3
    \$\begingroup\$ 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. \$\endgroup\$ – Cody Gray Jun 28 '17 at 18:10
  • 2
    \$\begingroup\$ 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. \$\endgroup\$ – Cody Gray Jun 28 '17 at 18:12
3
\$\begingroup\$

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.

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

C (gcc), 20 bytes

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

Try it online!

\$\endgroup\$
  • \$\begingroup\$ 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". \$\endgroup\$ – Cody Gray Jun 29 '17 at 10:22
  • \$\begingroup\$ 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. \$\endgroup\$ – Dennis Jun 29 '17 at 14:41
  • \$\begingroup\$ "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. \$\endgroup\$ – Cody Gray Jun 30 '17 at 10:31
  • \$\begingroup\$ 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. \$\endgroup\$ – Dennis Jun 30 '17 at 15:18
  • \$\begingroup\$ 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. \$\endgroup\$ – Cody Gray Jun 30 '17 at 15:22
3
\$\begingroup\$

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

Haskell, 33 bytes

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

Try it online!

Uses 0-indexing.

\$\endgroup\$
  • 1
    \$\begingroup\$ What does the ~ do in this context? I get that it is a lazy match, but why do you need a lazy match? \$\endgroup\$ – Wheat Wizard Jul 17 '17 at 14:28
2
\$\begingroup\$

Jelly, 7 6 bytes

1 byte thanks to Erik the Outgolfer.

Bt0ṖṪṆ

Try it online!

Longer programs

\$\endgroup\$
  • \$\begingroup\$ Hmm...well, you can just do ṖṪṆ (as my deleted answer) instead of ṫ-ḄỊ. \$\endgroup\$ – Erik the Outgolfer Jun 28 '17 at 15:31
  • 1
    \$\begingroup\$ Another one for your 7-byte list: BUḌDḊḢ¬ \$\endgroup\$ – steenbergh Jun 28 '17 at 16:26
2
\$\begingroup\$

,,,, 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                             []
\$\endgroup\$
2
\$\begingroup\$

Haskell, 26 bytes

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

Try it online!

Boolean output.

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

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
\$\endgroup\$
  • \$\begingroup\$ How come I never heard of de2bi... :O \$\endgroup\$ – Sanchises Jun 29 '17 at 20:53
1
\$\begingroup\$

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!

\$\endgroup\$
  • \$\begingroup\$ So which one is your submission? \$\endgroup\$ – Leaky Nun Jun 28 '17 at 15:44
  • \$\begingroup\$ @LeakyNun The first one because it's shorter; the second one was my original submission. Should I post them separately? \$\endgroup\$ – HyperNeutrino Jun 28 '17 at 15:46
  • \$\begingroup\$ ~-x&1 works for the while condition instead, I think. \$\endgroup\$ – FryAmTheEggman Jun 28 '17 at 15:47
  • \$\begingroup\$ (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! \$\endgroup\$ – HyperNeutrino Jun 28 '17 at 15:49
  • \$\begingroup\$ @StewieGriffin Ah yes, thanks. Unfortunately I can't ping the user because the edit was rejected. \$\endgroup\$ – HyperNeutrino Jun 28 '17 at 15:58
1
\$\begingroup\$

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

Pari/GP, 20 bytes

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

Using the Kronecker symbol.

Try it online!

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

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

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.

\$\endgroup\$
  • \$\begingroup\$ Welcome to the site! \$\endgroup\$ – DJMcMayhem Jun 28 '17 at 18:48
1
\$\begingroup\$

C (gcc), 35 31 bytes

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

Switched to a recursive implementation. Try it online!

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

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?

\$\endgroup\$
0
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ This returns false for everything because the character (0 or 1) is always a string. \$\endgroup\$ – Shaggy Jun 28 '17 at 16:14
  • \$\begingroup\$ Oops, should've noticed that... Fixed now \$\endgroup\$ – Luke Jun 28 '17 at 16:17
  • \$\begingroup\$ Looks like it fails for 1 now. \$\endgroup\$ – Shaggy Jun 28 '17 at 16:28
0
\$\begingroup\$

JavaScript (ES6), 53 34 bytes

a=>eval("for(;~a&1;a/=2);~a>>1&1")
\$\endgroup\$
  • \$\begingroup\$ 42 bytes: a=>!+(a=a.toString(2))[a.lastIndexOf(1)-1] \$\endgroup\$ – Shaggy Jun 28 '17 at 16:24
  • \$\begingroup\$ I already found a shorter (mathematical) solution... \$\endgroup\$ – Luke Jun 28 '17 at 16:27
  • \$\begingroup\$ Nice :) Mind if I post that 42 byte one? \$\endgroup\$ – Shaggy Jun 28 '17 at 16:42
  • \$\begingroup\$ @Shaggy, no not at all \$\endgroup\$ – Luke Jun 28 '17 at 21:16
0
\$\begingroup\$

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!

\$\endgroup\$
0
\$\begingroup\$

Common Lisp, 56 bytes

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

Try it online!

\$\endgroup\$
0
\$\begingroup\$

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

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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