# How can I know the length of sublists in an expression without evaluating the expression?

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 '18 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 '18 at 1:05

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}$$

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 '18 at 1:10
• @user130306, that's correct. – kglr Oct 22 '18 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 '18 at 1:23