A323424 Number of cycles (mod n) under Collatz map.

1, 1, 2, 1, 2, 2, 3, 2, 2, 2, 3, 2, 3, 2, 3, 2, 2, 2, 3, 2, 2, 2, 3, 2, 2, 2, 4, 2, 2, 2, 3, 2, 2, 2, 3, 2, 3, 3, 3, 2, 3, 2, 4, 2, 3, 2, 3, 2, 3, 2, 3, 2, 2, 2, 4, 2, 2, 2, 3, 2, 2, 2, 3, 2, 2, 2, 3, 2, 3, 2, 3, 2, 2, 2, 3, 3, 2, 2, 3, 2, 2, 2, 4, 2, 2, 2, 3

Offset: 1

Author

Rémy Sigrist, Jan 14 2019

Keywords

• nonn

Comments

This sequence is likely to be unbounded.

Examples

			The initial terms, alongside the corresponding cycles, are:
  n   a(n)  cycles
  --  ----  --------------------
   1     1  (0)
   2     1  (0)
   3     2  (0), (1)
   4     1  (0)
   5     2  (0), (1, 4, 2)
   6     2  (0), (1, 4, 2)
   7     3  (0), (1, 4, 2), (3)
   8     2  (0), (1, 4, 2)
   9     2  (0), (1, 4, 2)
  10     2  (0), (1, 4, 2)
  11     3  (0), (1, 4, 2), (5)
  12     2  (0), (1, 4, 2)
  13     3  (0), (1, 4, 2), (3, 10, 5)
  14     2  (0), (1, 4, 2)
  15     3  (0), (1, 4, 2), (7)
  16     2  (0), (1, 4, 2)
  17     2  (0), (1, 4, 2)
  18     2  (0), (1, 4, 2)
  19     3  (0), (1, 4, 2), (9)
  20     2  (0), (1, 4, 2)
		

Links

• Rémy Sigrist, Illustration for n = 13
• Index entries for sequences related to 3x+1 (or Collatz) problem

Crossrefs

See A000374, A023135, A023153, A233521 for similar sequences.

Cf. A006370.

Programs

PARI

a(n, f = k -> if (k%2, 3*k+1, k/2)) = { my (c=0, s=0); for (k=0, n-1, if (!bittest(s, k), my (v=0, i=k); while (1, v += 2^i; i = f(i) % n; if (bittest(s, i), break, bittest(v, i), c++; break)); s += v)); return (c) }

Formula

a(n) >= 2 for any n > 4 (as we have at least the cycles (0) and (1, 4, 2)).