CODEWITHSUNDEEP
pythonsequence
user11846775
user11846775

Reputation:

script to calculate the nth element of the sequence

I am trying to write some code that will calculate the nth element of the sequence. 

a_i = 2 * a_i-1 + 1 for i > 0, where a_0 = 1.

I understand how the formula works and how to implement it in Python.

I am just lost at how to find the formula for the nth element.

It has been some time since I have taken clac2.

I know there is a way to find the formula so if anyone has any tips it would be much appreciated!

I would post some code but I know that it is wrong and does not calculate the nth element.

As of right now, I am just hard coding each element. So, as I said, once I know the formula to find the nth element I can write the code.

Upvotes: 1

Views: 794

Answers (3)

ForceBru
ForceBru

Reputation: 44838

That can be done with a pretty straightforward recursive function:

def a(i):
    if i == 0:
        return 1
    return 2 * a(i - 1) + 1

Of course, if you need a list like [a(i) for i in range(1000)], you don't want the function to recalculate a(0), a(1), ..., a(n - 2), a(n - 1) in order to calculate a(n) for all n, so you need a cache:

import functools 

@functools.lru_cache(None)
def a(i):
    ...  # do the thing

Upvotes: 1

NPE
NPE

Reputation: 500307

First of all, observe that a_0 = 1 = 2**(0+1) - 1.

Now, by induction:

a_i = 2 * a_(i-1) + 1 = 2*(2**((i-1)+1) - 1) + 1 = 2**(i+1) - 1.

This give you a closed-form solution:

>>> def a(i):
...   return 2**(i+1) - 1
...
>>> [a(i) for i in range(10)]
[1, 3, 7, 15, 31, 63, 127, 255, 511, 1023]

Upvotes: 5

mentallurg
mentallurg

Reputation: 5207

You don't need formula that directly gives you the nth element. Calculate the 1st element, then the 2nd etc. until you get the nth element.

Upvotes: 0

Related Questions