_Yet another easy kata!_


# Task:
  
  
  - Let's write a sequence starting with `seq = [0, 1, 2, 2]` in which
      - 0 and 1 occurs 1 time
      - 2 occurs 2 time
  
  
  and sequence advances with adding next natural number `seq[natural number]` times so now, 3 appears 
  2 times and so on.
  
  ### Input
   - You are given input `n`  and return nth(0-based) value of this list.
  
  
  let;s take example:
  
  seq = [0, 1, 2, 2]\
  i = 3 and as seq[i]=2, seq = [0, 1, 2, 2, 3, 3]\
  i = 4 and as seq[i]=3, seq = [0, 1, 2, 2, 3, 3, 4, 4, 4]\
  i = 5 and as seq[i]=3, seq = [0, 1, 2, 2, 3, 3, 4, 4, 4, 5, 5, 5]
  and so on.
  
  Some elements of list:
  ```
[0, 1, 2, 2, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6, 6, 7, 7, 7, 7, 8, 8, 8, 8, 9, 9, 9, 9, 9, 10, 10, 10, 10, 10, 11, 11, 11, 11, 11, 12, 12, 12, 12, 12, 12, 13, 13, 13, 13, 13, 13, 14, 14, 14, 14, 14, 14, 15, 15, 15, 15, 15, 15, 16, 16, 16, 16, 16, 16, 16, 17, 17, 17, 17, 17, 17, 17, 18, 18, 18, 18, 18, 18, 18, 19, 19, 19, 19, 19, 19, 19, 20, 20, 20, 20, 20, 20, 20, 20, 21, 21, 21, 21, 21, 21, 21, 21]
  ```
  
  
  # Constraint :
  
  
  * Python
    - 0 <= n <= `$2^{41}$`
  * Javascript
    - 0 <= n <= `$2^{49}$`
  
  
  

##### Have fun!

_tip: you can solve this using smart brute-force._

Difficulty: interview

Starter code:

def find(n):
	

Solutions:
idx, n, seq = 2, 6, [1, 2, 4, 6]
while n < 2 ** 41:
    idx += 1
    seq.extend(range(n + idx, n + (seq[idx] - seq[idx-1]) * idx + 1, idx))
    n += (seq[idx] - seq[idx-1]) * idx

from bisect import bisect
def find(n): return bisect(seq, n)

cache = [0, 2, 4]
comp = [0, 2, 6]

repeat = len(cache)-1
b = cache[-1]
while comp[-1] < 2 ** 41:
    if len(cache) >= b:
        repeat += 1
        b = cache[repeat]
    cache.append(cache[-1] + repeat)
    comp.append(comp[-1] + (cache[-1] - cache[-2]) * (len(cache) - 1))

from bisect import bisect
def find(n):
    repeat = bisect(comp, n)
    return cache[repeat-1] + (n - comp[repeat-1]) // repeat

cache = [0, 2, 4]
pc = [0, 2, 6]

repeat = len(cache)-1
b = cache[-1]
while pc[-1] < 2 ** 41:
    if len(cache) >= b:
        repeat += 1
        b = cache[repeat]
    cache.append(cache[-1] + repeat)
    pc.append(pc[-1] + (cache[-1] - cache[-2]) * (len(cache) - 1))

from bisect import bisect
def find(n):
    repeat = bisect(pc, n)
    return cache[repeat-1] + (n - pc[repeat-1]) // repeat

# That was the easy?
# - Cache is too slow (first version with bisect failed monsters)
# - Recursion is too deep
# - Formula is too imprecise
# I fear what the hard version will be x)

x, y, r, i, memo = 3, 4, 2, 0, []
for n in range(3, 100000):
    if n > x:
        _, _, x, r = memo[i]
        i += 1
    memo.append([y, r, y+r-1, n])
    y += r
        
def find(n):
    if n < 6: return [0, 1, 2, 2, 3, 3][n]
    x = 6
    for a, b, _, y in memo:
        if y * b >= n - x:
            return (n - x) // y + a
        x += y * b

# ~~~without caching - 5s~~~

from itertools import count

def find(n):
    if n < 12:
        return [0, 1, 2, 2, 3, 3, 4, 4, 4, 5, 5, 5][n]
    track, upcoming, passed = [], 6, 12
    _, b, repeat = 4, 5, 3
    for ongoing in count(2+2):
        if ongoing > b:
            _, b, repeat = track.pop(0)
        track.append([upcoming, upcoming + repeat - 1, ongoing])
        if passed + (repeat * ongoing) >= n:
            return upcoming + (n - passed) // ongoing
        passed += repeat * ongoing
        upcoming += repeat

import math

