36
\$\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\$
3
  • \$\begingroup\$ Given your own MATL solution, is it acceptable to output the result in reverse order? \$\endgroup\$
    – Shaggy
    Jan 22, 2018 at 12:34
  • \$\begingroup\$ Yes, as long as it's sorted. @Shaggy \$\endgroup\$ Jan 22, 2018 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, 2018 at 18:05

54 Answers 54

1
2
1
\$\begingroup\$

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.

\$\endgroup\$
4
  • \$\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
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\$
3
  • 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
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
  • 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\$ Feb 19, 2018 at 8:54
1
\$\begingroup\$

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

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

Arturo, 18 bytes

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

Try it!

Port of The Thonnu's Thunno 2 answer.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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