A228488 -id:A228488 - cp's OEIS frontend

A228469 a(n) = 6*a(n-2) + a(n-4), where a(0) = 2, a(1) = 8, a(2) = 13, a(3) = 49.

2, 8, 13, 49, 80, 302, 493, 1861, 3038, 11468, 18721, 70669, 115364, 435482, 710905, 2683561, 4380794, 16536848, 26995669, 101904649, 166354808, 627964742, 1025124517, 3869693101, 6317101910, 23846123348, 38927735977, 146946433189, 239883517772, 905524722482

Offset: 0

Clark Kimberling, Aug 22 2013

The classical Euclidean algorithm iterates the mapping u(x,y) = (y, (x mod y)) until reaching g = GCD(x,y) in a pair ( . , g).  In much the same way, the modified  algorithm (A228247) iterates the mapping v(x,y) = (y, y - (x mod y)).  The accelerated Euclidean algorithm uses w(x,y) = min(u(x,y),v(x,y)).  Let s(x,y) be the number of applications of u, starting with (x,y) -> u(x,y) needed to reach ( . , g), and let u'(x,y) be the number of applications of w to reach ( . , g).  Then u'(x,y) <= u(x,y) for all (x,y).
Starting with a pair (x,y), at each application of w, record 0 if w( . , . ) = u( . , . ) and 1 otherwise.  The trace of (x,y), denoted by trace(x,y), is the resulting 01 word, whose length is the total number of applications of w.
Conjecture:  a(n) is the least positive integer c for which there is a positive integer b for which trace(b,c) consists of the first n letters of 01010101010101...

			a(3) = 13 because trace(18/13) = 010, and 13 is the least c for which there is a number b such that trace(b/c) = 010.  Successive applications of w are indicated by (18,13)->(13,5)->(5,2)->(2,1).  Whereas w finds GCD in 3 steps, u takes 4 steps, as indicated by (18,3)->(13,5)->(5,3)->(3,2)->(2,1).

Clark Kimberling, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (0,6,0,1).

Cf. A179237 (bisection), A228470, A228471, A228487, A228488.

