Есть ли другой способ найти элемент n в этой рекурсивной последовательности?

Question

Последовательность:

a _n = a _n-1 + (2 * a _n-2 )

a ₀ = 1, a ₁ = 1. Найдите ₁₀₀

То, как я это сделал, - это создание списка.

 #List 'a' with a0 = 1 , a1 = 1.
a = [1,1]
#To get the a100, implement 'i' as the index value of the list.
for i in range (2,101):
  x = a[i-1] + (2 * a[i-2])
  print( str(len(a)) + (": ") + str(x))
  #Save new value to list
  a.append(x)

Есть ли другой способ сделать это, где вы можете просто получить значение ₁₀₀ ? Или значение ₁₀₀₀₀ .. это займет так много памяти.

Answer 1

В этом конкретном случае c последовательность, по-видимому, известна как последовательность Якобстала . Википедия дает выражение для закрытой формы для a_n, которое может быть выражено следующим образом:

def J(n):
  return (2**(n+1) - (1 if n % 2 else -1))//3

В более общем смысле вы можете использовать быстрое возведение в матрицу, чтобы найти конкретное значение c a_n в O(log n) матричные операции. Подход здесь небольшая модификация это 1011

import numpy as np

def a(n):
  mat = np.array([[1, 2], [1, 0]], dtype=object)  # object for large integers
  return np.linalg.matrix_power(mat, n)[0,0]

1013 * Здесь значение a_1000:.

7143390714575115472989500327066678737076032078036890716291669255802340340832907483287989192104639054183964486117020978834580968571282093623989718383132383202623045183216153990280716403374914094585302788102030983322387960844932511706110362630718041943047464318457694778440286554435082924558137112046251

Answer 2

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

a = lambda n: (2**(n+1) + (-1)**n)//3

Тогда

a(0) == 1
a(1) == 1
a(2) == 3
...

Используйте решение Wolfram Alpha для закрытой формы решение .

Answer 3

Для более общего решения, sympy's rsolve может генерировать формулу для линейных повторений. А затем используйте substitution , чтобы найти конкретные значения.

from sympy import rsolve, Function, symbols

f = Function('f')
n = symbols('n', integer=True)
T = f(n) - f(n - 1) - 2 * f(n - 2)
sol = rsolve(T, f(n), {f(0): 1, f(1): 1})
print(sol.factor())
for k in range(6):
    print(f'a[{10**k}] = {sol.subs({n:10**k})}')

Это находит формулу: ((-1)**n + 2*2**n)/3 и подстановка различных значений дает:

a[1] = 1
a[10] = 683
a[100] = 845100400152152934331135470251
a[1000] = 7143390714575115472989500327066678737076032078036890716291669255802340340832907483287989192104639054183964486117020978834580968571282093623989718383132383202623045183216153990280716403374914094585302788102030983322387960844932511706110362630718041943047464318457694778440286554435082924558137112046251
a[10000] = 13300420779205055899224947751223900558823312212574616365680059665686292553481297754613307789357463065266220752948806082847704327566275854078395857288064215971903820031195863017843497700844039930347033391278795541028339072307078736457006049910726416592060326596558672835961088838567081045539649268371274925376816731095916294031173247751323635481912358774462877183753093841891253840488152356727760984122637587639312975932940560640357511880709747618222262691017043766353735428453489979600223956211100972865182186443850404115054687605329465453071585497122508186691535256991501267222976387636433705286400943222614410489725426171396919846079518533884638490449629415374679171890883668485549192847140249201910928687618755494267749463781127049374279769561549759200832570764870138287994839741197500087328573494472227205070621546774178994858997503894208562707691159300991409504210074059830342802209213468621093971730976504006937230561044048029975244677676707947087336124281517272447267049737611904634607637370045500833604005013228174598706158078702963192048604263495032226147988471602982108251173897742022519137359868942131422329103081800375446624970338827853981873988860876269047918349845673238184625284288814399599917924440538912558558685095521850114849105048496522741529593155873907738282168861316542080131736118854643798317265443020838956090639908522753418790270855651099392460347365053921743882641323846748271362887055383912692879736402269982104388805781403942200602501882277026496929598476838303527006808207298214407168983217160516849324232198998893837958637097759081249712999519344381402467576288757211476207860932148655897231556293513976121900670048618498909700385756334067235325208259649285799693889564105871362639412657210097186118095746465818754306322522134720983321447905340926047485500603884544957480384983947611769143791817076603055269994974019086721023722205420067991783904156229025970272783748933896591684108429045765889012975813584862160062970831282169566933785351515891836917604484599090827358327607311145704700506065400164526586785514617302254188281302685535172938965970009784445593131997924161090875584262602248970534271757827918474036922817159666073457645479797721100990086996148246631809842046103645478455250800241851505149187576887740797874187195112987924800865762440512367759907023068198581038345298256830912964615391929510632144672034080214910330858779357159414245558929061170945822567007313514409276959727327732103102944890874437957354081499958646666151187821572015407908429716866090505450005466559490856410166587392640154829574782514412057571343645656039081553195235917082324370960357975081345975714019208241045008362225535513352731779100379038105003677818345932796086474225126766610787543447696005152433715459704967280220123536564742545543604882702212692308056024281175802607700426526000495235781464187268985316355546978912530579053491968145752746720495213034211965438416298865678974339803258684849814383125421063166939821410053665460303868944551299858094210708807124261007787849536528397806251