A346965 a(n) is the number of ascending subsequences in reducing n to 1 using the Collatz reduction, or -1 if n refutes the Collatz conjecture.

0, 0, 1, 0, 1, 1, 3, 0, 4, 1, 3, 1, 2, 3, 2, 0, 3, 4, 4, 1, 1, 3, 2, 1, 5, 2, 17, 3, 4, 2, 16, 0, 6, 3, 2, 4, 4, 4, 6, 1, 17, 1, 6, 3, 4, 2, 16, 1, 5, 5, 5, 2, 2, 17, 17, 3, 7, 4, 6, 2, 3, 16, 15, 0, 6, 6, 5, 3, 3, 2, 16, 4, 18, 4, 2, 4, 5, 6, 6, 1, 4, 17, 17

Offset: 1

Author

Douglas Boffey, Aug 09 2021

Keywords

• nonn

Comments

In this sequence, a subsequence is considered ascending for as long as a (3*n + 1) / 2 step is required.

Examples

			a(9) = 4, viz.
  9->14;
  14->7->11->17->26;
  26->13->20;
  20->10->5->8.
		

Links

• Douglas Boffey, Table of n, a(n) for n = 1..20000
• Douglas Boffey, Code used for generating b-file

Crossrefs

Cf. A000265, A070168, A078719, A085062, A160541, A221469.

Programs

C

/* A007814 */
int num_clear_bits(unsigned n) {
  if (n == 0)
    return -1;
  return log2(n & -n);
}
int A346965(unsigned n) {
  int x;
  int result = 0;
  n >>= num_clear_bits(n);
  while (n > 1) {
    x = num_clear_bits(n + 1);
    n = ((n >> x) + 1) * pow(3, x) - 1;
    n >>= num_clear_bits(n);
    ++result;
  }
  return result;
}

Formula

a(2^n) = 0.

a((2^n*(2*x+1)-1) * 2^y) = a(3^n*(2*x+1)-1) + 1, where x, y >= 0.

a(n) = a(A085062(n)) + (n mod 2) for n >= 2. - Alan Michael Gómez Calderón, Feb 09 2025

a(n) = A160541(A000265(n)). - Alan Michael Gómez Calderón, Mar 19 2025