29
\$\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\$
2
  • \$\begingroup\$ someway related \$\endgroup\$
    – nimi
    Commented Jun 28, 2017 at 15:30
  • 14
    \$\begingroup\$ The least significant bit of 100001011000 is a 0. Do you mean the least significant 1? \$\endgroup\$ Commented Jun 28, 2017 at 15:30

40 Answers 40

1
2
1
\$\begingroup\$

Husk, 10 8 bytes

¬!2↓¬↔Θḋ

Try it online!

¬          # logical NOT of
 !2        # the second element
   ↓¬      # after chopping-off initial zeros
     ↔     # of the reverse of
      Θḋ   # the binary digits of the input
\$\endgroup\$
1
\$\begingroup\$

Stax, 5 bytes

éò/ú╗

Run and debug it

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

tinylisp, 83 bytes

(load library
(d F(q((x)(i(h x)x(F(t x
(d G(q((x)(- 1(h(t(F(reverse(c 0(to-base 2 x

Try it online!

fixed with dlosc's help.

\$\endgroup\$
2
  • \$\begingroup\$ Doesn't work for powers of 2--you'll want to cons a 0 to the front of the binary representation before reversing it, I think. \$\endgroup\$
    – DLosc
    Commented Feb 2, 2022 at 16:29
  • \$\begingroup\$ Also, def can be d. \$\endgroup\$
    – DLosc
    Commented Feb 2, 2022 at 16:35
1
\$\begingroup\$

Vyxal, 6 bytes

b0PṪt⌐

Try it Online!

b      # Convert to binary
 0P    # Strip zeroes
   Ṫt  # Second-to-last item
     ⌐ # The NOT of that
\$\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\$
3
  • \$\begingroup\$ This returns false for everything because the character (0 or 1) is always a string. \$\endgroup\$
    – Shaggy
    Commented Jun 28, 2017 at 16:14
  • \$\begingroup\$ Oops, should've noticed that... Fixed now \$\endgroup\$
    – Luke
    Commented Jun 28, 2017 at 16:17
  • \$\begingroup\$ Looks like it fails for 1 now. \$\endgroup\$
    – Shaggy
    Commented Jun 28, 2017 at 16:28
0
\$\begingroup\$

JavaScript (ES6), 53 34 bytes

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

MMIX, 24 bytes (6 instrs)

00000000: 36ff0000 c8ffff00 3bffff01 c80000ff  6”¡¡Ṁ””¡;””¢Ṁ¡¡”
00000010: 73000001 f8010000                    s¡¡¢ẏ¢¡¡

Disassembled

dragon  NEGU $255,0,$0      // t = -n
        AND  $255,$255,$0   // t &= n (gets last 1 bit)
        SLU  $255,$255,1    // t <<= 1
        AND  $0,$0,$255     // n &= t
        ZSZ  $0,$0,1        // n = !n
        POP  1,0            // return n
\$\endgroup\$
0
\$\begingroup\$

Japt -!, 6 bytes

&n)Ñ&U

Try it

&n)Ñ&U     :Implicit input of integer U
&          :Bitwise AND of U with
 n         :Its negation
  )        :Group that together
   Ñ       :Multiply by 2
    &U     :Bitwise AND with U
\$\endgroup\$
1
2

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.