_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._

Source: codewars | Difficulty: MEDIUM
Tags: Data structures

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


(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


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
			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:
			cycle += 1
		elif cycle <= 5 and c.count(cycle) == 3:
			cycle += 1
		elif cycle <= 8 and c.count(cycle) == 4:
			cycle += 1
		elif cycle <= 11 and c.count(cycle) == 5:
			cycle += 1
		elif cycle <= 15 and c.count(cycle) == 6:
			cycle += 1
		elif cycle <= 19 and c.count(cycle) == 7:
			cycle += 1
		elif cycle <= 23 and c.count(cycle) == 8:
			cycle += 1
		elif cycle <= 28 and c.count(cycle) == 9:
			cycle += 1
		elif cycle <= 33 and c.count(cycle) == 10:
			cycle += 1
		elif cycle <= 38 and c.count(cycle) == 11:
			cycle += 1
		elif cycle <= 44 and c.count(cycle) == 12:
			cycle += 1
		elif cycle <= 50 and c.count(cycle) == 13:
			cycle += 1
		elif cycle <= 56 and c.count(cycle) == 14:
			cycle += 1
		elif cycle <= 62 and c.count(cycle) == 15:
			cycle += 1
		elif cycle <= 69 and c.count(cycle) == 16:
			cycle += 1
		elif cycle <= 76 and c.count(cycle) == 17:
			cycle += 1
		elif cycle <= 83 and c.count(cycle) == 18:
			cycle += 1
		elif cycle <= 90 and c.count(cycle) == 19:
			cycle += 1
		elif cycle <= 98 and c.count(cycle) == 20:
			cycle += 1
		elif cycle <= 106 and c.count(cycle) == 21:
			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)