Again, the relevant property isn't really interleaved polynomials, but rather eventual periodicity mod any integer. But the only Hurwitz numbers we have formulæ for are "single mover", linear, or equivalent thereto under homographic maps. Julian habilitated my nonworking attempt at this, but before doing so correctly predicted that, for any Hurwitz number h, there would be exactly σ(|ad-bc|) equivalence classes of patterns among the continued fractions for (a h +b)/(c h + d), where σ is DivisorSigma. E.g., there are seven possible patterns when Δ := |ad-bc| =4, regardless of h. For h := Coth[1/3], e.g., In[75]:= hursigs[Coth[1/3], 69, 4] During evaluation of In[75]:= 0.606005 (secs) Out[75]= {7, 4 -4 10 {1, 3, 8 + 9 k, 156 + 144 k, 11 + 9 k, 3, 1, 12 + 9 k, } 0 1 228 + 144 k, 15 + 9 k} 2 -3 18 {1, 1, 1 + 9 k, 1, 3, 3 + 9 k, 1, 1, 20 + 36 k, 1, 1, 0 2 6 + 9 k, 3, 1, 7 + 9 k, 1, 1, 38 + 36 k} 2 -4 1 {3 + 6 k} 0 2 1 0 10 {1, 3, 2 + 9 k, 60 + 144 k, 5 + 9 k, 3, 1, 6 + 9 k, -1 4 132 + 144 k, 9 + 9 k} 1 -1 18 {1, 1, 3 + 9 k, 3, 1, 4 + 9 k, 1, 1, 26 + 36 k, 1, 1, -1 5 7 + 9 k, 1, 3, 9 + 9 k, 1, 1, 44 + 36 k} 1 -2 18 {1, 1, 9 k, 3, 1, 1 + 9 k, 1, 1, 14 + 36 k, 1, 1, -3 10 4 + 9 k, 1, 3, 6 + 9 k, 1, 1, 32 + 36 k} 1 -3 10 {1, 3, 5 + 9 k, 108 + 144 k, 8 + 9 k, 3, 1, 9 + 9 k, -4 16 180 + 144 k, 12 + 9 k} showing quasiperiods 10, 18, and 1. The argument 69 is how many continued fraction terms to use, and should exceed thrice the expected longest quasiperiod. If h fails to be Hurwitz, the function hursig (below) will just find longer and longer quasiperiods for increasing values of 69. We yet lack a proven bound for how many matrices to try, and are just using a,|b|,|c| ≤ Δ, but we'll know if we miss any because Julian proved his prediction. Here is our code: Clear[hurcanon]; hurcanon[L_List] := Block[{v = Variables[L][[1]]}, First[Sort[ NestList[ Expand[If[ FreeQ[# /. k -> -1, _?(# < 0 &)], # /. k -> k - 1, #] &[ kRotateLeft[#, 1]]] &, #, Length[#] - 1]]] &[ Expand[L /. v -> v + Max[Ceiling[ Solve[# == 0][[1, 1, 2]] & /@ Select[L, Not[NumberQ[#]] &]]]]]] kRotateLeft[L_, n_] := Join[Drop[L, n], Take[L, n] /. k -> k + 1] trailing0s[L_List] := If[(Equal @@ L && (L == {} || L[[1]] == 0)), Length[L], Length[L] - Position[L, Except[0], 1][[-1, 1]]] Clear[hurperiod]; hurperiod[L_List] := Ordering[Table[ trailing0s[ Drop[L, 2*k] - 2*Drop[Drop[L, k], -k] + Drop[L, -2*k]], {k, Floor[Length[L]/3]}], -1][[1]] Clear[hursig]; hursig[L_List] := Block[{per = hurperiod[L]}, hurcanon[k*(Take[L, {-per - 1, -2}] - Take[L, {-2*per - 1, -2 - per}]) + Take[L, {-per - 1, -2}]]] hursigs[h_?NumericQ, terms_Integer, det_?NumericQ, rang_: Hold[]] := (Print[#1]; #2) & @@ Timing[Block[{sigs = {}, range = {ReleaseHold[rang], Abs[det]}[[1]]}, Do[If[IntegerQ[(b*c + det)/a] && (a*h + b)/(c*h + (b*c + det)/a) > 0, Block[{sig = hursig[ContinuedFraction[(a*h + b)/(c*h + (b*c + det)/a), terms]]}, If[Not[MemberQ[sigs, {_, _, sig}]], PrependTo[ sigs, {MatrixForm[{{a, b}, {c, (b*c + det)/a}}], Length[sig], sig}]]]], {a, 1, range}, {b, -range, range}, {c, -range, range}]; {Length[sigs], MatrixForm[sigs]}]] Here is Julian' proof of σ(|Δ|) distinct signatures for det = Δ We first note that we can make the lower-left entry smaller by adding a term: In[217]:= {{a, b}, {c, d}} == {{b, r}, {d, s}}.{{q, 1}, {1, 0}} /. {q -> Floor[c/d], r -> a - b*Floor[c/d], s -> c - d*Floor[c/d]} Out[217]= True so by induction {{a,b},{c,d}}=={{A,B},{C,0}}.<CF matrices>, and we need only consider numbers of the form (a*x+b)/c. Note that this allows negative terms, so we need the lemma that a negative term can be assumed to be the first term without changing the tail. Next, a only matters mod b: In[283]:= {{a, b}, {c, 0}}.{{0, 1}, {1, 0}}.{{x, 1}, {1, 0}} Out[283]= {{a + b x, b}, {c, 0}} Then, for a given determinant ∆, the number of possible tails is at most the number of {{a,b},{c,0}} with determinant ±∆ (since the CF terms contribute a ±1) and b>0 (negating the matrix does not affect what the transformation is), where a is considered mod b. Since bc=±∆ b divides ∆, and since each b can be paired with b different a's and two different c's, the number is at most twice the sum of the divisors of ∆. But we also have that In[284]:= {{a, b}, {c, 0}}.{{-1, 1}, {1, 0}}.{{1, 1}, {1, 0}}.{{-1, 1}, {1, 0}} Out[284]= {{-a, b}, {-c, 0}} so (a,b,c) is the same as (-a,b,-c), and we can assume c positive, for a bound of σ(∆). But are these all different? Suppose that two were the same, so that there would be a unimodular matrix relating them: In[289]:= {{p, q}, {r, s}} /. Solve[{{a, b}, {c, 0}}.{{p, q}, {r, s}} == {{d, e}, {f, 0}}, {p, q, r, s}][[1]] Out[289]= {{f/c, 0}, {-((-c d + a f)/(b c)), e/b}} Since e/b and f/c have to be integers, and ef=±bc (determinants), e=±b and f=±c. Then (af-cd)/(bc) being an integer means that either a+d is divisible by b (if f=-c) or a-d is (if f=c). Thus, taking d mod b, we find that {{d,e},{f,0}}={{εa,±b},{εc,0}}, which is an equivalence we have already dealt with. Thus there are exactly σ(∆) different tails for continued fractions of the numbers (ax+b)/(cx+d), with ad-bc=∆ and x is neither rational nor a quadratic irrational (this last comes from eliminating possible identities in which algebraic conditions on x mean that the matrices can be non-obviously equivalent (and equivalent "only" for that particular x)). QED --rwg ACW> For some reason I find this remarkable. It suggests the question: how does one go about searching for interleaved polynomial sequences? On Thu, Sep 6, 2012 at 3:53 PM, Jeffrey Shallit <shallit@uwaterloo.ca <http://gosper.org/webmail/src/compose.php?send_to=shallit%40uwaterloo.ca>>wrote:
As far as I know, nothing is known. I computed thousands of partial> quotients 30 years ago, but there was no simple pattern I could detect.>>> On 9/5/12 3:17 PM, Allan Wechsler wrote:>>> What is known about the simple continued fraction expansion of exp(3)?>> Obviously we can generate it fairly easily, but I want to know if there>> are>> any known patterns or periodicities in the terms. I thought exp(3) was a>> known Hurwitz number (continued fraction consists of interleaved>> polynomials) but I can't see any obvious patterns.>> ______________________________**_________________