A368136 Numbers k for which a generalized Collatz trajectory (x / k if k divides x, x + ceiling(x / k) otherwise) has non-elementary loops starting from a positive integer x_0 < k^2.

3, 4, 6, 9, 10, 15, 16, 17, 20, 23, 24, 27, 29, 31, 48, 54, 57, 78, 85, 94, 111, 118, 123, 127, 129, 134, 136, 171, 172, 225, 368, 419, 540, 547, 706, 744, 1112, 1148, 1169, 1229, 1308, 1403, 1545, 1782, 1869, 1926, 1939

Offset

1,1

Comments

For a given k, define the generalized Collatz trajectory starting at x_0 > 0 as follows:

x_(i+1) = x_(i) / k if k divides x_(i);

x_(i+1) = x_(i) + ceiling(x_(i) / k) otherwise.

For k = 2, this is equivalent to the Collatz step x -> x/2 or (3x + 1)/2.

We call a loop an 'elementary loop' if it contains 1 as a term and otherwise a 'non-elementary loop'. The loop containing 1 consists of the terms 1, 4, 2, 1 for k = 2, or 1, 2, ..., k, 1 for other k.

k^2 has been chosen as an arbitrary boundary, giving more terms of the (limiting) sequence (i.e., the unknown sequence that would result if no boundary were used) than using 2*k, 3*k, or similar boundaries. It is unknown whether there are values of k for which non-elementary loops exist only for values greater than k^2.

It is also unknown whether there are values of k and x_0 for which trajectories do not contain any loop. Such values would be terms of the sequence only if there are also non-elementary loops.

Links

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

Walter Carnielli, Some natural generalizations of the Collatz Problem, Applied Mathematics E-Notes 15 (2015): 207-215.

Wikipedia, Collatz Conjecture.

Wikipedia, Floyd's cycle detection algorithm.

OEIS Wiki, 3x+1 problem.

Example

k = 3 is a term since it has a non-elementary loop starting from x_0 = 7:
  7, 10, 14, 19, 26, 35, 47, 63, 21, 7, ...
k = 2 is not a term since it has no non-elementary loops starting from x_0 < 4.

Prog

(Python)
def containsloops(k):
    for x_ in range(k, k*k):
        s = 0
        x = x_
        m = x
        while x != 1 and s <= m:
            d, r = divmod(x, k)
            x = d if r == 0 else d + x + 1
            s += 1
            m = max(m, x)
        if s > m and x > k:
            return True
    return False
print([k for k in range(1, 100) if containsloops(k)])

Crossrefs

Cf. A006370.

See A033478 for an example of a trajectory (based on the 3x + 1 formulation) with k = 2 and x_0 = 3, ending in an elementary loop.

Sequence in context: A299231 A005122 A166161 * A130904 A034706 A245810

Adjacent sequences: A368133 A368134 A368135 * A368137 A368138 A368139

Keyword

nonn,more

Author

Giuseppe Ciacco, Dec 13 2023

Extensions

a(43)-a(45) from Giuseppe Ciacco, Feb 05 2024

a(46)-a(48) from Giuseppe Ciacco, Feb 14 2024

Status

approved