Handling large numbers python 2.7(runtime error)

Question

I have to make a program that finds the n-th element in the following endless sequence:

1 1 2 1 1 2 3 2 1 1 2 3 4 3 2 1......

So here you can see that 'center' increments by one and side elements of the 'center' reflect each other so we can break this sequence into small groups:

[1][121][12321][1234321]..... 

So the task is to find n-th element in the sequence given n. For example, we take 7 as input and must return 3, because the 7th element in sequence is 3. The problem here is that when n exceeds 10^15 my program shows runtime error, while input can be as large as 10^100000. Here is my code:

n = int(input())
fin = n
number = long(1)
counter = long(0)
while n>0:
    n = n - number
    number = number+2
    counter = counter + 1
mid = long((counter-1)*(2+2*(counter-1))/2+1)

place = long(counter - abs(mid-fin))

if fin==0:
    print 0
else:
    print place

Answer 1

We have groups of numbers:

[1] [1 2 1] [1 2 3 2 1] ...

The overall amount of numbers in k groups is:

1 + 3 + 5 + ... + k*2-1 

This is an arithmetic progression, its sum equals to

(1 + k*2-1) * k / 2 = k^2

Now let's find the number of full groups k that go before n-th number in the sequence.

k = ⌊sqrt(n-1)⌋

Now we know that our n-th number is in group number k+1 that has k*2+1 elements. Let's discard first k groups (they have k^2 numbers), now we need to find the number with index n-k^2. And its value will be equal to k+1 - |n-k^2 - (k+1)|. For relatively small n we can use this code:

n = int(input())
k = int(math.sqrt(n-1))
print(k+1 - abs(n-k*k - (k+1)))

But seeing the n <= 10^5000000 constraint we cannot simply use math.sqrt, we need other way of finding a square root of a large integer. This SO question could be helpful.