def find(n):
    first = [0, 1, 2, 2, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6, 6, 7, 7, 7, 7, 8, 8, 8, 8, 9, 9, 9, 9, 9, 10, 10, 10, 10, 10, 11, 11, 11, 11, 11, 12, 12, 12, 12, 12, 12, 13, 13, 13, 13, 13, 13, 14, 14, 14, 14, 14, 14, 15, 15, 15, 15, 15, 15, 16, 16, 16, 16, 16, 16, 16, 17, 17, 17, 17, 17, 17, 17, 18, 18, 18, 18, 18, 18, 18, 19, 19, 19, 19, 19, 19, 19, 20, 20, 20, 20, 20, 20, 20, 20, 21, 21, 21, 21, 21, 21, 21, 21]
    if n < 13: return first[n]
    seq=[1,1,3,5]
    k = 3
    add = 3
    count = 2
    sum = 11
    while(True):
        if sum+add*len(seq)>=n:
            return math.ceil((n-sum)/len(seq))+seq[len(seq)-1]
        seq.append(seq[len(seq)-1]+add)
        sum+=add*(len(seq)-1)
        count-=1
        if count == 0:
            k+=1  
            add += 1 #seq[k]-seq[k-1]
            count= seq[k]-seq[k-1]
        



import math


def memoize(f):
    memo = {}    
    def helper(x):
        if x not in memo:
            memo[x] = f(x)
        return memo[x]    
    return helper


def find_bounds(n):
    low_prod = 0
    high_prod = 0
    low = 0
    high = 0
    for x in range(1, n+1):
        low = high
        low_prod = high_prod
        high += find(x)
        high_prod += x * find(x)
        if high_prod > n:
            ratio = (n - low_prod) / (high_prod - low_prod)
            return ratio, high, low


@memoize   
def find(n):
    if n == 0:
        return 0
    if n == 1:
        return 1
    if n == 2:
        return 2
    
    ratio, high, low = find_bounds(n)
    return low + math.ceil((high-low) * ratio)


def find(n):
    if n<4:
        return [0,1,2,2][n]
    
    x,length,last_number,cycle,c = 2,2,1,2,[]

    for y in range(2,10000):
        for i in range(cycle):
            length += x*y
            last_number += y
            if length >= n:
                while length > n:
                    length -= x
                    last_number -= 1
                    if length<=n:
                        return last_number+1
            x += 1
        c.append(cycle)
        if cycle <= 3 and c.count(cycle)==2: # 2
            cycle += 1
        elif cycle <= 5 and c.count(cycle)==3: # 2
            cycle += 1
        elif cycle <= 8 and c.count(cycle)==4: # 3
            cycle += 1
        elif cycle <= 11 and c.count(cycle)==5: # 3
            cycle += 1
        elif cycle <= 15 and c.count(cycle)==6: # 4
            cycle += 1
        elif cycle <= 19 and c.count(cycle)==7: # 4
            cycle += 1
        elif cycle <= 23 and c.count(cycle)==8: # 4
            cycle += 1
        elif cycle <= 28 and c.count(cycle)==9: # 5
            cycle += 1
        elif cycle <= 33 and c.count(cycle)==10: # 5
            cycle += 1
        elif cycle <= 38 and c.count(cycle)==11: # 5
            cycle += 1
        elif cycle <= 44 and c.count(cycle)==12: # 6
            cycle += 1
        elif cycle <= 50 and c.count(cycle)==13: # 6
            cycle += 1
        elif cycle <= 56 and c.count(cycle)==14: # 6
            cycle += 1
        elif cycle <= 62 and c.count(cycle)==15: # 6
            cycle += 1
        elif cycle <= 69 and c.count(cycle)==16: # 7
            cycle += 1
        elif cycle <= 76 and c.count(cycle)==17: # 7
            cycle += 1
        elif cycle <= 83 and c.count(cycle)==18: # 7
            cycle += 1
        elif cycle <= 90 and c.count(cycle)==19: # 7
            cycle += 1
        elif cycle <= 98 and c.count(cycle)==20: # 8
            cycle += 1
        elif cycle <= 106 and c.count(cycle)==21: # 8
            cycle += 1


from itertools import chain, repeat

def find(n):
    if n <= 3: return [0, 1, 2, 2][n]
    inicio, suma, largo  = [[2]], 5, 4
    for i, j in enumerate(chain.from_iterable(inicio), 3):
        suma += i * j
        if suma >= n:
            x = (suma - n) // i
            return j + largo - x-1
        inicio.append(repeat(i, j))
        largo += j

import math

def find(n):
    level = []
    sum2, result, i = 0,0,0
    rem = 3
    current = 2
    while sum2 <= n:
        sum2 += (i+1)*current
        result += current
        i += 1
        rem -= 1
        level.append(current)      
        if rem == 0:
            rem = level[current]
            current += 1    
    return result - math.ceil((sum2 - n)/(i))