32
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Given your own MATL solution, is it acceptable to output the result in reverse order? \$\endgroup\$ – Shaggy Jan 22 '18 at 12:34
  • \$\begingroup\$ Yes, as long as it's sorted. @Shaggy \$\endgroup\$ – Stewie Griffin Jan 22 '18 at 12:42
  • \$\begingroup\$ Pushing my luck here, but would this output format be acceptable [85,[42,[21,[10,[5,[2,[1,0]]]]]]]? \$\endgroup\$ – Shaggy Jan 22 '18 at 18:05

50 Answers 50

1
\$\begingroup\$

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.

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

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.

\$\endgroup\$
  • 2
    \$\begingroup\$ ÷ doesn't need the .. \$\endgroup\$ – Dennis Jan 22 '18 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 '18 at 18:01
  • \$\begingroup\$ Julia 0.5 doesn't print a warning. \$\endgroup\$ – Dennis Jan 22 '18 at 18:03
1
\$\begingroup\$

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

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.

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

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!

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

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.

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

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!

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

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>

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

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!

\$\endgroup\$
  • 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 '18 at 8:54
0
\$\begingroup\$

Python 3 53 bytes

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

Try it online

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

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!

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

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.

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

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!

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

Clean, 61 bytes

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

Try it online!

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

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

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

Try it online!

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

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

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

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

Jelly, 5 bytes

R2*:3

Try it online!

Took Emigna's strategy and ported it to Jelly.

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

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.

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

Jelly, 13 bytes

Rṁ@⁾10VDḄ
ḶÇ€

Try it online!

\$\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.