скрипт для вычисления n-го элемента последовательности

Question

Я пытаюсь написать некоторый код, который будет вычислять n-й элемент последовательности.

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

Я понимаю, как работает формула и как ее реализовать в Python.

Я просто заблудился, как найти формулу для n-го элемента.

Прошло какое-то время с тех пор, как я принял clac2.

Я знаю, что есть способ найти формулу, поэтому, если у кого-то есть какие-либо советы, она будет очень признательна!

Я бы опубликовал некоторый код, но я знаю, что он неправильный и не вычисляет n-й элемент.

На данный момент я просто жестко кодирую каждый элемент.Итак, как я уже сказал, когда я знаю формулу для поиска n-го элемента, я могу написать код.

Answer 1

Прежде всего, обратите внимание, что a_0 = 1 = 2**(0+1) - 1.

Теперь по индукции:

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

Это даст вам решение в закрытой форме:

>>> 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]

Answer 2

Это можно сделать с помощью довольно простой рекурсивной функции:

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

Конечно, если вам нужен список типа [a(i) for i in range(1000)], вы не хотите, чтобы функция пересчитывала a(0), a(1), ..., a(n - 2), a(n - 1) в порядкедля расчета a(n) для всех n, поэтому вам нужен кеш:

import functools 

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

Answer 3

Вам не нужна формула, которая напрямую дает вам n-й элемент.Вычислите 1-й элемент, затем 2-й и т. Д., Пока не получите n-й элемент.