c1 = CoefficientList[Series[(2 + 8 x + x^2 + x^3)/(1 - 6 x^2 - x^4), {x, 0, 40}], x]; c2 = CoefficientList[Series[(3 + 11 x + 2 x^3)/(1 - 6 x^2 - x^4), {x, 0, 40}], x]; pairs = Transpose[CoefficientList[Series[{-((3 + 11 x + 2 x^3)/(-1 + 6 x^2 + x^4)), -((2 + 8 x + x^2 + x^3)/(-1 + 6 x^2 + x^4))}, {x, 0, 20}], x]]; t[{x_, y_, }] := t[{x, y}]; t[{x, y_}] := Prepend[If[# > y - #, {y - #, 1}, {#, 0}], y] &[Mod[x, y]]; userIn2[{x_, y_}] := Most[NestWhileList[t, {x, y}, (#[[2]] > 0) &]]; Map[Map[#[[3]] &, Rest[userIn2[#]]] &, pairs] (* Peter J. C. Moses, Aug 20 2013 *)
LinearRecurrence[{0, 6, 0, 1}, {2, 8, 13, 49}, 30] (* T. D. Noe, Aug 23 2013 *)

Vec((x^3+x^2+8*x+2)/(1-6*x^2-x^4)+O(x^99)) \\ Charles R Greathouse IV, Jun 12 2015

G.f.: (x^3 + x^2 + 8*x + 2)/(1 - 6*x^2 - x^4). - Ralf Stephan, Aug 24 2013

A228471 a(n) = 6*a(n-2) + a(n-4), where a(0) = 3, a(1) = 5, a(2) = 19, a(3) = 31.

Original entry on oeis.org

3, 5, 19, 31, 117, 191, 721, 1177, 4443, 7253, 27379, 44695, 168717, 275423, 1039681, 1697233, 6406803, 10458821, 39480499, 64450159, 243289797, 397159775, 1499219281, 2447408809, 9238605483, 15081612629, 56930852179, 92937084583, 350823718557, 572704120127

Offset: 0

Clark Kimberling, Aug 22 2013

The classical Euclidean algorithm iterates the mapping u(x,y) = (y, (x mod y)) until reaching g = GCD(x,y) in a pair ( . , g). In much the same way, the modified algorithm (A228247) iterates the mapping v(x,y) = (y, y - (x mod y)). The accelerated Euclidean algorithm uses w(x,y) = min(u(x,y),v(x,y)). Let s(x,y) be the number of applications of u, starting with (x,y) -> u(x,y) needed to reach ( . , g), and let u'(x,y) be the number of applications of w to reach ( . , g). Then u'(x,y) <= u(x,y) for all (x,y).

Conjecture: a(n) is the least positive integer c for which there is a positive integer b for which trace(b,c) consists of the first n letters of 101010101010101..., where "trace" is as defined at A228469.

			a(3) = 19 because trace(30/19) = 101, and 19 is the least c for which there is a number b such that trace(b/c) = 101. Successive applications of w are indicated by (30,19)->(19,11)->(11,3)->(3,1). Whereas w finds GCD in 3 steps, u takes 5 steps, as indicated by (30,19)->(19,11)->(11,8)->(8,3)->(3,2)->(2,1).

Clark Kimberling, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (0,6,0,1).

Cf. A228469, A228470, A228487, A228488.

c1 = CoefficientList[Series[(3 + 5 x + x^2 + x^3)/(1 - 6 x^2 - x^4), {x, 0, 40}], x]; c2 = CoefficientList[Series[(5 + 8 x + x^3)/(1 - 6 x^2 - x^4), {x, 0, 40}], x]; pairs = Transpose[CoefficientList[Series[{-((3 + 11 x + 2 x^3)/(-1 + 6 x^2 + x^4)), -((2 + 8 x + x^2 + x^3)/(-1 + 6 x^2 + x^4))}, {x, 0, 20}], x]]; t[{x_, y_, }] := t[{x, y}]; t[{x, y_}] := Prepend[If[# > y - #, {y - #, 1}, {#, 0}], y] &[Mod[x, y]]; userIn2[{x_, y_}] := Most[NestWhileList[t, {x, y}, (#[[2]] > 0) &]]; Map[Map[#[[3]] &, Rest[userIn2[#]]] &, pairs] (* Peter J. C. Moses, Aug 20 2013 *)
LinearRecurrence[{0, 6, 0, 1}, {3, 5, 19, 31}, 30] (* T. D. Noe, Aug 23 2013 *)

G.f.: (3 + 5*x + x^2 + x^3)/(1 - 6*x^2 - x^4). - Peter J. C. Moses, Aug 20 2013 - from Mathematica code

A228489 Period of trace(n*tau), where tau = (1+sqrt(5))/2 = golden ratio.

Original entry on oeis.org

1, 1, 1, 1, 1, 4, 1, 1, 2, 4, 1, 1, 1, 6, 3, 1, 2, 1, 1, 10, 1, 8, 6, 1, 9, 4, 10, 8, 1, 18, 1, 6, 6, 1, 13, 1, 4, 1, 3, 10, 4, 4, 12, 6, 17, 1, 1, 1, 18, 21, 8, 10, 6, 8, 1, 8, 12, 4, 16, 16, 3, 6, 1, 14, 9, 14, 20, 1, 6, 36, 18, 1, 4, 13, 26, 1, 12, 20, 20

Offset: 0

Clark Kimberling, Aug 23 2013

nonn

It is assumed that trace(n*tau) is purely periodic, as conjectured at A228487 where trace is defined.

			a(6) = 4 because the trace(6*tau) = 1001 (repeated) has period 4.
   n  trace(n*tau)
   -  ------------
   1  000000000...
   2  111111111...
   3  000000000...
   4  000000000...
   5  000000000...
   6  1001 (repeated)
   7  000000000...
   8  111111111...
   9  10 (repeated)
  10  0100 (repeated)
  14  110011 (repeated)
  17  10 (repeated)
  20  0101010010 (repeated)
  30  101000111111001010 (repeated)
  31  000000000...
  35  1100101010011 (repeated)

Cf. A228487, A228488.

$MaxExtraPrecision = Infinity; period[seq_] := (If[Last[#1] == {} || Length[#1] == Length[seq] - 1, 0, Length[#1]] &)[NestWhileList[Rest, Rest[seq], #1 != Take[seq, Length[#1]] &, 1]]; periodicityReport[seq_] := ({Take[seq, Length[seq] - Length[#1]], period[#1], Take[#1, period[#1]]} &)[Take[seq, -Length[NestWhile[Rest[#1] &, seq, period[#1] == 0 &, 1, Length[seq]]]]]
(*output format {initial segment,period length,period}*)
t[{x_, y_, }] := t[{x, y}]; t[{x, y_}] := Prepend[If[# > y - #, {y - #, 1}, {#, 0}], y] &[Mod[x, y]]; userIn2[{x_, y_}] := Most[NestWhileList[t, {x, y}, (#[[2]] > 0) &]];
z = 160; pr = Table[p = Convergents[n*GoldenRatio, z];  pairs = Table[{Numerator[#], Denominator[#]} &[p[[k]]], {k, 1, z}]; periodicityReport[Most[Last[Map[Map[#[[3]] &, Rest[userIn2[#]]] &, pairs]]]], {n, 200}]
m = Map[#[[2]] &, pr]   (* Peter J. C. Moses, Aug 22 2013 *)

A228668 Array: row n consists of n-th nonsquare f(n) followed by L(CF(sqrt(f(n)))) followed by L(ACF(sqrt(f(n)))), where L indicates the length of the repeating string; CF indicates continued fraction, and ACF indicates accelerated continued fraction.

Original entry on oeis.org

2, 1, 1, 3, 2, 2, 5, 1, 1, 6, 2, 2, 7, 2, 4, 8, 2, 2, 10, 1, 1, 11, 2, 2, 12, 2, 2, 13, 3, 5, 14, 2, 4, 15, 2, 2, 17, 1, 1, 18, 2, 2, 19, 4, 6, 20, 2, 2, 21, 4, 6, 22, 4, 6, 23, 2, 4, 24, 2, 2, 26, 1, 1, 27, 2, 2, 28, 4, 4, 29, 8, 5, 30, 2, 2, 31, 6, 8, 32

Offset: 1

Clark Kimberling, Aug 29 2013

See A228667 for the definition of accelerated continued fraction.

			The initial 2,1,1 means that both the ACF and CF of sqrt(2) have repeating strings of length 1; the next 3,2,2 means that the ACF and CF of sqrt(3) have repeating strings of length 2 and 2.  In the table below, Mathematica notation is used for repeating continued fractions; x(n) approximates sqrt(n)-ACF(sqrt(n)) and y(n) approximates sqrt(n)-CF(sqrt(n)).
n . ACF(sqrt(n)) . x(n) ........... CF(sqrt(n)) ... y(n)
2 . {1,{2}} ..... -0.32 ........... {1,{2}} ....... -0.32
3 . {2,{-4,4}} .. -1.3 x 10^(-11) . {1,{1,2}} ..... -7 x 10^(-6)
7 . {3,{-3,6}} .. -5.0 x 10^(-12) . {2,{1,1,1,4}} . -5 x 10^(-6)

Cf. A228668, A228488.

$MaxExtraPrecision = Infinity; period[seq_] := (If[Last[#1] == {} || Length[#1] == Length[seq] - 1, 0, Length[#1]] &)[NestWhileList[Rest, Rest[seq], #1 != Take[seq, Length[#1]] &, 1]]; periodicityReport[seq_] := ({Take[seq, Length[seq] - Length[#1]], period[#1], Take[#1, period[#1]]} &)[Take[seq, -Length[NestWhile[Rest[#1] &, seq, period[#1] == 0 &, 1, Length[seq]]]]]
(*output format {initial seqment,period length,period}*)
(*error messages occur if the sequence not found to be periodic.*)
aCF[rational_] := Module[{steps = {}, stop = False, i = 0, x = Numerator[rational], y = Denominator[rational], w, u, v, f, c},(*Step 1*)w = Mod[x, y]; Which[w == 0, c[i] = x/y; stop = True; AppendTo[steps, "A"], 0 < w <= y/2, c[i] = Floor[x/y]; {u, v, f} = {y, w, 1}; AppendTo[steps, "B"], w > y/2, c[i] = 1 + Floor[x/y]; {u, v, f} = {y, y - w, -1};    AppendTo[steps, "C"]];  i++; (*Step 2*)While[stop =!= True, w = Mod[u, v]; Which[f == 1 && w == 0, c[i] = u/v; stop = True; AppendTo[steps, "0.1"], f == -1 && w == 0, c[i] = -u/v; stop = True; AppendTo[steps, "0.2"], f == 1 && w <= v/2, c[i] = Floor[u/v]; {u, v, f} = {v, w, 1}; AppendTo[steps, "1"], f == 1 && w > v/2, c[i] = 1 + Floor[u/v]; {u, v, f} = {v, v - w, -1}; AppendTo[steps, "2"], f == -1 && w <= v/2, c[i] = -Floor[u/v]; {u, v, f} = {v, w, -1}; AppendTo[steps, "3"], f == -1 && w > v/2, c[i] = -1 - Floor[u/v]; {u, v, f} = {v, v - w, -f}; AppendTo[steps, "4"]]; i++]; (*Display results*) {FromContinuedFraction[#], {"Steps", steps}, {"ACF", #}, {"CF", ContinuedFraction[x/y]}} &[Map[c, Range[i] - 1]]]
m = Map[{#, Map[periodicityReport[#][[2]] &, {Drop[#[[1]][[2]], -3],    Drop[#[[2]][[2]], -3]} &[aCF[Rationalize[Sqrt[#], 10^-80]][[{3, 4}]]]]} &, Select[Range[200], ! IntegerQ[Sqrt[#]] &]]
Flatten[m] (* Peter J. C. Moses, Aug 28 2013 *)

cp's OEIS Frontend

A228469 a(n) = 6*a(n-2) + a(n-4), where a(0) = 2, a(1) = 8, a(2) = 13, a(3) = 49.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A228471 a(n) = 6*a(n-2) + a(n-4), where a(0) = 3, a(1) = 5, a(2) = 19, a(3) = 31.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A228489 Period of trace(n*tau), where tau = (1+sqrt(5))/2 = golden ratio.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A228668 Array: row n consists of n-th nonsquare f(n) followed by L(CF(sqrt(f(n)))) followed by L(ACF(sqrt(f(n)))), where L indicates the length of the repeating string; CF indicates continued fraction, and ACF indicates accelerated continued fraction.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica