0

The sequence is:

an = an-1 + (2 * an-2)

a0 = 1, a1= 1. Find a100

The way I did it is making a list.

 #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)

Is there another way to do this where you can just directly get the value of a100? Or the value of a10000.. it will take up so much memory.

wjandrea
  • 28,235
  • 9
  • 60
  • 81
Eric Lin
  • 39
  • 6
  • 3
    You don't actually need to store everything in a list: just keep the last two entries in variables. Your update step would be something like `a0, a1 = a1, a0+2*a1`, then print `a1`. I don't know the mathematical technique for directly calculating values, but there's a website called the Online Encyclopedia of Integer Sequences (oeis.org) that most likely knows this sequence already, and probably has a generating function listed for it. Just calculate a dozen or so terms, and paste them into the site's search field. – jasonharper Mar 16 '20 at 03:22
  • Thank you, that's a cool website! – Eric Lin Mar 16 '20 at 03:50
  • I tried your steps, and it works perfectly. Thank you! `def x(n): a = 1 b = 1 for i in range(2,n): a, b = b, b + 2*a return b print (x(101))` – Eric Lin Mar 16 '20 at 04:30

3 Answers3

3

For this specific case, the sequence appears to be known as the Jacobsthal sequence. Wikipedia gives a closed form expression for a_n that can be expressed as follows:

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

Slightly more generally, you can use fast matrix exponentiation to find a specific value of a_n in O(log n) matrix operations. The approach here is a slight modification of this.

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]

Here is the value for a_1000:

7143390714575115472989500327066678737076032078036890716291669255802340340832907483287989192104639054183964486117020978834580968571282093623989718383132383202623045183216153990280716403374914094585302788102030983322387960844932511706110362630718041943047464318457694778440286554435082924558137112046251

hilberts_drinking_problem
  • 11,322
  • 3
  • 22
  • 51
  • 1
    Thank you so much! Now I know why discrete math is so closely related to functions in programming. – Eric Lin Mar 16 '20 at 03:56
2

This recurrence relation has a closed form solution:

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

Then

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

Use Wolfram Alpha solve for the closed form solution.

Vincent Lucarelli
  • 164
  • 5
1

For a more general solution, sympy's rsolve can generate a formula for linear recurrences. And then use substitution to find particular values.

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})}')

This finds the formula: ((-1)**n + 2*2**n)/3 and substituting various values gives:

a[1] = 1
a[10] = 683
a[100] = 845100400152152934331135470251
a[1000] = 7143390714575115472989500327066678737076032078036890716291669255802340340832907483287989192104639054183964486117020978834580968571282093623989718383132383202623045183216153990280716403374914094585302788102030983322387960844932511706110362630718041943047464318457694778440286554435082924558137112046251
a[10000] = 13300420779205055899224947751223900558823312212574616365680059665686292553481297754613307789357463065266220752948806082847704327566275854078395857288064215971903820031195863017843497700844039930347033391278795541028339072307078736457006049910726416592060326596558672835961088838567081045539649268371274925376816731095916294031173247751323635481912358774462877183753093841891253840488152356727760984122637587639312975932940560640357511880709747618222262691017043766353735428453489979600223956211100972865182186443850404115054687605329465453071585497122508186691535256991501267222976387636433705286400943222614410489725426171396919846079518533884638490449629415374679171890883668485549192847140249201910928687618755494267749463781127049374279769561549759200832570764870138287994839741197500087328573494472227205070621546774178994858997503894208562707691159300991409504210074059830342802209213468621093971730976504006937230561044048029975244677676707947087336124281517272447267049737611904634607637370045500833604005013228174598706158078702963192048604263495032226147988471602982108251173897742022519137359868942131422329103081800375446624970338827853981873988860876269047918349845673238184625284288814399599917924440538912558558685095521850114849105048496522741529593155873907738282168861316542080131736118854643798317265443020838956090639908522753418790270855651099392460347365053921743882641323846748271362887055383912692879736402269982104388805781403942200602501882277026496929598476838303527006808207298214407168983217160516849324232198998893837958637097759081249712999519344381402467576288757211476207860932148655897231556293513976121900670048618498909700385756334067235325208259649285799693889564105871362639412657210097186118095746465818754306322522134720983321447905340926047485500603884544957480384983947611769143791817076603055269994974019086721023722205420067991783904156229025970272783748933896591684108429045765889012975813584862160062970831282169566933785351515891836917604484599090827358327607311145704700506065400164526586785514617302254188281302685535172938965970009784445593131997924161090875584262602248970534271757827918474036922817159666073457645479797721100990086996148246631809842046103645478455250800241851505149187576887740797874187195112987924800865762440512367759907023068198581038345298256830912964615391929510632144672034080214910330858779357159414245558929061170945822567007313514409276959727327732103102944890874437957354081499958646666151187821572015407908429716866090505450005466559490856410166587392640154829574782514412057571343645656039081553195235917082324370960357975081345975714019208241045008362225535513352731779100379038105003677818345932796086474225126766610787543447696005152433715459704967280220123536564742545543604882702212692308056024281175802607700426526000495235781464187268985316355546978912530579053491968145752746720495213034211965438416298865678974339803258684849814383125421063166939821410053665460303868944551299858094210708807124261007787849536528397806251
JohanC
  • 71,591
  • 8
  • 33
  • 66