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

What happens for centers greater than 9 (assuming the numbers are in base9)? In other words what is the sequence following 12345678987654321? — CristiFati
– CristiFati, Commented Jan 3, 2018 at 13:06

DAle · Accepted Answer · 2018-01-03 15:41:37Z

7

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.

edited Jan 3, 2018 at 15:41

answered Jan 3, 2018 at 13:17

DAle

9,1922 gold badges28 silver badges48 bronze badges

Sign up to request clarification or add additional context in comments.

7 Comments

ar kang Over a year ago

Thank you very much! But can you explain this line: k = lsqrt(n-1)l?

DAle Over a year ago

@arkang, sqrt - is a square root of a number, ⌊x⌋ is x rounded down to the nearest integer

ar kang Over a year ago

Unfortunately, this code does not work for certain inputs (which are unknown). But anyway thank you very much for the help!

DAle Over a year ago

@arkang, could you please give me a link to the problem? Maybe that sequence is zero-based?

ar kang Over a year ago

I think link to the problem will be useless, because it is not on english), but I can tell you for sure that there is nothing else in the task and the sequence is not zero based.

|

Collectives™ on Stack Overflow

Handling large numbers python 2.7(runtime error)

1 Answer 1

7 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

7 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related