Similar setting of the [previous](https://www.codewars.com/kata/progressive-spiral-number-position/), this time you are called to identify in which "branch" of the spiral a given number will end up.

Considering a square of numbers disposed as the 25 items in [the previous kata](https://www.codewars.com/kata/progressive-spiral-number-position/), the branch are numbered as it follows:

```
17 16 15 14 13    1 1 1 1 0
18 05 04 03 12    2 1 1 0 0
19 06 01 02 11 => 2 2 0 0 0
20 07 08 09 10    2 2 3 3 0
21 22 23 24 25    2 3 3 3 3
```

Meaning that, for example, numbers in the `10-13` range will be in branch `0`, numbers in the range `14-17` are inside branch `1`, all those nice numbers in the `18-21` can call branch `2` their house and finally the `21-25` team all falls under the `3` branch.

Your function must return the number of the index of each number [`1` being a special case you might consider equivalent to being in the first branch, `0`], as per examples:

```python
branch(1) == 0 #kind of special case here
branch(5) == 1
branch(25) == 3
branch(30) == 0
branch(50) == 0
```

It might help A LOT to both solve the [previous kata](https://www.codewars.com/kata/progressive-spiral-number-position/) and to visualize the diagonals of the square. Be ready for big numbers and, as usual, inspired by [AoC](http://adventofcode.com/2017/day/3). Finally, when ready, go to compute [the distance](https://www.codewars.com/kata/progressive-spiral-number-distance/) of the series.

Difficulty: EASY
Tags: Number theory

Mathematics

Ad-hoc

Starter code:
def branch(n):
	

Solutions:
from math import ceil

def branch(n):
	if n == 1:
		return 0
	l = int(ceil(n ** 0.5)) // 2
	n -= (2 * l - 1) ** 2 + 1
	return n // (2 * l or 1)


branch = lambda n: (lambda r: r and (n - 2) // r + 2 - r)(0 - (1 - n ** 0.5) // 2 * 2)


branch = lambda n: 0 if n == 1 else (lambda s: (n - s * s - 1) // (s + 1))(((n - 1) ** 0.5 - 1) // 2 * 2 + 1)


def branch(n):
	if n == 1:
		return 0
	i = 1
	while True:
		if n <= (2 * i - 1) ** 2:
			break
		i += 1
	return int((n - (2 * i - 3) ** 2 - 1) / (2 * i - 2))


(k, li) = (1, [0])
for i in range(1, 1000000):
	li.append(k)
	k += 8 * i

def branch(n):
	(a, b) = next(([i, li[i - 1] + 1] for (i, j) in enumerate(li) if j >= n))
	step = a * 2 - 2
	for i in range(4):
		if b <= n < b + step:
			return i
		b += step
	return 0


def branch(n):
	if n == 1:
		return 0
	l = (1 + int((n - 1 + 0.5) ** 0.5)) // 2
	x = (2 * l - 1) ** 2 + 1
	return (n - x) // (l * 2)


import math

def branch(n):
	l = (math.sqrt(n) + 1) // 2
	d = n - (2 * l - 1) ** 2
	if d == 0:
		if l == 1:
			return 0
		else:
			return 3
	else:
		return int((d - 1) / (2 * l))


from math import ceil

def branch(n):
	k = ceil(n ** 0.5) // 2
	lst = list(range((2 * k - 1) ** 2 + 1, (2 * k + 1) ** 2 + 1)) or [1]
	return lst.index(n) // (len(lst) / 4)


memo = [[0, 0, 0, 0], [1, 1, 1, 1]]
for i in range(3, 1000000, 2):
	memo.append([j for j in range(i ** 2, i ** 2 - (i - 1) * 3 - 1, -i + 1)][::-1])

def branch(n):
	layer = int((1 + (n - 1) ** 0.5) // 2 + 1)
	for (branch, coner_number) in enumerate(memo[layer]):
		if n <= coner_number:
			return branch


from math import sqrt, ceil

def branch(n):
	if n == 1:
		return 0
	x = ceil(sqrt(n)) // 2 * 2
	return (n - 1 - (x - 1) ** 2) // x