A short investigation of the Look-and-Say Digit Sequence. Additional details on C-finite sequences in Sage can be found in the documentation.
Requirements: None
# Define the ring of C-finite sequences over the rationals
C.<z> = CFiniteSequences(QQ)
print(C)
The ring of C-Finite sequences in z over Rational Field
# Rational generating function due to Conway
g = -12*z^78+18*z^77-18*z^76+18*z^75-18*z^74+20*z^73+22*z^72-31*z^71-15*z^70+4*z^69+4*z^68+19*z^67-62*z^66+50*z^65+21*z^64+11*z^63-41*z^62-54*z^61+56*z^60+44*z^59-15*z^58+27*z^57+15*z^56-45*z^55+8*z^54-89*z^53+64*z^52+66*z^51+25*z^50-38*z^49-126*z^48+39*z^47+32*z^46+33*z^45+65*z^44-107*z^43-14*z^42-16*z^41+13*z^40+79*z^39-7*z^38-42*z^37-12*z^36-8*z^35+26*z^34+9*z^33-35*z^32+23*z^31+20*z^30+30*z^29-34*z^28-58*z^27+z^26+20*z^25+36*z^24+6*z^23-13*z^22-8*z^21-6*z^20-3*z^19+z^18+4*z^17+z^16+4*z^15+5*z^14+z^13-8*z^12-6*z^11+6*z^9+4*z^8-z^7-z^5-z^4-z^3-z^2+z+1
h = 6*z^72-9*z^71+9*z^70-18*z^69+16*z^68-11*z^67+14*z^66-8*z^65+z^64-5*z^63+7*z^62+2*z^61+8*z^60-14*z^59-5*z^58-5*z^57+19*z^56+3*z^55-6*z^54-7*z^53-6*z^52+16*z^51-7*z^50+8*z^49-22*z^48+17*z^47-12*z^46+7*z^45+5*z^44+7*z^43-8*z^42+4*z^41-7*z^40-9*z^39+13*z^38-4*z^37-6*z^36+14*z^35-14*z^34+19*z^33-7*z^32-13*z^31+2*z^30-4*z^29+18*z^28-z^26-4*z^25-12*z^24+8*z^23-5*z^22+8*z^20+z^19+7*z^18-8*z^17-5*z^16-2*z^15+3*z^14+3*z^13-2*z^8-z^7+3*z^5+z^4-z^3-z^2-z+1
f = g/h
digitseq = C(f)
# Initial terms of the sequence
digitseq.series(10)
1 + 2*x + 2*x^2 + 4*x^3 + 6*x^4 + 6*x^5 + 8*x^6 + 10*x^7 + 14*x^8 + 20*x^9 + O(x^10)
# Get a linear recurrence satisfied by the digit counting sequence
digitseq.recurrence_repr()
'homogeneous linear recurrence with constant coefficients of degree 72: a(n+72) = a(n+71) + a(n+70) + a(n+69) - a(n+68) - 3*a(n+67) + a(n+65) + 2*a(n+64) - 3*a(n+59) - 3*a(n+58) + 2*a(n+57) + 5*a(n+56) + 8*a(n+55) - 7*a(n+54) - a(n+53) - 8*a(n+52) + 5*a(n+50) - 8*a(n+49) + 12*a(n+48) + 4*a(n+47) + a(n+46) - 18*a(n+44) + 4*a(n+43) - 2*a(n+42) + 13*a(n+41) + 7*a(n+40) - 19*a(n+39) + 14*a(n+38) - 14*a(n+37) + 6*a(n+36) + 4*a(n+35) - 13*a(n+34) + 9*a(n+33) + 7*a(n+32) - 4*a(n+31) + 8*a(n+30) - 7*a(n+29) - 5*a(n+28) - 7*a(n+27) + 12*a(n+26) - 17*a(n+25) + 22*a(n+24) - 8*a(n+23) + 7*a(n+22) - 16*a(n+21) + 6*a(n+20) + 7*a(n+19) + 6*a(n+18) - 3*a(n+17) - 19*a(n+16) + 5*a(n+15) + 5*a(n+14) + 14*a(n+13) - 8*a(n+12) - 2*a(n+11) - 7*a(n+10) + 5*a(n+9) - a(n+8) + 8*a(n+7) - 14*a(n+6) + 11*a(n+5) - 16*a(n+4) + 18*a(n+3) - 9*a(n+2) + 9*a(n+1) - 6*a(n), starting a(0...) = [1, 2, 2, 4, 6, 6, 8, 10, 14, 20, 26, 34, 46, 62, 78, 102, 134, 176, 226, 302, 408, 528, 678, 904, 1182, 1540, 2012, 2606, 3410, 4462, 5808, 7586, 9898, 12884, 16774, 21890, 28528, 37158, 48410, 63138, 82350, 107312, 139984, 182376, 237746, 310036, 403966, 526646, 686646, 894810, 1166642, 1520986, 1982710, 2584304, 3369156, 4391702, 5724486, 7462860, 9727930, 12680852, 16530884, 21549544, 28091184, 36619162, 47736936, 62226614, 81117366, 105745224, 137842560, 179691598, 234241786, 305351794, 398049970, 518891358, 676414798, 881752750, 1149440192, 1498380104, 1953245418]'
# Sequence terms can also be accessed directly
print(digitseq[1000])
27981351371113001020436934044969543281325518064547027161534027713608590019465423516313818830989981757685809308236276
# Sage can find the closed form of the sequence (corresponding to Theorem 2.3 in the textbook)
# Takes 10+ minutes
asm = digitseq.closed_form()
asm
2.042160076857881?*1.303577269034297?^n - (1.304638747964804? - 0.1269290081499280?*I)*(1.059673936824031? + 0.06193785064242932?*I)^n - (1.304638747964804? + 0.1269290081499280?*I)*(1.059673936824031? - 0.06193785064242932?*I)^n + (0.02805004006256416? - 0.6707565233085509?*I)*(1.032508921516637? + 0.2788945601052167?*I)^n + (0.02805004006256416? + 0.6707565233085509?*I)*(1.032508921516637? - 0.2788945601052167?*I)^n - (0.12331055512333749? + 1.201334126923233?*I)*(1.020231387488337? + 0.1732885609934655?*I)^n - (0.12331055512333749? - 1.201334126923233?*I)*(1.020231387488337? - 0.1732885609934655?*I)^n + (0.0981439660979499? - 0.01577626267857238?*I)*(0.9814594704741177? + 0.3758720971778864?*I)^n + (0.0981439660979499? + 0.01577626267857238?*I)*(0.9814594704741177? - 0.3758720971778864?*I)^n + (0.03481179854242824? - 0.1121258670026815?*I)*(0.9161602225609649? + 0.6457963110326476?*I)^n + (0.03481179854242824? + 0.1121258670026815?*I)*(0.9161602225609649? - 0.6457963110326476?*I)^n + (1.628877576705379? + 1.686352734102582?*I)*(0.9104733616787827? + 0.1519984821535185?*I)^n + (1.628877576705379? - 1.686352734102582?*I)*(0.9104733616787827? - 0.1519984821535185?*I)^n - (0.003919639533825015? + 0.2266456462319149?*I)*(0.8567209043332170? + 0.4490317560825665?*I)^n - (0.003919639533825015? - 0.2266456462319149?*I)*(0.8567209043332170? - 0.4490317560825665?*I)^n - (0.04077290929829635? + 0.07087511881818378?*I)*(0.8399666788300980? + 0.6003062158802451?*I)^n - (0.04077290929829635? - 0.07087511881818378?*I)*(0.8399666788300980? - 0.6003062158802451?*I)^n - (0.2840300502107521? - 0.3004542497948497?*I)*(0.678827751775423? + 0.6478304904047382?*I)^n - (0.2840300502107521? + 0.3004542497948497?*I)*(0.678827751775423? - 0.6478304904047382?*I)^n - (0.4893153413442025? + 0.5778030774135450?*I)*(0.594227321547377? + 0.7225690549852261?*I)^n - (0.4893153413442025? - 0.5778030774135450?*I)*(0.594227321547377? - 0.7225690549852261?*I)^n + (0.3874848481654065? + 0.2054814416473357?*I)*(0.5675536121973295? + 0.8341522109021707?*I)^n + (0.3874848481654065? - 0.2054814416473357?*I)*(0.5675536121973295? - 0.8341522109021707?*I)^n - (0.02549605434774883? - 0.02408173751335947?*I)*(0.542332767099137? + 0.9258485990610539?*I)^n - (0.02549605434774883? + 0.02408173751335947?*I)*(0.542332767099137? - 0.9258485990610539?*I)^n - (0.1292061890592742? - 0.2764105281976084?*I)*(0.4177076932836939? + 0.9981509518397633?*I)^n - (0.1292061890592742? + 0.2764105281976084?*I)*(0.4177076932836939? - 0.9981509518397633?*I)^n + (0.04418834616280911? - 0.2872664347944996?*I)*(0.3164150356396493? + 0.9583273406901440?*I)^n + (0.04418834616280911? + 0.2872664347944996?*I)*(0.3164150356396493? - 0.9583273406901440?*I)^n - (0.5240034544546955? - 1.453097263525036?*I)*(0.1504039520646909? + 0.8558656132043055?*I)^n - (0.5240034544546955? + 1.453097263525036?*I)*(0.1504039520646909? - 0.8558656132043055?*I)^n - (0.3352645703036359? - 0.007019255038281606?*I)*(0.1232258097296343? + 1.014958362086107?*I)^n - (0.3352645703036359? + 0.007019255038281606?*I)*(0.1232258097296343? - 1.014958362086107?*I)^n + (0.1987574648009353? - 0.001298820082271100?*I)*(-0.001038328986626625? + 1.054668185905421?*I)^n + (0.1987574648009353? + 0.001298820082271100?*I)*(-0.001038328986626625? - 1.054668185905421?*I)^n - (0.2146947244544422? + 0.1520998408859337?*I)*(-0.07279394407030095? + 1.067737534526073?*I)^n - (0.2146947244544422? - 0.1520998408859337?*I)*(-0.07279394407030095? - 1.067737534526073?*I)^n - (1.092598946233596? - 0.02431308050796932?*I)*(-0.1298724492560712? + 0.9038748892735383?*I)^n - (1.092598946233596? + 0.02431308050796932?*I)*(-0.1298724492560712? - 0.9038748892735383?*I)^n + (0.1811807413893607? + 0.10998685967342738?*I)*(-0.2430397042958056? + 0.9056239736870791?*I)^n + (0.1811807413893607? - 0.10998685967342738?*I)*(-0.2430397042958056? - 0.9056239736870791?*I)^n - (0.005443724527454856? - 0.03459781388160297?*I)*(-0.2806289245025200? + 1.062905415380168?*I)^n - (0.005443724527454856? + 0.03459781388160297?*I)*(-0.2806289245025200? - 1.062905415380168?*I)^n - (0.08036051054309407? + 0.07688475881572641?*I)*(-0.3530186552790463? + 0.9793508619496293?*I)^n - (0.08036051054309407? - 0.07688475881572641?*I)*(-0.3530186552790463? - 0.9793508619496293?*I)^n + (0.2381689367509643? - 0.3830631668563242?*I)*(-0.4247306738917062? + 0.7762732379754871?*I)^n + (0.2381689367509643? + 0.3830631668563242?*I)*(-0.4247306738917062? - 0.7762732379754871?*I)^n - (0.03366273985027083? + 0.04773559644797399?*I)*(-0.4832345922564344? + 1.038600821422953?*I)^n - (0.03366273985027083? - 0.04773559644797399?*I)*(-0.4832345922564344? - 1.038600821422953?*I)^n - (0.003562666935307555? + 0.0697803982057204?*I)*(-0.5832139196610093? + 0.7313357205425795?*I)^n - (0.003562666935307555? - 0.0697803982057204?*I)*(-0.5832139196610093? - 0.7313357205425795?*I)^n + (0.05754696952765589? - 0.02925700946333145?*I)*(-0.6693089055601368? + 0.8773407372761569?*I)^n + (0.05754696952765589? + 0.02925700946333145?*I)*(-0.6693089055601368? - 0.8773407372761569?*I)^n - (0.11973995751392972? + 0.4540951592172023?*I)*(-0.7323331945525536? + 0.6254876986244164?*I)^n - (0.11973995751392972? - 0.4540951592172023?*I)*(-0.7323331945525536? - 0.6254876986244164?*I)^n - (0.0923137604628498? - 0.0671045777082309?*I)*(-0.7519238040211451? + 0.8097588973508138?*I)^n - (0.0923137604628498? + 0.0671045777082309?*I)*(-0.7519238040211451? - 0.8097588973508138?*I)^n + (0.02167124679228547? + 0.004848716702948803?*I)*(-0.8323067713147285? + 0.5189859757039583?*I)^n + (0.02167124679228547? - 0.004848716702948803?*I)*(-0.8323067713147285? - 0.5189859757039583?*I)^n + (0.0772151729658365? - 0.05800776326362268?*I)*(-0.9305647670774127? + 0.3131783328349095?*I)^n + (0.0772151729658365? + 0.05800776326362268?*I)*(-0.9305647670774127? - 0.3131783328349095?*I)^n - (0.1429345593175186? - 0.006216889595755088?*I)*(-0.9716042876499926? + 0.3815090162192434?*I)^n - (0.1429345593175186? + 0.006216889595755088?*I)*(-0.9716042876499926? - 0.3815090162192434?*I)^n - (0.01593311718974587? + 0.001099832142389197?*I)*(-0.9879742365208926? + 0.6100133753185804?*I)^n - (0.01593311718974587? - 0.001099832142389197?*I)*(-0.9879742365208926? - 0.6100133753185804?*I)^n + 0.006720042877328100?*(-1.011153820101259?)^n + (0.04599975234636240? + 0.001656480671067814?*I)*(-1.031493213627106? + 0.2397268031579972?*I)^n + (0.04599975234636240? - 0.001656480671067814?*I)*(-1.031493213627106? - 0.2397268031579972?*I)^n + 0.0006555622786823183?*(-1.088244112543826?)^n + (0.01517085068523166? + 0.003381087198300183?*I)*(-1.130898122714237? + 0.1597722162774364?*I)^n + (0.01517085068523166? - 0.003381087198300183?*I)*(-1.130898122714237? - 0.1597722162774364?*I)^n - 1
# For each summand a*p^n print absolute value of exponential part p
summands = asm.operands() # Create list of summands
[k.operands()[0].operands()[0].abs() for k in summands[0:-1]] # Extract base and compute absolute value
[1.303577269034297?, 1.061482524456406?, 1.061482524456406?, 1.069512435022488?, 1.069512435022488?, 1.034843470959528?, 1.034843470959528?, 1.050972181182851?, 1.050972181182851?, 1.120893584934062?, 1.120893584934062?, 0.923073822022723?, 0.923073822022723?, 0.9672642999160666?, 0.9672642999160666?, 1.032429936784732?, 1.032429936784732?, 0.9383450649300170?, 0.9383450649300170?, 0.9355277381754175?, 0.9355277381754175?, 1.008923690707685?, 1.008923690707685?, 1.072996019868072?, 1.072996019868072?, 1.082028206511739?, 1.082028206511739?, 1.009212448740643?, 1.009212448740643?, 0.8689806077596091?, 0.8689806077596091?, 1.022411402984160?, 1.022411402984160?, 1.054668697026756?, 1.054668697026756?, 1.070216053387879?, 1.070216053387879?, 0.9131575266814713?, 0.9131575266814713?, 0.9376689605510934?, 0.9376689605510934?, 1.099327301267429?, 1.099327301267429?, 1.041033276017875?, 1.041033276017875?, 0.8848707732440088?, 0.8848707732440088?, 1.145516188193635?, 1.145516188193635?, 0.9354092217996849?, 0.9354092217996849?, 1.103494984286915?, 1.103494984286915?, 0.9630922951482984?, 0.9630922951482984?, 1.105033428857442?, 1.105033428857442?, 0.9808572804204174?, 0.9808572804204174?, 0.9818510344665798?, 0.9818510344665798?, 1.043821834048524?, 1.043821834048524?, 1.161124200977918?, 1.161124200977918?, 1.011153820101259?, 1.058984036664920?, 1.058984036664920?, 1.088244112543826?, 1.142128593921363?, 1.142128593921363?]
# Dominant asymptotics are given by the following term
domasm = summands[0]
domasm
2.042160076857881?*1.303577269034297?^n
# The constants appearing here are algebraic numbers of degree 71
print(QQbar(domasm.operands()[0].operands()[0]).minpoly().degree())
print(QQbar(domasm.operands()[1]).minpoly().degree())
71 71