Re: [math-fun] Pi to 31.4 trilllion digits
[DanA wrote] PS Let me add some afterthoughts: ----- Question: --------- Are there algorithms relating the cfe's of x and y with the cfe of simple functions of x and y like x + y x - y x * y x / y x ^ y —Dan Dan, it's grim: In[257]:= Coth /@ {1/2, 1, 2} Out[257]= {Coth[1/2], Coth[1], Coth[2]} These coths are related by the double angle formula (1+c^2)/2/c. But look at the CFs: In[258]:= ContinuedFraction[#, 5] & /@ % Out[258]= {{2, 6, 10, 14, 18}, {1, 3, 5, 7, 9}, {1, 26, 1, 3, 1}} Coth 2 evidently = 1/2,3/2,5/2,..., but normalizing pseudorandomizes: In[301]:= ContinuedFraction[FromContinuedFraction[{1, 3, 5, 7, 9}/2]] Out[301]= {1, 26, 1, 4, 2, 2, 1, 2} Unlike the linear conversions in my old http://www.tweedledum.com/rwg/cfup.htm, even the spigot conversion of x={2, 6, 10, 14, 18,...} to (1+x^2)/2/x = {1, 3, 5, 7, 9,..} is non finite state: Initialize V(x) to the symbolic expression (1+x^2)/2/x . Input terms via x → 2+1/x, 6+1/x, ... . Output t =⎣V(1)⎦ when it equals ⎣V(∞)⎦. V → 1/(V - t). (This is easy. Try it.) Input and output will strictly alternate until the input of 26 and the output of 13 leaves V = (2 (1654632 + 86200843 x + 1122694538 x^2))/ (229783 + 11709446 x + 149100967 x^2) (!) which can further output 15(!) This was unavoidable. The larger terms of the input contributed information faster than the smaller output terms were removing it. For a conversion to be finite state, the input and output information densities must match exactly. There might be (necessarily non-unique) number representations less efficient than decimal or cf that might reveal number-theoretic secrets. —rwg
On Sun, Mar 17, 2019 at 11:35 AM Bill Gosper <billgosper@gmail.com> wrote:
[DanA wrote] PS Let me add some afterthoughts:
----- Question: --------- Are there algorithms relating the cfe's of x and y with the cfe of simple functions of x and y like
x + y
x - y
x * y
x / y
x ^ y
—Dan
Dan, it's grim:
In[257]:= Coth /@ {1/2, 1, 2}
Out[257]= {Coth[1/2], Coth[1], Coth[2]}
These coths are related by the double angle formula (1+c^2)/2/c. But look at the CFs: In[258]:= ContinuedFraction[#, 5] & /@ %
Out[258]= {{2, 6, 10, 14, 18}, {1, 3, 5, 7, 9}, {1, 26, 1, 3, 1}}
Coth 2 evidently = 1/2,3/2,5/2,..., but normalizing pseudorandomizes:
In[301]:= ContinuedFraction[FromContinuedFraction[{1, 3, 5, 7, 9}/2]]
Out[301]= {1, 26, 1, 4, 2, 2, 1, 2}
Unlike the linear conversions in my old http://www.tweedledum.com/rwg/cfup.htm, even the spigot conversion of x={2, 6, 10, 14, 18,...} to (1+x^2)/2/x = {1, 3, 5, 7, 9,..} is non finite state: Initialize V(x) to the symbolic expression (1+x^2)/2/x . Input terms via x → 2+1/x, 6+1/x, ... . Output t =⎣V(1)⎦ when it equals ⎣V(∞)⎦. V → 1/(V - t). (This is easy. Try it.) Input and output will strictly alternate until the input of 26 and the output of 13 leaves V =
(2 (1654632 + 86200843 x + 1122694538 x^2))/ (229783 + 11709446 x + 149100967 x^2)
(!) which can further output 15(!)
I.e., Input → Output 2 → 1 6 → 3 10 → 5 . . . 26 → 13, 15 without ever reading the pending "30"!
This was unavoidable. The larger terms of the input contributed information faster than the smaller output terms were removing it.
For a conversion to be finite state, the input and output information densities must match exactly.
E.g., in calculating (e+1)/(e-1) = 2, 6, 10, 14, . . . from e = 2, 1, 2, 1, 1, 4, 1, 1, 6, 1, . . ., the V expression (state variable) periodically reaches 1 + 2 x each time it reads 2k 1 1 and outputs 4 k + 2. For k = 4 Out[323]= 1 + 2 x In[324]:= Together[% /. x -> 4 + 1/x] Out[324]= (2 + 9 x)/x In[325]:= Together[% /. x -> 1 + 1/x] Out[325]= (9 + 11 x)/(1 + x) In[326]:= Together[% /. x -> 1 + 1/x] Out[326]= (11 + 20 x)/(1 + 2 x) In[327]:= ∞1@% Out[327]= {10, 10} In[328]:= Together[1/(%% - %[[1]])] Out[328]= 1 + 2 x We can estimate the information content in a term or burst of terms by its (in)frequency according to Gauss-Kuzmin: If a+1/(b+1/c) = z, then the frequency of the burst ...,a,b,c,... is log₂((z+1)²/z/(z+2)). E.g., In[347]:= cfprob /@ {{4, 1, 1}, {1, 1, 4}, {1, 4, 1}, {10}} Out[347]= {Log[154/153]/Log[2], Log[154/153]/Log[2], Log[121/120]/ Log[2], Log[121/120]/Log[2]} More generally, In:= cfprob /@ {{1, k, 1}, {2 k + 2}} {Abs[Log[(1 + (1 + k)/(2 + k))/(1 + (1 + 2 k)/(1 + 2 (1 + k)))]]/Log[2], Abs[Log[(1 + 1/(2 + 2 k))/(1 + 1/(3 + 2 k))]]/Log[2]} In:= FullSimplify[Equal @@ %] True But why {1,k,1} and not {k,1,1} nor {1,1,k}? Gauss-Kuzmin is only part of the story. The information content also depends on how "interesting" it is to its receiver. In an even simpler case, Out[305]= (2 (1 + 2 x))/x converts 2,2,2,... = 1 + √2 to 4,1,4,1,4,... = 2 (1 + √2) In[306]:= ∞1@% Out[306]= {6, 4} In[308]:= Together[%305 /. x -> 2 + 1/x] Out[308]= (2 (2 + 5 x))/(1 + 2 x) In[309]:= ∞1@% Out[309]= {4, 5} In[310]:= Together[%% /. x -> 2 + 1/x] Out[310]= (2 (5 + 12 x))/(2 + 5 x) In[311]:= ∞1@% Out[311]= {4, 4} In[312]:= Together[1/(%% - %[[1]])] Out[312]= (2 + 5 x)/(2 (1 + 2 x)) In[313]:= ∞1@% Out[313]= {1, 1} In[314]:= Together[1/(%% - %[[1]])] Out[314]= (2 (1 + 2 x))/x But neither {4,1} nor {1,4} has the same probability as {2, 2}: In[317]:= cfprob /@ {{2, 2}, 2, {4, 1}, {1, 4}, 5} Out[317]= {Log[50/49]/Log[2], Log[9/8]/Log[2], Log[55/54]/Log[2], Log[55/54]/Log[2], Log[36/35]/Log[2]} How do we construct an invariant here? —rwg
There might be (necessarily non-unique) number representations less efficient than decimal or cf that might reveal number-theoretic secrets. —rwg
participants (1)
-
Bill Gosper