Algorithm that runs very long for some parameters and never halts for others 11 days ago I asked a similar question with a specific narrow focus, to which there is probably no answer. So here I am asking about the underlying problem.

I teach computer science and would like to discuss Turing's halting problem1 with my students. As an introduction to this topic, I would like to give them two computer programs (written in Python) with these properties:

*

*The two programs should be as similar as possible. Ideally, they should differ only by one numeric literal, and this difference should be very small.

*The two programs should not read any input. All parameters are defined within the program.

*The two programs should be very short and easy to understand. The shorter the better. No more than 10 lines of code (not counting comments and blank lines).

The students are asked to tell which of the two programs halts and which runs forever. They should suggest methods how to find out the right solution.
I think a good approach is to code a math problem that has a solution for some small input parameter with a large number as the result, while having no solution at all for another small input parameter.
My first attempt was a Python program that computes the greatest common divisor of some simple expressions in a loop, halting after about $8\cdot10^{51}$ cycles:
import math
n = 1
gcd = 1
while gcd == 1:
    n += 1
    gcd = math.gcd(n ** 17 + 9, (n + 1) ** 17 + 9)
print("n   =",n)
print("gcd =",gcd)

So this program tries to find in a brute force approach the smallest $n$ for which
$$
\mathrm{gcd}(n^a+b,(n+c)^a+b)\ne1
$$
with $(a,b,c)=(17,9,1)$. (Compare OEIS A255859)
The print commands are not really necessary, so the program has 6 relevant lines of code and would run on an average common desktop computer for about $10^{41}$ years (that's about $7\cdot10^{29}$ times the age of the universe) and then it would output two numbers with 52 decimal places each.
This program is short and easy to understand. More importantly, without knowing the solution in advance and without advanced mathematical knowledge, it is virtually impossible to tell whether or not this program will eventually come to an end.
In the question linked to in the introduction, I asked for another value triple for $(a,b,c)$ that would cause the program to run forever. This would give the perfect never-stopping sibling program for the program shown here. But it seems that all non-trivial triples ($a\ne1\land c\ne1$) would cause the program to come to an end sooner or later.
Therefore, I need another mathematical problem that can be wrapped into two similar Python programs, one of which stops after a very long runtime, while the other runs forever.
What mathematical problems could these be, and with what parameters?
Just for your information:
My students are not studying math or computer science. Some of them study data science, the others information security. So most of them are interested in math, but it is not their major.

1 Turing's Halting Problem in a nutshell: Is it possible to write a computer program that is a universal halting tester (UHT)? This UHT should be able to read any computer program and the input given to that program, and then tell whether the program with that input will halt (stop) at some point or whether it will keep running forever. The answer is: It is possible to write halting testers for many special cases, but it can be proved that the existence of a universal halting tester is impossible.

Addendum (reaction to answers given so far):
Thank you very much for the answers given so far. Most of them are really great! Thank you! But it would be really nice to have a problem, that has another property that I didn't mention explicitly:
When you add a print command inside the loop of the program shown here in my question, that prints the value of gcd in each round, then you get a list with more than $8\cdot10^{51}$ identical lines, each line showing the number $1$. And then, in its last round it for the very first time prints another number (which in this case has 52 decimal digits) and then halts.
I know, I didn't mention this property explicitly, but is there another problem that fulfills all criteria form above plus the additional criterion that it repeats the very same number in many rounds before it does something else?
 A: (Generalized) Pell's equation can be a good source of big numbers. For example, consider the equation $$x^2 - 2017y^2 = K$$
and look for a solution in positive integers.

*

*$K=0$ has no solutions. "Unfortunately", the proof that there are no solutions is so simple that a smarter student might figure it out on their own (especially if they are familiar with the proof that $\sqrt{2}$ is irrational).

*The smallest solution for $K=1$ has more than $50$ decimal digits:$x_1=22691017898615873418283839489716246568157231499338273$. Finding this solution (and knowing it's minimal) requires a fair bit of understanding how Pell's equations work.

*$K=3$ can be solved by a simple brute-force search, since the smallest solution has $x_3=5865694$ (of course, there are faster methods for finding this solution too).

*$K=5$ might be a better no-solution example. Unlike the $K=0$ case, this one should not be easy to see as being unsolvable.

Thus, the following program (with $\_\_\_\_$ replaced by $K$) can finish quickly, rather slowly, or not at all.
x, y = 1, 1

while True:
   d = (x*x - 2017*y*y) - ____
   if d > 0:
      y += 1
   elif d < 0:
      x += 1
   else:
      break

print(x, y)


While not outright obvious, the unsolvability of $x^2-2017y^2=5$ can be demonstrated rather easily by considering the whole equation modulo $5$. The only remainders of squares modulo $5$ are $0$, $1$ and $4$, and the only combination that fits the equation is for both $x$ and $y$ being divisible by $5$. But that is impossible, since that would make the left-hand side of the equation divisible by $25$ but the right-hand side is not.
A: The sum of cubes problem gives a very nice twist on what you’re asking. Consider this pseudocode:
for n from 0 to infinity:
  for x from -n to +n:
    for y from -n to +n:
      for z from -n to +n:
        if x**3 + y**3 + z**3 = ____:
          halt

If you fill in the blank with…

*

*… 113 the program never terminates,

*… 114 no one knows whether it terminates, and

*… 115 the program terminates.

This doesn’t quite meet the “halts after a very long time” criterion, but still illustrates the complexity of the halting problem.
If you want something that takes a very long time to halt, try setting the blanks to 33 (will take an astonishing amount of time to terminate) and 32 (never halts).
(I’ve used this example in my intro CS theory course because it’s super easy to state and yet immediately hits on an open problem. Students find this fascinating!)
A: compare   finding integers
$$   x^2 + 27 y^2  = 7 z^3   + 14  $$
$$   x^2 + 27 y^2  = 7 z^3   + 6  $$
where the first one...
The relevant material is in Ireland and Rosen. This was the first example that Kaplansky found when I gave him some working programs
A: The following program finds solutions of $2^n\bmod n = 2$ (i.e. positive integers $n$ such that when $2^n$ is divided by $n$ the remainder is $2$) until they exceed a specified size $N$:
n = 0; N = 10**10**6
while True:
    n += 1
    found = 1 if (pow(2,n,n) == 2 and n > N) else 0
    print(found, end=' ')  
    if found: break

On an ideal computer with unlimited resources, this program has the following properties for any positive integer $N$ (no matter how large!) :

*

*It prints more than $N$ $0$s followed by a $1$, halting on the first solution larger than $N$. That such a solution must exist can be proved using Fermat's "little" theorem.

*If == 2 is changed to == 1, the resulting program prints $0$s forever without halting.  Proof of this is not trivial (e.g. the proof given here, again using Fermat's theorem).

*found, as a function of $n$, is the indicator function for the event $(2^n\bmod n = 2 \ \ \text{ and }\ \  n > N)$. If the = 1 in its definition is replaced by = n, then the list of $0$s would be followed by $n$, rather than by $1$.

Note: A typical PC executes the statement N=10**10**6 and begins printing an infeasible number of $0$s almost immediately. Setting N=10**10**10, however, may require several days before the printing starts.
