OFFSET
1,2
COMMENTS
At each step, let the state of the process be (i,t), i_max the greatest i seen so far and i_min > 1 the least i seen so far. Consider the triples (i,j,t%j) for 2 <= j <= i_max, where i_max is the largest i seen so far. If all of those triples have been seen in previous steps, then the next step will not produce a new triple either, so the process will never reach i=1.
EXAMPLE
For k = 8, the process stops at T = 57: (8,0), (9,8), (8,17), (7,25), (6,32), (5,38), (4,43), (3,47), (2,50), (3,52), (2,55), (1,57).
For k = 4, the process never stops: (4,0), (5,4), (4,9), (3,13), (2,16), (3,18), (4,21), ...
PROG
(Python)
def isok(n):
t = 0
seen = set()
maxn = n
steps = 0
while n>1:
maxn = max(maxn, n)
tuples = set((n, m, t%m) for m in range(2, maxn+1))
if tuples <= seen:
break
seen = seen.union(tuples)
t += n
if t%n==0:
n += 1
else:
n -= 1
return n==1
CROSSREFS
KEYWORD
easy,nonn
AUTHOR
Christian Perfect, Nov 10 2020
STATUS
approved