A338807 Numbers k such that the process starting at (k, 0) mapping (k, t) to (k+1, t+k) if t = 0 (mod k), and (k-1, t+k) otherwise, eventually reaches (1, T) for some T.

1, 2, 8, 9, 11, 14, 18, 20, 23, 32, 35, 38, 40, 47, 49, 50, 53, 56, 57, 58, 59, 62, 67, 71, 73, 74, 77, 89, 91, 92, 95, 98, 101, 104, 106, 114, 116, 128, 134, 135, 137, 140, 148, 149, 152, 155, 156, 158, 159, 162, 164, 169, 172, 173, 185, 188, 191, 194, 197

Offset: 1

Author

Christian Perfect, Nov 10 2020

Keywords

• easy
• nonn

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.

Examples

			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), ...
		

Programs

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