I have a list called eaData which contains sublists of the form {a, b, number}, where each sublist gives the number of steps in the Euclidean algorithm (EA) for numbers $a$ and $b$.

I have the following code:

eaSteps[{a_, b_}] :=
  NestWhileList[{#[[2]], Mod[#[[1]], #[[2]]]}&, {a, b}, #[[2]] != 0 &]

So for example

eaSteps[{1736, 1333}]
{{1736,1333},{1333,403},{403,124},{124,31},{31,0}}`

I also have

eaData = 
   SortBy[
     Flatten[
       Table[
         {a, b, Length[eaSteps[{a, b}]] - 1},
         {a, 1, 100},
         {b, 1, a}],
       1],
     Part[#,3]&]

My question is: Given that my eaData list contains 5050 sublists, how could I know there are 5050 subentries before I even run the code?

I know that for the EA, the maximum number of steps is at most 5 times the minimum number of digits of either a or b, but how does that help me here?

Further, if b <= a <= 1000, then how can I find the a and b values that require the most steps in the EA?

I'm thinking that I know a has at most 4 digits, so there are at most 20, steps. But now I'm stuck. Any help?

  • shouldn't you change {a, 1, 25} to {a, 1, 100} to get 5050 sublists? – kglr Oct 22 at 1:02
  • yes sorry, I meant {a,1,100}, i just mean, how do I know without running the code itself that I'd get 5050. what is the logic behind it? – user130306 Oct 22 at 1:05
up vote 5 down vote accepted

Update 2: The functions maxEALengthPair and maxEALength can be replaced with alternatives without loops using InverseFunction[Fibonacci]:

ClearAll[fibonacciFloor, maxEALengthPair2, maxEALength2]
fibonacciFloor[n_] := Floor[InverseFunction[Fibonacci][n]]
maxEALength2[n_] := fibonacciFloor[n] - 2
maxEALengthPair2[n_] := Fibonacci[fibonacciFloor[n] + {0, -1}]
And @@ (maxEALengthPair2 @ # == maxEALengthPair @ # & /@ 
  {50, 100, 500, 1000, 10000, 100000, 1000000, 10^7, 10^9})

True

And @@ (maxEALength2@# == maxEALength@# & /@
   {50, 100, 500, 1000,  10000, 100000, 1000000, 10^7, 10^9})

True

Conjecture: For any n such that Fibonacci[k] <= n <= Fibonacci[k+1], the length of longest list eaSteps[{a, b}] (b<a<=n) is k-2 and is reached by the pair {a, b} = Fibonacci[{k, k-1}].

Update: It is also possible to find a pair of numbers {a, b} less than n with maximum length for the sequence eaSteps[{a,b}] without "running the code". It seems that Fibonacci sequence can be used to identify a pair with maximum eaSteps length (I have no idea why though):

First, consecutive triples of the Fibonacci sequence satisfy the relation implicit in eaSteps:

And @@ (# == Mod[#3, #2] & @@@ Partition[Fibonacci[Range[2, 10^5]], 3, 1])

True

Also, if we start with a consecutive Fibonacci numbers {a, b}, eaSteps traces all the Fibonacci numbers smaller than b:

Reverse@eaSteps[Fibonacci[{101, 100}]][[All, 1]] == Fibonacci[Range[2, 101]]

True

ClearAll[maxEALengthPair, maxEALength]
maxEALengthPair[n_] := Module[{i = 0}, 
   While[Fibonacci[++i] < n]; Fibonacci[{i - 1, i - 2}]];
maxEALength[n_] := Module[{i = 0}, While[Fibonacci[++i] < n]; i - 3]

TeXForm @ Grid[{#, ## & @@ #2} & @@@ Transpose[{{"n",  "pair"},
 {#, maxEALengthPair /@ #} &@{50, 100, 500, 1000, 10000, 100000, 1000000, 10^7}}], 
   Dividers -> All] 

$\tiny\begin{array}{|c|c|c|c|c|c|c|c|c|} \hline \text{n} & 50 & 100 & 500 & 1000 & 10000 & 100000 & 1000000 & 10000000 \\ \hline \text{pair} & \{34,21\} & \{89,55\} & \{377,233\} & \{987,610\} & \{6765,4181\} & \{75025,46368\} & \{832040,514229\} & \{9227465,5702887\} \\ \hline \end{array}$

Brute-force approach gives the same results for n ∈ {50, 100, 500, 1000}:

nl = {50, 100, 500, 1000} ;
{#, MaximalBy[Reverse /@ Subsets[Range[#], {2}], Length @* eaSteps][[1]] & /@ #}&@nl
Grid[{#, ## & @@ #2} & @@@ Transpose[{{"n",  "pair"}, {#, 
   MaximalBy[Reverse /@ Subsets[Range[#], {2}], Length[eaSteps[#]] &][[1]] & /@ #} &@nl}], 
  Dividers -> All]

$\tiny\begin{array}{|c|c|c|c|c|} \hline \text{n} & 50 & 100 & 500 & 1000 \\ \hline \text{pair} & \{34,21\} & \{89,55\} & \{377,233\} & \{987,610\} \\ \hline \end{array}$

Note: For some n, there are multiple pairs with maximum eaSteps length. For example, for n=50 there are 7 pairs that give a length 7 list:

MaximalBy[Reverse /@ Subsets[Range[50], {2}], Length @* eaSteps ] 

{{34, 21}, {47, 29}, {50, 29}, {49, 30}, {49, 31}, {50, 31}, {47, 34}}

 Length[eaSteps @ #] - 1 &/@ %

{7, 7, 7, 7, 7, 7, 7}

The table above gives only the first of multiple pairs.

We next tabulate the pairs and lengths for some Fibonacci numbers:

Grid[{#, ## & @@ #2} & @@@ Transpose[{{"k", "F[k]", "pair", "length"}, 
 {#, Fibonacci@#, Column[maxEALengthPair@Fibonacci@#] & /@ #, 
  maxEALength[Fibonacci@#] & /@ #} & @ Range[10, 60, 5]}], 
  Dividers -> All] // TeXForm

$\tiny\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|} \hline \text{k} & 10 & 15 & 20 & 25 & 30 & 35 & 40 & 45 & 50 & 55 & 60 \\ \hline \text{F[k]} & 55 & 610 & 6765 & 75025 & 832040 & 9227465 & 102334155 & 1134903170 & 12586269025 & 139583862445 & 1548008755920 \\ \hline \text{pair} & \begin{array}{l} 34 \\ 21 \\ \end{array} & \begin{array}{l} 377 \\ 233 \\ \end{array} & \begin{array}{l} 4181 \\ 2584 \\ \end{array} & \begin{array}{l} 46368 \\ 28657 \\ \end{array} & \begin{array}{l} 514229 \\ 317811 \\ \end{array} & \begin{array}{l} 5702887 \\ 3524578 \\ \end{array} & \begin{array}{l} 63245986 \\ 39088169 \\ \end{array} & \begin{array}{l} 701408733 \\ 433494437 \\ \end{array} & \begin{array}{l} 7778742049 \\ 4807526976 \\ \end{array} & \begin{array}{l} 86267571272 \\ 53316291173 \\ \end{array} & \begin{array}{l} 956722026041 \\ 591286729879 \\ \end{array} \\ \hline \text{length} & 7 & 12 & 17 & 22 & 27 & 32 & 37 & 42 & 47 & 52 & 57 \\ \hline \end{array}$

Grid[{#, ## & @@ #2} & @@@ Transpose[{{"k", "F[k]", "pair", "length"}, 
 {#, Fibonacci@#, Column[maxEALengthPair@Fibonacci@#] & /@ #, 
  maxEALength[Fibonacci@#] & /@ #} &@Range[4, 25]}], 
  Dividers -> All] // TeXForm

$\tiny\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|} \hline \text{k} & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 \\ \hline \text{F[k]} & 3 & 5 & 8 & 13 & 21 & 34 & 55 & 89 & 144 & 233 & 377 & 610 & 987 & 1597 & 2584 & 4181 & 6765 \\ \hline \text{pair} & \begin{array}{l} 2 \\ 1 \\ \end{array} & \begin{array}{l} 3 \\ 2 \\ \end{array} & \begin{array}{l} 5 \\ 3 \\ \end{array} & \begin{array}{l} 8 \\ 5 \\ \end{array} & \begin{array}{l} 13 \\ 8 \\ \end{array} & \begin{array}{l} 21 \\ 13 \\ \end{array} & \begin{array}{l} 34 \\ 21 \\ \end{array} & \begin{array}{l} 55 \\ 34 \\ \end{array} & \begin{array}{l} 89 \\ 55 \\ \end{array} & \begin{array}{l} 144 \\ 89 \\ \end{array} & \begin{array}{l} 233 \\ 144 \\ \end{array} & \begin{array}{l} 377 \\ 233 \\ \end{array} & \begin{array}{l} 610 \\ 377 \\ \end{array} & \begin{array}{l} 987 \\ 610 \\ \end{array} & \begin{array}{l} 1597 \\ 987 \\ \end{array} & \begin{array}{l} 2584 \\ 1597 \\ \end{array} & \begin{array}{l} 4181 \\ 2584 \\ \end{array} \\ \hline \text{length} & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 \\ \hline \end{array}$

Original answer:

You can get the length of Flatten[Table[{a, b, foo}, {a, 1, n}, {b, 1, a}], 1] using

n (n + 1)/2 

(which is Sum[1, {i, 1, n}, {j, 1, i}])

or

Length[Subsets[Range[n], {1, 2}]]

For n = 100:

100 101 /2 

5050

Length[Subsets[Range[100], {1, 2}]]

5050

table[n_Integer] := Flatten[Table[{a, b, foo}, {a, 1, n}, {b, 1, a}], 1];
Length[table[100]]

5050

For the second part of the question, using a brute force approach

MaximalBy[Reverse/@Subsets[Range[1000],{2}], Length[eaSteps[#]]&]

{{987, 610}}

Length[Length[eaSteps[{987, 610}]]] -1

14

  • thank you! so basically the reason I would know its 5050 before I even run the code is if I use Subsets right? – user130306 Oct 22 at 1:10
  • @user130306, that's correct. – kglr Oct 22 at 1:22
  • great, thank you again. and for the second part of the question, do the values a = 987, b = 610, n = 14 work and is that the right answer? – user130306 Oct 22 at 1:23

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.