Efficiently producing certain kinds of examples of the application of Euclid's algorithm

Question

Is there some efficient way to churn out pairs of integers $n,m$ such that

• $\gcd(n,m)=1$;
• $n,m$ both have fairly large numbers of fairly small prime factors; and
• Euclid's algorithm applied to $n,m$ has a moderately large number of steps; e.g. a number is replaced by its remainder at least four or five or six times?

Answer 1

How about the following heuristic:

1. Choose $n = {p_1}^{e_1}\cdots{p_k}^{e_k}$ for some small primes $p_i$ and arbitrary exponents.

2. Let $a = {p_{k+1}}^{e_k+1}\cdots{p_l}^{e_l}$ using different small primes. Choose arbitrary exponents while ensuring that $a \ll n$.

3. Let $p^\star$ be the smallest prime greater than $\dfrac{\phi n}{a}$ where $\phi = \dfrac{1+\sqrt5}{2}$.

4. Let $m = ap^\star$.

Then $m$ and $n$ both have many small prime factors ($n$ has exactly one large prime factor, $p^\star$), and $m \approx a \dfrac{\phi n}{a} = \phi n$. Because $m$ and $n$ have a ratio of approximately $\phi$, the Euclidean algorithm will take many steps to run.

---

Example:

1. Choose $n = 2^4 \cdot 3^3 \cdot 5^4 \cdot 19^2 \cdot 61 = 5945670000$.
2. Choose $a = 7 \cdot 11 \cdot 13 \cdot 17 \cdot 23 = 391391$.
3. $p^\star = 24593$, the smallest prime greater than $\dfrac{\phi n}{a} = 24579.75\ldots\,$.
4. $m = ap^\star = 9625478863$.

Running Euclid on $(n,m)$ takes 24 steps. Here's a list of the intermediate values along with their ratios. Note that the ratio stays near $\phi$ for the first five or six steps:

9625478863 5945670000  ratio: 1.618
5945670000 3679808863  ratio: 1.615
3679808863 2265861137  ratio: 1.624
2265861137 1413947726  ratio: 1.602
1413947726 851913411  ratio: 1.659
851913411 562034315  ratio: 1.515
562034315 289879096  ratio: 1.938
289879096 272155219  ratio: 1.065
272155219 17723877  ratio: 15.355
17723877 6297064  ratio: 2.814
6297064 5129749  ratio: 1.227
5129749 1167315  ratio: 4.394
1167315 460489  ratio: 2.534
460489 246337  ratio: 1.869
246337 214152  ratio: 1.15
214152 32185  ratio: 6.653
32185 21042  ratio: 1.529
21042 11143  ratio: 1.888
11143 9899  ratio: 1.125
9899 1244  ratio: 7.957
1244 1191  ratio: 1.044
1191 53  ratio: 22.471
53 25  ratio: 2.12
25 3  ratio: 8.333
3 1  ratio: 3.0

Answer 2

Example #1: Neighboring Fibonacci Numbers

By reverse induction and $F_n + F_{n-1} = F_{n+1}$

$(F_n, F_{n+1}) = (F_n, F_{n-1} + F_n) = (F_n, F_{n-1}) = \dots = (F_1, F_0) = 1$

How to prove gcd of consecutive Fibonacci numbers is 1?

---

Example #2: Advanced Discussion on arXiv

just this week A short proof that the number of division steps in the Euclidean algorithm is normally distributed was posted. The average number of Euclidean algorithm steps is $\frac{12}{\pi^2} \log 2 \log n $. If $n = 10^6$ that number is about $2 \times 6 = 12$.

Here with some Python I compute random gcd's of numbers up to $10^6$. Notice it takes no more than 30 steps (on average about $12$ in agreement with above). In these examples GCD will be $1$ about two-thirds of the time. My code is on GitHub.

---

Example #3: Connection to Yves Daoust solution

Divide the set $P$ of primes less than 100 and split into two sets $P_1, P_2$. If you randomly multiply only within $P_1$ or $P_2$ you are guaranteed to be relatively prime and smooth. If these two products are less than $10^N$ the expected number of steps is around $2*N$.

Answer 3

$$3\cdot7\cdot13\cdot23\cdot31\cdot41=6737367$$

$$2\cdot5\cdot11\cdot17\cdot29\cdot37=2376770$$

$$6737367, 2376770, 1983827, 392943, 19112, 10703, 8409, 2294, 1527, 767, 760, 7, 4, 3, 1$$

Answer 4

I would try working the Euclidean algorithm backwards: $r_{n-2}=k\cdot r_{n-1}+r_n$, looking for $k$'s that gave me the small factors I wanted at each step. Since you want $\gcd(m,n)=1$, the last two remainders would be $0$ (last), and $1$ (second to last).

For instance, the (reverse) sequence of remainders could be something like:

$0$

$1$

$6\cdot 1+0=6$

$4\cdot 6+1=25$

$2\cdot 25+6=56$

$1\cdot 56+25=81$

$4\cdot 81+56=380$

$3\cdot 380+81=1221$

Giving you a problem where you start with taking the gcd of $380=2^2\cdot 5\cdot 19$ and $1221=3\cdot11\cdot 37$

(Of course you can play with the multipliers going from one remainder to the next to (try to) get initial numbers that have suitable factorizations.)

Then, as you discuss in your comments, you would multiply each by some common amount to get the problem you wanted.