For every positive integer N, there exists a unique sequence starting with 1 and ending with N and such that every number in the sequence is either the double of the preceeding number or the double plus 1. 

For example, given N = 13, the sequence is [1, 3, 6, 13], because . . . :
```
 3 =  2*1 +1
 6 =  2*3
 13 = 2*6 +1
```

Write a function that returns this sequence given a number N. Try generating the elements of the resulting list in ascending order, i.e., without resorting to a list reversal or prependig the elements to a list.

Difficulty: introductory

Starter code:

def climb(n):
	

Solutions:
def climb(n):
    return [1] if n == 1 else climb(int(n/2)) + [n]

# If we write the decision tree for the problem we can see
# that we can traverse upwards from any node simply by
# dividing by two and taking the floor. This would require
# a reversal of the list generated since we're building it
# backwards.
# 
# If we examine the successor function (x -> {2x, 2x + 1})
# we can deduce that the binary representation of any number
# gives us the steps to follow to generate it: if the n-th (LTR)
# bit is set, we use 2x + 1 for the next element, otherwise we
# choose 2x. This allows us to build the sequence in order.

def climb(n):
    res = []
    cur = 1
    mask = 1 << max(0, n.bit_length() - 2)

    while cur <= n:
        res.append(cur)
        cur = 2*cur + (1 if (n & mask) != 0 else 0)
        mask >>= 1

    return res

def climb(n):
    result = [1]
    for x in "{:b}".format(n)[1:]:
        result.append(result[-1]*2 + (x=='1'))
    return result

def climb(n):
    return [n >> i for i in range(len(f"{n:b}") - 1, -1, -1)]

from math import log
from collections import deque
    
def climb(n):
    return [n//2**i for i in range(int(log(n, 2)) + 1)][::-1]

def climb(n):
    """This is much faster."""
    seq = deque([n])
    while n > 1:
        n //= 2
        seq.appendleft(n)
    return list(seq)

def climb(n):
    #your code here
    return  [n>>n.bit_length()-i-1 for i in range(n.bit_length())]


def climb(n):
    return list(climb_iterator(n))
    
def climb_iterator(n):
    cursor = 0
    for digit in bin(n)[2:]:
        cursor = 2 * cursor + int(digit)
        yield cursor

def climb(n):
  res = [n]
  while res[-1] != 1: res.append(res[-1]//2)
  return res[::-1]

def climb(n):
    arr = []
    while n:
        arr.append(n)
        n //= 2
    return arr[::-1]