The first n numbers without consecutive equal binary digits

Question

The sequence contains the decimal representation of the binary numbers of the form: 10101..., where the n-th term has n bits.

The sequence is probably easiest to explain by just showing the relationships between the binary and decimal representations of the numbers:

0       ->  0
1       ->  1
10      ->  2
101     ->  5
1010    ->  10
10101   ->  21
101010  ->  42

Challenge:

Take an input integer n, and return the first n numbers in the sequence. You may choose to have the sequence 0-indexed or 1-indexed.

Test cases:

n = 1   <- 1-indexed
0

n = 18
0, 1, 2, 5, 10, 21, 42, 85, 170, 341, 682, 1365, 2730, 5461, 10922, 21845, 43690, 87381

Explanations are encouraged, as always.

This is OEIS A000975.

Given your own MATL solution, is it acceptable to output the result in reverse order? — Shaggy, Jan 22, 2018 at 12:34
Pushing my luck here, but would this output format be acceptable [85,[42,[21,[10,[5,[2,[1,0]]]]]]]? — Shaggy, Jan 22, 2018 at 18:05

Jo King · Accepted Answer · 2018-01-22 13:20:50Z

1

brainfuck, 40 bytes

,[>.>>[>]<[.->[>]+[<]+<]+<[[-<+>]>-<]<-]

Try it online!

0-indexed. Input as char code, output as unary with null bytes separating series of char code 1s. Assumes 8-bit cells unless you want to input over 255. Assumes negative cells, though this could be fixed at the expense of several bytes.

Previously, 50 bytes

,[[<]>->>[<-<->>>>-<]<[->>++<<]>>+[-<<+>>]<<.<<+>]

Try it online!

Inputs as char code, outputs as char code. 1-indexed. Probably could be golfed a little.

@Unihedron points out I forgot to specify that this needs infinite sized cells, otherwise it tops out at the 8th number.

edited Jan 22, 2018 at 13:20

answered Jan 22, 2018 at 11:18

Jo King♦

47.1k5 gold badges124 silver badges184 bronze badges

