login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A228471 a(n) = 6*a(n-2) + a(n-4), where a(0) = 3, a(1) = 5, a(2) = 19, a(3) = 31. 3
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 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,1

COMMENTS

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.

LINKS

Clark Kimberling, Table of n, a(n) for n = 0..1000

Index entries for linear recurrences with constant coefficients, signature (0,6,0,1).

FORMULA

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

a(n) = (2-1/2*(-1)^n)*((3-sqrt(10))^(1/4*((-1)^n-1)+1/2*n)+(3+sqrt(10))^(1/4*((-1)^n-1)+1/2*n))+(3/20*(-1)^n-13/20)*sqrt(10)*((3-sqrt(10))^(1/4*((-1)^n-1)+1/2*n)-(3+sqrt(10))^(1/4*((-1)^n-1)+1/2*n)). - Paolo P. Lava, Sep 11 2013

EXAMPLE

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).

MAPLE

P:=proc(q) local n; for n from 0 to q do

print(evalf((2-1/2*(-1)^n)*((3-sqrt(10))^(1/4*((-1)^n-1)+1/2*n)+(3+sqrt(10))^(1/4*((-1)^n-1)+1/2*n))+(3/20*(-1)^n-13/20)*sqrt(10)*((3-sqrt(10))^(1/4*((-1)^n-1)+1/2*n)-(3+sqrt(10))^(1/4*((-1)^n-1)+1/2*n)))); od; end: P(100); # Paolo P. Lava, Sep 11 2013

MATHEMATICA

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 *)

CROSSREFS

Cf. A228469, A228470, A228487, A228488.

Sequence in context: A277688 A215131 A068990 * A062594 A128027 A128066

Adjacent sequences:  A228468 A228469 A228470 * A228472 A228473 A228474

KEYWORD

nonn,easy

AUTHOR

Clark Kimberling, Aug 22 2013

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified November 13 13:15 EST 2018. Contains 317149 sequences. (Running on oeis4.)