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

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

27.3k3 gold badges30 silver badges99 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

9631 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,12813 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

39.6k4 gold badges32 silver badges90 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.7k2 gold badges16 silver badges47 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,3037 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

20.9k3 gold badges22 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

27.3k3 gold badges30 silver badges99 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,3037 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,0861 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

13k2 gold badges13 silver badges35 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

5713 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

1515 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,6921 gold badge25 silver badges62 bronze badges

Add a comment |

The first n numbers without consecutive equal binary digits

Challenge:

Test cases:

52 Answers 52

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?

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.