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

Links

Table of n, a(n) for n=1..59.

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

Sequence in context: A345019 A116039 A030334 * A020676 A086678 A359771

Adjacent sequences: A338804 A338805 A338806 * A338808 A338809 A338810

Keyword

easy,nonn

Author

Christian Perfect, Nov 10 2020

Status

approved