All the Solutions to Hofsdater's Q-recurrence with initial 2 initial conditi\ ons between 1 and, 16 That happen to have Rational Generating Functions By Shalosh B. Ekhad Recall that the famous (or, more accurately, infamous), Hofsdater's Q-sequen\ ce, Sequence A005185 in the OEIS is defined by the intial conditions Q(1)=1, Q(2)=1, and for n>2 by Q(n)=Q(n-Q(n-1))+Q(n-Q(n-2)) It seems to be completely "chaotic". Nevertheless, if instead of the initial\ conditions [1,1], one takes the following one, one gets sequences whose generating functions are rational. 6 5 4 3 2 -3 t - t + t + 3 t + t + 2 t INI= , [2, 1], Generating Function=, --------------------------------- 6 3 t - 2 t + 1 and in Maple notation: (-3*t^6-t^5+t^4+3*t^3+t^2+2*t)/(t^6-2*t^3+1) 4 2 -2 t + 2 t + 2 t INI= , [2, 2], Generating Function=, ------------------ 4 2 t - 2 t + 1 and in Maple notation: (-2*t^4+2*t^2+2*t)/(t^4-2*t^2+1) 4 3 2 -t - 2 t + 3 t + 2 t INI= , [2, 3], Generating Function=, ----------------------- 4 2 t - 2 t + 1 and in Maple notation: (-t^4-2*t^3+3*t^2+2*t)/(t^4-2*t^2+1) 7 2 -2 t + 4 t + 2 t INI= , [2, 4], Generating Function=, ------------------ 6 4 2 t - t - t + 1 and in Maple notation: (-2*t^7+4*t^2+2*t)/(t^6-t^4-t^2+1) 6 4 3 2 2 t - 5 t - 2 t + 5 t + 2 t INI= , [2, 5], Generating Function=, ------------------------------- 4 2 t - 2 t + 1 and in Maple notation: (2*t^6-5*t^4-2*t^3+5*t^2+2*t)/(t^4-2*t^2+1) 9 2 -2 t + 6 t + 2 t INI= , [2, 6], Generating Function=, ------------------ 8 6 2 t - t - t + 1 and in Maple notation: (-2*t^9+6*t^2+2*t)/(t^8-t^6-t^2+1) 8 4 3 2 2 t - 7 t - 2 t + 7 t + 2 t INI= , [2, 7], Generating Function=, ------------------------------- 4 2 t - 2 t + 1 and in Maple notation: (2*t^8-7*t^4-2*t^3+7*t^2+2*t)/(t^4-2*t^2+1) 11 2 -2 t + 8 t + 2 t INI= , [2, 8], Generating Function=, ------------------- 10 8 2 t - t - t + 1 and in Maple notation: (-2*t^11+8*t^2+2*t)/(t^10-t^8-t^2+1) 10 4 3 2 2 t - 9 t - 2 t + 9 t + 2 t INI= , [2, 9], Generating Function=, -------------------------------- 4 2 t - 2 t + 1 and in Maple notation: (2*t^10-9*t^4-2*t^3+9*t^2+2*t)/(t^4-2*t^2+1) 13 2 -2 t + 10 t + 2 t INI= , [2, 10], Generating Function=, -------------------- 12 10 2 t - t - t + 1 and in Maple notation: (-2*t^13+10*t^2+2*t)/(t^12-t^10-t^2+1) 12 4 3 2 2 t - 11 t - 2 t + 11 t + 2 t INI= , [2, 11], Generating Function=, ---------------------------------- 4 2 t - 2 t + 1 and in Maple notation: (2*t^12-11*t^4-2*t^3+11*t^2+2*t)/(t^4-2*t^2+1) 15 2 -2 t + 12 t + 2 t INI= , [2, 12], Generating Function=, -------------------- 14 12 2 t - t - t + 1 and in Maple notation: (-2*t^15+12*t^2+2*t)/(t^14-t^12-t^2+1) 14 4 3 2 2 t - 13 t - 2 t + 13 t + 2 t INI= , [2, 13], Generating Function=, ---------------------------------- 4 2 t - 2 t + 1 and in Maple notation: (2*t^14-13*t^4-2*t^3+13*t^2+2*t)/(t^4-2*t^2+1) 17 2 -2 t + 14 t + 2 t INI= , [2, 14], Generating Function=, -------------------- 16 14 2 t - t - t + 1 and in Maple notation: (-2*t^17+14*t^2+2*t)/(t^16-t^14-t^2+1) 16 4 3 2 2 t - 15 t - 2 t + 15 t + 2 t INI= , [2, 15], Generating Function=, ---------------------------------- 4 2 t - 2 t + 1 and in Maple notation: (2*t^16-15*t^4-2*t^3+15*t^2+2*t)/(t^4-2*t^2+1) 19 2 -2 t + 16 t + 2 t INI= , [2, 16], Generating Function=, -------------------- 18 16 2 t - t - t + 1 and in Maple notation: (-2*t^19+16*t^2+2*t)/(t^18-t^16-t^2+1) 6 2 -2 t + 2 t + 4 t INI= , [4, 2], Generating Function=, ------------------ 6 4 2 t - t - t + 1 and in Maple notation: (-2*t^6+2*t^2+4*t)/(t^6-t^4-t^2+1) 8 2 -2 t + 2 t + 6 t INI= , [6, 2], Generating Function=, ------------------ 8 6 2 t - t - t + 1 and in Maple notation: (-2*t^8+2*t^2+6*t)/(t^8-t^6-t^2+1) 10 2 -2 t + 2 t + 8 t INI= , [8, 2], Generating Function=, ------------------- 10 8 2 t - t - t + 1 and in Maple notation: (-2*t^10+2*t^2+8*t)/(t^10-t^8-t^2+1) 12 2 -2 t + 2 t + 10 t INI= , [10, 2], Generating Function=, -------------------- 12 10 2 t - t - t + 1 and in Maple notation: (-2*t^12+2*t^2+10*t)/(t^12-t^10-t^2+1) 14 2 -2 t + 2 t + 12 t INI= , [12, 2], Generating Function=, -------------------- 14 12 2 t - t - t + 1 and in Maple notation: (-2*t^14+2*t^2+12*t)/(t^14-t^12-t^2+1) 16 2 -2 t + 2 t + 14 t INI= , [14, 2], Generating Function=, -------------------- 16 14 2 t - t - t + 1 and in Maple notation: (-2*t^16+2*t^2+14*t)/(t^16-t^14-t^2+1) 18 2 -2 t + 2 t + 16 t INI= , [16, 2], Generating Function=, -------------------- 18 16 2 t - t - t + 1 and in Maple notation: (-2*t^18+2*t^2+16*t)/(t^18-t^16-t^2+1) To sum up, here are the succesful ones, in Maple notation. {[[2, 1], (-3*t^6-t^5+t^4+3*t^3+t^2+2*t)/(t^6-2*t^3+1)], [[2, 2], (-2*t^4+2*t^2 +2*t)/(t^4-2*t^2+1)], [[2, 3], (-t^4-2*t^3+3*t^2+2*t)/(t^4-2*t^2+1)], [[2, 4], (-2*t^7+4*t^2+2*t)/(t^6-t^4-t^2+1)], [[2, 5], (2*t^6-5*t^4-2*t^3+5*t^2+2*t)/(t^ 4-2*t^2+1)], [[2, 6], (-2*t^9+6*t^2+2*t)/(t^8-t^6-t^2+1)], [[2, 7], (2*t^8-7*t^ 4-2*t^3+7*t^2+2*t)/(t^4-2*t^2+1)], [[2, 8], (-2*t^11+8*t^2+2*t)/(t^10-t^8-t^2+1 )], [[2, 9], (2*t^10-9*t^4-2*t^3+9*t^2+2*t)/(t^4-2*t^2+1)], [[2, 10], (-2*t^13+ 10*t^2+2*t)/(t^12-t^10-t^2+1)], [[2, 11], (2*t^12-11*t^4-2*t^3+11*t^2+2*t)/(t^4 -2*t^2+1)], [[2, 12], (-2*t^15+12*t^2+2*t)/(t^14-t^12-t^2+1)], [[2, 13], (2*t^ 14-13*t^4-2*t^3+13*t^2+2*t)/(t^4-2*t^2+1)], [[2, 14], (-2*t^17+14*t^2+2*t)/(t^ 16-t^14-t^2+1)], [[2, 15], (2*t^16-15*t^4-2*t^3+15*t^2+2*t)/(t^4-2*t^2+1)], [[2 , 16], (-2*t^19+16*t^2+2*t)/(t^18-t^16-t^2+1)], [[4, 2], (-2*t^6+2*t^2+4*t)/(t^ 6-t^4-t^2+1)], [[6, 2], (-2*t^8+2*t^2+6*t)/(t^8-t^6-t^2+1)], [[8, 2], (-2*t^10+ 2*t^2+8*t)/(t^10-t^8-t^2+1)], [[10, 2], (-2*t^12+2*t^2+10*t)/(t^12-t^10-t^2+1)] , [[12, 2], (-2*t^14+2*t^2+12*t)/(t^14-t^12-t^2+1)], [[14, 2], (-2*t^16+2*t^2+ 14*t)/(t^16-t^14-t^2+1)], [[16, 2], (-2*t^18+2*t^2+16*t)/(t^18-t^16-t^2+1)]} ----------------------------------------------------------------- This ends this article, that took, 108.186, seconds.