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

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A228247 Number of primitive solutions of t(x,n) - s(x,n) = 2, where s(x,n) and t(x,n) are the number of applications of the classical and modified Euclidean algorithms needed to convert (x,n) to GCD(x,n). 3
0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 2, 0, 1, 2, 1, 1, 2, 1, 3, 2, 0, 2, 5, 2, 1, 4, 2, 3, 4, 1, 5, 3, 4, 6, 5, 1, 1, 6, 5, 4, 4, 3, 7, 8, 1, 7, 9, 4, 5, 6, 4, 5, 6, 6, 10, 6, 5, 6, 8, 4, 7, 9, 7, 7, 8, 6, 6, 12, 10, 10, 11, 3, 5, 7, 8, 11, 6, 11, 13, 10, 4, 7, 15 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,11

COMMENTS

The classical Euclidean algorithm uses the mapping u(x,y) = (y, (x mod y)).  In much the same way, the modified Euclidean algorithm, introduced here, uses the mapping v(x,y) = (y, y-(x mod y)).  Specifically, suppose that (x,y) is an ordered pair of positive integers.  Let s(x,y) be the number of applications of u, starting with (x,y)->u(x,y), needed to reach ( . , g), where g = GCD(x,y), and let t(x,y) be the number of applications of v, starting with (x,y)->v(x,y), to reach ( . , g).

For fixed d >= 0, if t(x,y)-s(x,y) = d, then t(x+k*y,y)-s(x+k*y,y) = d for all k>=0.  Thus, for any such (x,y), there is a least m for which t(m,y)-s(m,y) = d.  The pair (m,y) is called a primitive solution of t(x,y)-s(x,y) = d.  Let c(n) be the number of primitive solutions of the equation t(x,n)-s(x,n) = d.

For d = 0, (c(n)) = (0,1,0,1,1,1,2,2,1,3,1,2,2,3,2,5,...)

For d = 1, (c(n)) = (1,1,2,2,3,3,3,3,4,4,3,6,4,4,6,4,...)

For d = 2, (c(n)) = (0,0,0,0,0,0,0,1,0,0,2,0,1,2,1,1,...) = A228247

For d > 0, (c(n)) = (1,1,2,2,3,3,3,4,4,4,5,6,5,6,7,5,...)

For d >=0, (c(n)) = (1,2,2,3,4,4,5,6,5,7,6,8,7,9,9,10,...)

Records are set by (x,y) = (F(n+1),F(n)), where F = A000045 (Fibonacci numbers).

LINKS

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

EXAMPLE

a(19) = 3 counts the primitive solutions (31,19), (33,19), (34,19).  Applications of the classical and modified Euclidean algorithms are indicated here:

(31,19)->(19,12)->(12,7)->(7,5)->(5,2)->(2,1), so s(31,19) = 5;

(31,19)->(19,7)->(7,2)->(2,1), so t(31,19) = 3 and d(31,19) = 2.

(33,19)->(19,4)->(14,5)->(5,4)->(4,1), so s(33,19) = 4;

(33,19)->(19,5)->(5,1), so t(33,19)=2, so t(33,19) = 2 and d(33,19) = 2.

(34,19)->(19,15)->(15,4)->(4,3)->(3,1), so s(34,19) = 4;

(34,19)->(19,4)->(4,1), so t(34,19) = 2 and d(34,19 = 2.  All other x for which d(x,19) = 2 are nonprimitive, so that a(19) = 3.

MATHEMATICA

f[{b_, c_}] := {c, Mod[b, c]}; f1[{b_, c_}] := {c, c - Mod[b, c]}; ans = Select[Flatten[Table[{Length[NestWhileList[f, #, #[[2]] > 0 &]] - Length[NestWhileList[f1, #, ! #[[1]] == #[[2]] &]], #} &[{b, c}], {c, 1, #}, {b, c, #}], 1] &[250], #[[1]] > 0 &]; sorted = Map[{#[[1]], Reverse[#[[2]]]} &, Sort[Map[{#[[1]], Reverse[#[[2]]]} &, ans]]];

groupA = Select[sorted, #[[2]][[1]] < 2 #[[2]][[2]] &];

SplitBy[groupA, #[[2]][[2]] &] // TableForm; z = 200;

Map[Count[groupA, {1, {_, #}}] &, Range[z]]  (* d = 1 *)

Map[Count[groupA, {2, {_, #}}] &, Range[z]]  (* d = 2; A228247 *)

Map[Count[groupA, {3, {_, #}}] &, Range[z]]  (* d = 3 *)

Map[Count[groupA, {_, {_, #}}] &, Range[z]]  (* d > 0 *)

(* Peter J. C. Moses, Aug 12 2013 *)

CROSSREFS

Cf. A000045.

Sequence in context: A260648 A127242 A025853 * A025847 A092130 A029298

Adjacent sequences:  A228244 A228245 A228246 * A228248 A228249 A228250

KEYWORD

nonn,easy

AUTHOR

Clark Kimberling, Aug 18 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 March 28 19:06 EDT 2017. Contains 284246 sequences.