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

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

Offset: 1

Author

Clark Kimberling, Aug 18 2013

Keywords

• nonn
• easy

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

Examples

			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.
		

Links

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

Crossrefs

Cf. A000045.

Programs

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