\$\begingroup\$ When I run it with `` (0d018) as par the test case, your code prints ` *UªUªUªUªUªUª` (0x01 02 05 0a 15 2a 55 aa 55 aa 55 aa 55 aa 55 aa 55 aa; 0d001 002 005 010 021 042 085 170 085 170 085 170 085 170 085 170 085 170) :( tio.run/##SypKzMxLK03O/… \$\endgroup\$
– Unihedron
Jan 22, 2018 at 11:51
\$\begingroup\$ Ok, seems it is a cell size problem. I think either your code should adapt to big integers or you need to specify the implementation that would run your code properly, but the default of 8-bit cells isn't enough \$\endgroup\$
– Unihedron
Jan 22, 2018 at 11:53
\$\begingroup\$ Forgot about that, thanks @Unihedron! I'll have a think about an 8-bit version, probably outputting in unary. \$\endgroup\$
– Jo King ♦
Jan 22, 2018 at 12:38
\$\begingroup\$ Using an interpreter with 32-bit cells, it works. Though I think I might have a try at a bitinteger (8bit) version myself if you haven't by the weekend :D \$\endgroup\$
– Unihedron
Jan 22, 2018 at 13:25

Add a comment |

Eric Duminil · Accepted Answer · 2018-01-22 15:32:48Z

1

Ruby, 27 bytes

->n{n.times{|i|p 2**i*2/3}}

Try it online!

It's just a Ruby port of this awesome Python answer.

answered Jan 22, 2018 at 15:32

Eric Duminil

1,0598 silver badges12 bronze badges

Add a comment |

LukeS · Accepted Answer · 2018-01-22 18:05:18Z

1

Julia 0.6, 15 14 bytes

!n=2.^(1:n)÷3

Try it online!

Using the 2/3 method. ÷ does integer division in Julia and . is element-wise function application.

-1 Byte thanks to Dennis.

edited Jan 22, 2018 at 18:05

answered Jan 22, 2018 at 13:44

LukeS

4413 silver badges5 bronze badges

2

\$\begingroup\$ ÷ doesn't need the .. \$\endgroup\$
– Dennis
Jan 22, 2018 at 15:19
\$\begingroup\$ I wanted to avoid WARNING: div(A::AbstractArray, B::Number) is deprecated, use div.(A, B) instead.. But you are right: The warning does not matter. \$\endgroup\$
– LukeS
Jan 22, 2018 at 18:01
\$\begingroup\$ Julia 0.5 doesn't print a warning. \$\endgroup\$
– Dennis
Jan 22, 2018 at 18:03

Add a comment |

user45941user45941 · Accepted Answer · 2018-01-23 00:23:34Z

1

Actually, 14 bytes

r⌠;"10"*H2@¿⌡M

Try it online!

Explanation:

r⌠;"10"*H2@¿⌡M
r               range(0, input)
 ⌠;"10"*H2@¿⌡M  map (for n in range):
   "10"*          repeat "10" n times
  ;     H         first n characters
         2@¿      interpret as binary integer

answered Jan 23, 2018 at 0:23

user45941

Add a comment |

Giuseppe · Accepted Answer · 2018-01-23 12:31:10Z

1

R, 21 bytes

cat(2^(1:scan())%/%3)

Try it online!

Based on the same algorithm as many here. 1-indexed.

R, 37 bytes

for(i in 0:scan())cat(F<-2*F+i%%2,"")

Try it online!

0-indexed. Doubling and adding n mod 2 at each iteration yields the correct result. F is initialized to zero.

edited Jan 23, 2018 at 12:31

answered Jan 22, 2018 at 13:21

Giuseppe

28.1k3 gold badges30 silver badges101 bronze badges

Add a comment |

mudkip201 · Accepted Answer · 2018-01-24 02:31:49Z

1

Pyt, 5 bytes

1←ř«₃

Explanation:

1        Pushes 1
 ←       Gets input
  ř      Pushes [1,2,...,input]
   «     Bit-shift 1 to the left by each element in the array
    ₃    Python 2-style division by 3 (2^k/3)

Try it online!

edited Jan 24, 2018 at 2:31

answered Jan 24, 2018 at 2:12

mudkip201

9731 gold badge6 silver badges10 bronze badges

Add a comment |

Tom Carpenter · Accepted Answer · 2018-01-24 15:02:03Z

Octave, 20 bytes

@(x)fix(2.^(1:x)./3)

Try it online!

Using @Neils Python method (+1 to him) saves a heck of a lot of bytes.

Previous answer (independent creation):

Octave, 49 40 bytes

@(n)arrayfun(@(x)sum(2.^(x-1:-2:0)),0:n)

Try it online!

Basically for each value x in 0:n where n is the input (0-indexed), we take a range of x-1:-2:0, and raise 2 to the power of each element in the range. The range results in alternating powers of 2, starting with an empty array [] for 0, then [],[1] for 0:1, then [],[1],[1 4] for 0:2, and so on.

If we then sum each of the produced alternating powers of two, we end up with the required sequence. This only works because in Octave the sum of an empty array is 0, so we can produce the first number 0 by producing no powers of two.

The resulting array, which contains all numbers in the pattern up to and including n is then returned.

Shieru Asakoto · Accepted Answer · 2018-02-06 14:13:32Z

1

JavaScript (Node.js), 44 bytes

In ascending order. Simple recursion. 1-indexed.

f=(n,i=0,a=[])=>n?f(n-1,~i&1+i*2,[...a,i]):a

Try it online!

JavaScript (Node.js), 43 41 38 35 bytes

... or return as string. Still in ascending order. 0-indexed.

f=(n,i=0)=>n?i+[,f(n-1,~i&1+i*2)]:i

Try it online!

JavaScript (Node.js), 40 bytes

In ascending order. 2**n/3 trick. 1-indexed.

n=>Array(n).fill(i=0).map(_=>2**++i/3|0)

Try it online!

edited Feb 6, 2018 at 14:13

answered Feb 6, 2018 at 8:26

Shieru Asakoto

6,17814 silver badges40 bronze badges

Add a comment |

Community · Accepted Answer · 2020-06-17 09:04:33Z

1

JavaScript (ES7), 39 35 31 30 bytes

1-indexed with output in reverse order.

f=n=>n?[2**n/3|0,...f(--n)]:[]

Try it

o.innerText=(
f=n=>n?[2**n/3|0,...f(--n)]:[]
)(i.value=8);oninput=_=>o.innerText=f(+i.value)

<input id=i type=number><pre id=o>

35 byte version, without recursion

n=>[...Array(n)].map(_=>2**n--/3|0)

o.innerText=(f=
n=>[...Array(n)].map(_=>2**n--/3|0)
)(i.value=8);oninput=_=>o.innerText=f(+i.value)

<input id=i type=number><pre id=o>

edited Jun 17, 2020 at 9:04

CommunityBot

1

answered Jan 22, 2018 at 10:43

Shaggy

41.6k4 gold badges34 silver badges92 bronze badges

Add a comment |

Netherwire · Accepted Answer · 2018-02-20 06:49:11Z

1

Ruby, 72 68 61 bytes

->n{a=[0]*n;n.times{|i|i.times{|j|a[i]|=1<<j if i%2!=j%2}};a}

Explained:

def f(n)
  a = [0] * n
  n.times do |i|
    i.times do |j|
      if i.even? != j.even?
        a[i] |= (1 << j)
      end
    end
  end
  a
end

This approach uses n'th bit installation using x | (1 << n). We start from the last bit and proceeding to the first, setting each 2'nd, alternating ones and zeros 'even?' check tells where to start.

Try Now!

I am new in both code golf and Ruby, so any comments will be appreciated!

edited Feb 20, 2018 at 6:49

answered Feb 19, 2018 at 8:43

Netherwire

1194 bronze badges

1

\$\begingroup\$ Welcome to PPCG! Since you're not using f for a recursive call, unnamed functions are completely fine, so you can save two bytes on the f=. Also using odd? instead of even? saves two more bytes. \$\endgroup\$
– Martin Ender
Feb 19, 2018 at 8:54

Add a comment |

DLosc · Accepted Answer · 2021-12-31 19:47:18Z

Pip, 11 bytes

Lai+:i+!%Pi

Attempt This Online!

Explanation

We can compute this sequence without using binary via the following recurrence relation:

\$ a_{n+1} = \left\{ \begin{array}{ll} 2 a_n + 1 & \text{ if } a_n \text{ even,} \\ 2 a_n & \text{ if } a_n \text{ odd.} \end{array} \right. \$

Lai+:i+!%Pi
             i (preset to 0) represents the current item in the sequence
 a           First command-line input
L            Loop that many times:
         Pi    Print i
        %      Take i mod 2
       !       Logically negate (1 -> 0 and 0 -> 1)
     i+        Plus current value of i
  i+:          Add that whole expression to i in-place to get next value in sequence

naffetS · Accepted Answer · 2022-04-24 19:09:39Z

1

Vyxal, 5 bytes

ʁEd3ḭ

Try it Online!

Port of Neil's Python answer.

How?

ʁEd3ḭ
ʁ     # Exclusive zero range of (implicit) input
 E    # Square, implicit vectorization
  d   # Double, implicit vectorization
   3ḭ # Floor divide by three, implicit vectorization again

edited Apr 24, 2022 at 19:09

answered Apr 24, 2022 at 2:38

naffetS

12.2k2 gold badges17 silver badges48 bronze badges

Add a comment |

chunes · Accepted Answer · 2023-06-30 18:46:04Z

1

Arturo, 18 bytes

$=>[map&=>[/2^&3]]

Try it!

Port of The Thonnu's Thunno 2 answer.

answered Jun 30 at 18:46

chunes

22.8k3 gold badges21 silver badges51 bronze badges

Add a comment |

Community · Accepted Answer · 2020-06-17 09:04:33Z

0

Python 3 53 bytes

lambda n:[int(('0'+'10'*i)[:i+1],2)for i in range(n)]

Try it online

edited Jun 17, 2020 at 9:04

CommunityBot

1

answered Jan 22, 2018 at 10:32

Asone Tuhid

2,3537 silver badges22 bronze badges

Add a comment |

Galen Ivanov · Accepted Answer · 2018-01-22 12:32:03Z

0

Red, 71 67 bytes

f: func[n][d: 0 loop n - 1[print d d: d * 2 + either odd? d[0][1]]]

1-indexed

Try it online!

And here's the Red impementation of Neil's 2/3 trick:

Red, 51 bytes

f: func[n][repeat i n[print to-integer 2 ** i / 3]]

Try it online!

edited Jan 22, 2018 at 12:32

answered Jan 22, 2018 at 11:30

Galen Ivanov

21k3 gold badges23 silver badges61 bronze badges

Add a comment |

Giuseppe · Accepted Answer · 2018-01-22 14:12:30Z

0

SNOBOL4 (CSNOBOL4), 64 bytes

	N =INPUT
I	X =LT(X,N) X + 1	:F(END)
	OUTPUT =2 ^ X / 3	:(I)
END

Try it online!

1-indexed. Uses the 2^i/3 method.

answered Jan 22, 2018 at 14:12

Giuseppe

28.1k3 gold badges30 silver badges101 bronze badges

Add a comment |

Community · Accepted Answer · 2020-06-17 09:04:33Z

0

C 52 bytes

i,a;f(n){for(;i++<n;){printf("%d ",a);a=a*2+1-a%2;}}

Try it online!

Without error messages (61 bytes):

int i,a;void f(n){for(;i++<n;){printf("%d ",a);a=a*2+1-a%2;}}

Try it online!

edited Jun 17, 2020 at 9:04

CommunityBot

1

answered Jan 22, 2018 at 16:59

Asone Tuhid

2,3537 silver badges22 bronze badges

Add a comment |

Οurous · Accepted Answer · 2018-01-22 21:05:34Z

0

Clean, 61 bytes

import StdEnv
$i=[sum[2^(n-p)\\p<-[1..n]|isOdd p]\\n<-[0..i]]

Try it online!

answered Jan 22, 2018 at 21:05

Οurous

8,0961 gold badge15 silver badges37 bronze badges

Add a comment |

Xcali · Accepted Answer · 2018-01-23 16:24:40Z

0

Perl 5, 44 + 2 (`-pa`) = 46 bytes

$\+=(length sprintf'%b',$_)/$F[0]while$_--}{

Try it online!

answered Jan 23, 2018 at 16:24

Xcali

13.4k2 gold badges14 silver badges37 bronze badges

Add a comment |

Community · Accepted Answer · 2020-06-17 09:04:33Z

0

clojure, 61 bytes

(fn f[n r](if(> n 0)(cons r(f(- n 1)(+ r r 1(-(mod r 2)))))))

Usage:

user> (f 10 0)
(0 1 2 5 10 21 42 85 170 341)

edited Jun 17, 2020 at 9:04

CommunityBot

1

answered Jan 25, 2018 at 7:01

user84207

1714 bronze badges

Add a comment |

lrn · Accepted Answer · 2018-01-25 13:48:36Z

0

Dart, 49 bytes

f(n,{a:0})=>new List.generate(n,(x)=>a=a<<1|x&1);

Use as

main() {
 print(f(31));
}

See DartPad

answered Jan 25, 2018 at 13:48

lrn

5813 silver badges7 bronze badges

Add a comment |

ellie · Accepted Answer · 2018-01-26 00:00:14Z

0

Jelly, 5 bytes

R2*:3

Try it online!

Took Emigna's strategy and ported it to Jelly.

answered Jan 26, 2018 at 0:00

ellie

1615 bronze badges

Add a comment |

6infinity8 · Accepted Answer · 2018-01-26 10:57:15Z

0

Scala, 64 bytes

val f=(n:Int)=>Stream from 1 map(i=>(1<<i)/3)take n mkString " "

1-indexed. A call to f(7) for example would return 0 1 2 5 10 21 42.

edited Jan 26, 2018 at 10:57

answered Jan 26, 2018 at 10:44

6infinity8

3711 silver badge10 bronze badges

Add a comment |

sporkl · Accepted Answer · 2018-02-06 14:52:25Z

0

Jelly, 13 bytes

Rṁ@⁾10VDḄ
ḶÇ€

Try it online!

answered Feb 6, 2018 at 14:52

sporkl

6,8041 gold badge25 silver badges62 bronze badges

Add a comment |

The first n numbers without consecutive equal binary digits

Challenge:

Test cases:

54 Answers 54

brainfuck, 40 bytes

Previously, 50 bytes

Ruby, 27 bytes

Julia 0.6, 15 14 bytes

Actually, 14 bytes

R, 21 bytes

R, 37 bytes

Pyt, 5 bytes

Octave, 20 bytes

Octave, 49 40 bytes

JavaScript (Node.js), 44 bytes

JavaScript (Node.js), 43 41 38 35 bytes

JavaScript (Node.js), 40 bytes

JavaScript (ES7), 39 35 31 30 bytes

Try it

35 byte version, without recursion

Ruby, 72 68 61 bytes

Pip, 11 bytes

Explanation

Vyxal, 5 bytes

How?

Arturo, 18 bytes

Python 3 53 bytes

Red, 71 67 bytes

Red, 51 bytes

SNOBOL4 (CSNOBOL4), 64 bytes

C 52 bytes

Without error messages (61 bytes):

Clean, 61 bytes

Perl 5, 44 + 2 (-pa) = 46 bytes

clojure, 61 bytes

Dart, 49 bytes

Jelly, 5 bytes

Scala, 64 bytes

Jelly, 13 bytes

Your Answer

Sign up or log in

Post as a guest

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

Linked

Related

Hot Network Questions

Perl 5, 44 + 2 (`-pa`) = 46 bytes

Not the answer you're looking for? Browse other questions tagged
code-golf
math
number
sequence
binary
or ask your own question.