[math-fun] Inverse Newman iteration
In[1106]:= NestList[2*Ceiling[1/#] - 1 - 1/# &, 3/8, 22] Out[1106]= {3/8, 7/3, 4/7, 5/4, 1/5, 4, 3/4, 5/3, 2/5, 5/2, 3/5, 4/3, 1/4, 3, 2/3, 3/2, 1/3, 2, 1/2, 1, 0, Indeterminate, Indeterminate} So 3/8 is the "20th rational". The 68th iterate on √2: In[1127]:= ContinuedFraction[ Nest[Simplify[2*Ceiling[1/#] - 1 - 1/#] &, Sqrt[2], 68]] Out[1127]= {1, 1, 1, 1, 1, 1, 1, 1, 1, {2}} I.e., it tries to disguise √2 as the golden ratio by sticking nine 1s on the front. Many other iterates of this process produce CFs with only 1s and 2s. --rwg
Iterating on tanh(1) produces bursts with constant preamble term sum: In[1120]:= ColumnForm[ContinuedFraction[#, 11] & /@ NestList[FullSimplify[2*Ceiling[1/#] - 1 - 1/#] &, Tanh[1], 69]] Out[1120]={ {{0, 1, 3, 5, 7, 9, 11, 13, 15, 17, 19}}, {{1, 1, 2, 5, 7, 9, 11, 13, 15, 17, 19}}, {{0, 2, 2, 5, 7, 9, 11, 13, 15, 17, 19}}, {{2, 1, 1, 5, 7, 9, 11, 13, 15, 17, 19}}, {{0, 1, 1, 1, 1, 5, 7, 9, 11, 13, 15}}, {{1, 2, 1, 5, 7, 9, 11, 13, 15, 17, 19}}, {{0, 3, 1, 5, 7, 9, 11, 13, 15, 17, 19}}, {{3, 6, 7, 9, 11, 13, 15, 17, 19, 21, 23}}, {{0, 1, 2, 6, 7, 9, 11, 13, 15, 17, 19}}, {{1, 1, 1, 6, 7, 9, 11, 13, 15, 17, 19}}, {{0, 2, 1, 6, 7, 9, 11, 13, 15, 17, 19}}, {{2, 7, 7, 9, 11, 13, 15, 17, 19, 21, 23}}, {{0, 1, 1, 7, 7, 9, 11, 13, 15, 17, 19}}, {{1, 8, 7, 9, 11, 13, 15, 17, 19, 21, 23}}, {{0, 9, 7, 9, 11, 13, 15, 17, 19, 21, 23}}, {{9, 1, 6, 9, 11, 13, 15, 17, 19, 21, 23}}, {{0, 1, 8, 1, 6, 9, 11, 13, 15, 17, 19}}, {{1, 1, 7, 1, 6, 9, 11, 13, 15, 17, 19}}, {{0, 2, 7, 1, 6, 9, 11, 13, 15, 17, 19}}, {{2, 1, 6, 1, 6, 9, 11, 13, 15, 17, 19}}, {{0, 1, 1, 1, 6, 1, 6, 9, 11, 13, 15}}, {{1, 2, 6, 1, 6, 9, 11, 13, 15, 17, 19}}, {{0, 3, 6, 1, 6, 9, 11, 13, 15, 17, 19}}, {{3, 1, 5, 1, 6, 9, 11, 13, 15, 17, 19}}, {{0, 1, 2, 1, 5, 1, 6, 9, 11, 13, 15}}, {{1, 1, 1, 1, 5, 1, 6, 9, 11, 13, 15}}, {{0, 2, 1, 1, 5, 1, 6, 9, 11, 13, 15}}, {{2, 2, 5, 1, 6, 9, 11, 13, 15, 17, 19}}, {{0, 1, 1, 2, 5, 1, 6, 9, 11, 13, 15}}, {{1, 3, 5, 1, 6, 9, 11, 13, 15, 17, 19}}, {{0, 4, 5, 1, 6, 9, 11, 13, 15, 17, 19}}, {{4, 1, 4, 1, 6, 9, 11, 13, 15, 17, 19}}, {{0, 1, 3, 1, 4, 1, 6, 9, 11, 13, 15}}, {{1, 1, 2, 1, 4, 1, 6, 9, 11, 13, 15}}, {{0, 2, 2, 1, 4, 1, 6, 9, 11, 13, 15}}, {{2, 1, 1, 1, 4, 1, 6, 9, 11, 13, 15}}, {{0, 1, 1, 1, 1, 1, 4, 1, 6, 9, 11}}, {{1, 2, 1, 1, 4, 1, 6, 9, 11, 13, 15}}, {{0, 3, 1, 1, 4, 1, 6, 9, 11, 13, 15}}, {{3, 2, 4, 1, 6, 9, 11, 13, 15, 17, 19}}, {{0, 1, 2, 2, 4, 1, 6, 9, 11, 13, 15}}, {{1, 1, 1, 2, 4, 1, 6, 9, 11, 13, 15}}, {{0, 2, 1, 2, 4, 1, 6, 9, 11, 13, 15}}, {{2, 3, 4, 1, 6, 9, 11, 13, 15, 17, 19}}, {{0, 1, 1, 3, 4, 1, 6, 9, 11, 13, 15}}, {{1, 4, 4, 1, 6, 9, 11, 13, 15, 17, 19}}, {{0, 5, 4, 1, 6, 9, 11, 13, 15, 17, 19}}, {{5, 1, 3, 1, 6, 9, 11, 13, 15, 17, 19}}, {{0, 1, 4, 1, 3, 1, 6, 9, 11, 13, 15}}, {{1, 1, 3, 1, 3, 1, 6, 9, 11, 13, 15}}, {{0, 2, 3, 1, 3, 1, 6, 9, 11, 13, 15}}, {{2, 1, 2, 1, 3, 1, 6, 9, 11, 13, 15}}, {{0, 1, 1, 1, 2, 1, 3, 1, 6, 9, 11}}, {{1, 2, 2, 1, 3, 1, 6, 9, 11, 13, 15}}, {{0, 3, 2, 1, 3, 1, 6, 9, 11, 13, 15}}, {{3, 1, 1, 1, 3, 1, 6, 9, 11, 13, 15}}, {{0, 1, 2, 1, 1, 1, 3, 1, 6, 9, 11}}, {{1, 1, 1, 1, 1, 1, 3, 1, 6, 9, 11}}, {{0, 2, 1, 1, 1, 1, 3, 1, 6, 9, 11}}, {{2, 2, 1, 1, 3, 1, 6, 9, 11, 13, 15}}, {{0, 1, 1, 2, 1, 1, 3, 1, 6, 9, 11}}, {{1, 3, 1, 1, 3, 1, 6, 9, 11, 13, 15}}, {{0, 4, 1, 1, 3, 1, 6, 9, 11, 13, 15}}, {{4, 2, 3, 1, 6, 9, 11, 13, 15, 17, 19}}, {{0, 1, 3, 2, 3, 1, 6, 9, 11, 13, 15}}, {{1, 1, 2, 2, 3, 1, 6, 9, 11, 13, 15}}, {{0, 2, 2, 2, 3, 1, 6, 9, 11, 13, 15}}, {{2, 1, 1, 2, 3, 1, 6, 9, 11, 13, 15}}, {{0, 1, 1, 1, 1, 2, 3, 1, 6, 9, 11}}, {{1, 2, 1, 2, 3, 1, 6, 9, 11, 13, 15}}} --rwg On Sat, Oct 5, 2013 at 6:20 PM, Bill Gosper <billgosper@gmail.com> wrote:
In[1106]:= NestList[2*Ceiling[1/#] - 1 - 1/# &, 3/8, 22]
Out[1106]= {3/8, 7/3, 4/7, 5/4, 1/5, 4, 3/4, 5/3, 2/5, 5/2, 3/5, 4/3, 1/4, 3, 2/3, 3/2, 1/3, 2, 1/2, 1, 0, Indeterminate, Indeterminate}
So 3/8 is the "20th rational".
The 68th iterate on √2: In[1127]:= ContinuedFraction[ Nest[Simplify[2*Ceiling[1/#] - 1 - 1/#] &, Sqrt[2], 68]]
Out[1127]= {1, 1, 1, 1, 1, 1, 1, 1, 1, {2}}
I.e., it tries to disguise √2 as the golden ratio by sticking nine 1s on the front. Many other iterates of this process produce CFs with only 1s and 2s. --rwg
Is anything known about the growth of this function? In[1130]:= NestWhile[{2*Ceiling[1/#[[1]]] - 1 - 1/#[[1]], #[[2]] + 1} &, {3/8, 0}, #[[1]] != 0 &] Out[1130]= {0, 20} In[1131]:= NestWhile[{2*Ceiling[1/#[[1]]] - 1 - 1/#[[1]], #[[2]] + 1} &, {22/7, 0}, #[[1]] != 0 &] Out[1131]= {0, 519} In[1132]:= NestWhile[{2*Ceiling[1/#[[1]]] - 1 - 1/#[[1]], #[[2]] + 1} &, {355/113, 0}, #[[1]] != 0 &] Out[1132]= {0, 67107847} Checks: In[1133]:= Timing[ NestWhile[{1/(2*Floor[#[[1]]] + 1 - #[[1]]), #[[2]] + 1} &, {0, 0}, #[[1]] != 22/7 &]] Out[1133]= {0.005219, {22/7, 519}} In[1134]:= Timing[ NestWhile[{1/(2*Floor[#[[1]]] + 1 - #[[1]]), #[[2]] + 1} &, {0, 0}, #[[1]] != 355/113 &]] Out[1134]= {700.483896, {355/113, 67107847}} --rwg On Sat, Oct 5, 2013 at 6:20 PM, Bill Gosper <billgosper@gmail.com> wrote:
In[1106]:= NestList[2*Ceiling[1/#] - 1 - 1/# &, 3/8, 22]
Out[1106]= {3/8, 7/3, 4/7, 5/4, 1/5, 4, 3/4, 5/3, 2/5, 5/2, 3/5, 4/3, 1/4, 3, 2/3, 3/2, 1/3, 2, 1/2, 1, 0, Indeterminate, Indeterminate}
So 3/8 is the "20th rational".
The 68th iterate on √2: In[1127]:= ContinuedFraction[ Nest[Simplify[2*Ceiling[1/#] - 1 - 1/#] &, Sqrt[2], 68]]
Out[1127]= {1, 1, 1, 1, 1, 1, 1, 1, 1, {2}}
I.e., it tries to disguise √2 as the golden ratio by sticking nine 1s on the front. Many other iterates of this process produce CFs with only 1s and 2s. --rwg
Apparently, _Rational is an illegal Mma compiler type, let alone _Integer|_Rational, but taking the trouble to rewrite it in integers, In[1192]:= Compile[{{N, _Integer}, {D, _Integer}}, Module[{n = N, d = D, k = 0}, While[n > 0, ++k; {n, d} = {2*n*Ceiling[d/n] - n - d, n}]; k], CompilationTarget :> "C"] Out[1192]= CompiledFunction[] In[1194]:= Timing[%1192[355, 113]] Out[1194]= {4.614657, 67107847} Compare with %1134 below. --rwg I was under the delusion of needing {n,d}={n,d}/GCD[n,d] in the loop. This is an error because you can't(?) specify integer divide, and {n,d}=Floor[{n,d}/GCD[n,d]] is exorbitant. Lucky it was a delusion. On Sat, Oct 5, 2013 at 9:43 PM, Bill Gosper <billgosper@gmail.com> wrote:
Is anything known about the growth of this function? In[1130]:= NestWhile[{2*Ceiling[1/#[[1]]] - 1 - 1/#[[1]], #[[2]] + 1} &, {3/8, 0}, #[[1]] != 0 &]
Out[1130]= {0, 20}
In[1131]:= NestWhile[{2*Ceiling[1/#[[1]]] - 1 - 1/#[[1]], #[[2]] + 1} &, {22/7, 0}, #[[1]] != 0 &]
Out[1131]= {0, 519}
In[1132]:= NestWhile[{2*Ceiling[1/#[[1]]] - 1 - 1/#[[1]], #[[2]] + 1} &, {355/113, 0}, #[[1]] != 0 &]
Out[1132]= {0, 67107847}
Checks:
In[1133]:= Timing[ NestWhile[{1/(2*Floor[#[[1]]] + 1 - #[[1]]), #[[2]] + 1} &, {0, 0}, #[[1]] != 22/7 &]]
Out[1133]= {0.005219, {22/7, 519}}
In[1134]:= Timing[ NestWhile[{1/(2*Floor[#[[1]]] + 1 - #[[1]]), #[[2]] + 1} &, {0, 0}, #[[1]] != 355/113 &]]
Out[1134]= {700.483896, {355/113, 67107847}} --rwg
On Sat, Oct 5, 2013 at 6:20 PM, Bill Gosper <billgosper@gmail.com> wrote:
In[1106]:= NestList[2*Ceiling[1/#] - 1 - 1/# &, 3/8, 22]
Out[1106]= {3/8, 7/3, 4/7, 5/4, 1/5, 4, 3/4, 5/3, 2/5, 5/2, 3/5, 4/3, 1/4, 3, 2/3, 3/2, 1/3, 2, 1/2, 1, 0, Indeterminate, Indeterminate}
So 3/8 is the "20th rational".
The 68th iterate on √2: In[1127]:= ContinuedFraction[ Nest[Simplify[2*Ceiling[1/#] - 1 - 1/#] &, Sqrt[2], 68]]
Out[1127]= {1, 1, 1, 1, 1, 1, 1, 1, 1, {2}}
I.e., it tries to disguise √2 as the golden ratio by sticking nine 1s on the front. Many other iterates of this process produce CFs with only 1s and 2s. --rwg
Some empirical observations: f(n) = 2^n-1 f(1/n) = 2^(n-1) f(1-1/n) = 2^n-2 f(n/(2*n+1)) = 2^(n+2)-4 f(n-1/n) = 1/2 (-2 - 2^n + 2^(2 n)) f(n+1/n) = 1/2 (-2 + 2^(2 n) + 2^(1 + n)) f(fib(n+1)/fib(n)) = (9*2^n+2^-n-4)/12 f(fib(n)/fib(n+1)) = (9*2^n-2^-n-8)/12 f(nth convergent(√3)) = 1/56 (-40 + 2^(3 n/2) (13 + 12 Sqrt[2] + (-1)^n (13 - 12 Sqrt[2]))) But for ratios of g[n] = g[n-2]+g[n-3], In[1]:= First /@ NestList[{#[[2]], #[[3]], #[[1]] + #[[2]]} &, {1, 1, 1}, 33] Out[1]= {1, 1, 1, 2, 2, 3, 4, 5, 7, 9, 12, 16, 21, 28, 37, 49, 65, 86, 114, 151, 200, 265, 351, 465, 616, 816, 1081, 1432, 1897, 2513, 3329, 4410, 5842, 7739} In[5]:= nam[Numerator[#], Denominator[#]] & /@Ratios[%1] Out[5]= {1, 1, 3, 1, 5, 9, 17, 25, 49, 9, 9, 497, 9, 8177, 65521, 1048561, 49137, 262129, 327665, 589809, 131057, 1638385, 458737, 3342321, 196593, 7012337, 50528241, 65208305, 1245169, 532873201, 8588034033, 61014001, 2153971697} (four 9s because of four 4/3s in the ratios) Note that f(fib(n)) = 2^fib(n)-1, a double exponential, but f(fib(n+1)/fib(n)) is not. --rwg On Sat, Oct 5, 2013 at 9:43 PM, Bill Gosper <billgosper@gmail.com> wrote:
Is anything known about the growth of this function? In[1130]:= NestWhile[{2*Ceiling[1/#[[1]]] - 1 - 1/#[[1]], #[[2]] + 1} &, {3/8, 0}, #[[1]] != 0 &]
Out[1130]= {0, 20}
In[1131]:= NestWhile[{2*Ceiling[1/#[[1]]] - 1 - 1/#[[1]], #[[2]] + 1} &, {22/7, 0}, #[[1]] != 0 &]
Out[1131]= {0, 519}
In[1132]:= NestWhile[{2*Ceiling[1/#[[1]]] - 1 - 1/#[[1]], #[[2]] + 1} &, {355/113, 0}, #[[1]] != 0 &]
Out[1132]= {0, 67107847}
Checks:
In[1133]:= Timing[ NestWhile[{1/(2*Floor[#[[1]]] + 1 - #[[1]]), #[[2]] + 1} &, {0, 0}, #[[1]] != 22/7 &]]
Out[1133]= {0.005219, {22/7, 519}}
In[1134]:= Timing[ NestWhile[{1/(2*Floor[#[[1]]] + 1 - #[[1]]), #[[2]] + 1} &, {0, 0}, #[[1]] != 355/113 &]]
Out[1134]= {700.483896, {355/113, 67107847}} --rwg
On Sat, Oct 5, 2013 at 6:20 PM, Bill Gosper <billgosper@gmail.com> wrote:
In[1106]:= NestList[2*Ceiling[1/#] - 1 - 1/# &, 3/8, 22]
Out[1106]= {3/8, 7/3, 4/7, 5/4, 1/5, 4, 3/4, 5/3, 2/5, 5/2, 3/5, 4/3, 1/4, 3, 2/3, 3/2, 1/3, 2, 1/2, 1, 0, Indeterminate, Indeterminate}
So 3/8 is the "20th rational".
The 68th iterate on √2: In[1127]:= ContinuedFraction[ Nest[Simplify[2*Ceiling[1/#] - 1 - 1/#] &, Sqrt[2], 68]]
Out[1127]= {1, 1, 1, 1, 1, 1, 1, 1, 1, {2}}
I.e., it tries to disguise √2 as the golden ratio by sticking nine 1s on the front. Many other iterates of this process produce CFs with only 1s and 2s. --rwg
Correcting f(fib(n+1)/fib(n)) and f(fib(n)/fib(n+1)) On Mon, Oct 7, 2013 at 1:31 PM, Bill Gosper <billgosper@gmail.com> wrote:
Some empirical observations: f(n) = 2^n-1 f(1/n) = 2^(n-1) f(1-1/n) = 2^n-2 f(n/(2*n+1)) = 2^(n+2)-4 f(n-1/n) = 1/2 (-2 - 2^n + 2^(2 n)) f(n+1/n) = 1/2 (-2 + 2^(2 n) + 2^(1 + n))
f(fib(n+1)/fib(n)) = 1/12 (-4 + (-2)^n + 9 2^n) f(fib(n)/fib(n+1)) = 1/12 (-8 - (-2)^n + 9 2^n) f(nth convergent(√3)) = 1/56 (-40 + 2^(3 n/2) (13 + 12 Sqrt[2] + (-1)^n (13 - 12 Sqrt[2])))
But for ratios of g[n] = g[n-2]+g[n-3], In[1]:= First /@ NestList[{#[[2]], #[[3]], #[[1]] + #[[2]]} &, {1, 1, 1}, 33]
Out[1]= {1, 1, 1, 2, 2, 3, 4, 5, 7, 9, 12, 16, 21, 28, 37, 49, 65, 86, 114, 151, 200, 265, 351, 465, 616, 816, 1081, 1432, 1897, 2513, 3329, 4410, 5842, 7739}
In[5]:= nam[Numerator[#], Denominator[#]] & /@Ratios[%1]
Out[5]= {1, 1, 3, 1, 5, 9, 17, 25, 49, 9, 9, 497, 9, 8177, 65521, 1048561, 49137, 262129, 327665, 589809, 131057, 1638385, 458737, 3342321, 196593, 7012337, 50528241, 65208305, 1245169, 532873201, 8588034033, 61014001, 2153971697}
(four 9s because of four 4/3s in the ratios) Note that f(fib(n)) = 2^fib(n)-1, a double exponential, but f(fib(n+1)/fib(n)) is not. --rwg
On Sat, Oct 5, 2013 at 9:43 PM, Bill Gosper <billgosper@gmail.com> wrote:
Is anything known about the growth of this function? In[1130]:= NestWhile[{2*Ceiling[1/#[[1]]] - 1 - 1/#[[1]], #[[2]] + 1} &, {3/8, 0}, #[[1]] != 0 &]
Out[1130]= {0, 20}
In[1131]:= NestWhile[{2*Ceiling[1/#[[1]]] - 1 - 1/#[[1]], #[[2]] + 1} &, {22/7, 0}, #[[1]] != 0 &]
Out[1131]= {0, 519}
In[1132]:= NestWhile[{2*Ceiling[1/#[[1]]] - 1 - 1/#[[1]], #[[2]] + 1} &, {355/113, 0}, #[[1]] != 0 &]
Out[1132]= {0, 67107847}
Checks:
In[1133]:= Timing[ NestWhile[{1/(2*Floor[#[[1]]] + 1 - #[[1]]), #[[2]] + 1} &, {0, 0}, #[[1]] != 22/7 &]]
Out[1133]= {0.005219, {22/7, 519}}
In[1134]:= Timing[ NestWhile[{1/(2*Floor[#[[1]]] + 1 - #[[1]]), #[[2]] + 1} &, {0, 0}, #[[1]] != 355/113 &]]
Out[1134]= {700.483896, {355/113, 67107847}} --rwg
On Sat, Oct 5, 2013 at 6:20 PM, Bill Gosper <billgosper@gmail.com> wrote:
In[1106]:= NestList[2*Ceiling[1/#] - 1 - 1/# &, 3/8, 22]
Out[1106]= {3/8, 7/3, 4/7, 5/4, 1/5, 4, 3/4, 5/3, 2/5, 5/2, 3/5, 4/3, 1/4, 3, 2/3, 3/2, 1/3, 2, 1/2, 1, 0, Indeterminate, Indeterminate}
So 3/8 is the "20th rational".
The 68th iterate on √2: In[1127]:= ContinuedFraction[ Nest[Simplify[2*Ceiling[1/#] - 1 - 1/#] &, Sqrt[2], 68]]
Out[1127]= {1, 1, 1, 1, 1, 1, 1, 1, 1, {2}}
I.e., it tries to disguise √2 as the golden ratio by sticking nine 1s on the front. Many other iterates of this process produce CFs with only 1s and 2s. --rwg
participants (1)
-
Bill Gosper