cp's OEIS Frontend

A006666 and A006667 are the number of halving and tripling steps to reach 1 in 3x+1 problem.

Properties of this sequence:

a(m) = 0 for m = A211981(m).

The Collatz conjecture is that a(n) is finite. If 1 should never be reached then a(n) = -1.

Compare this sequence with the analogous one A075680(n+1) for the reduced Collatz map of A075677.

a(n) gives also the minimal number of iterations of the Vaillant-Delarue map f, defined in A324245, acting on n to reach 0 (assuming the Collatz conjecture).

For the link to the Vaillant-Delarue paper (where fs is called f_s) see A324036.

This sequence appears easy because a(n) = A075680(n) - 1, but its true object is the introduction of polynomials f(z) with interesting properties, for instance the study of the roots of f(z)= 0.

The 3x+1 problem is an exceptional case of the zx + 1 problem (for z real or complex). The sequence gives the number of z <> 3 which gives the same trajectory as the 3x + 1 problem. We associate each number x with a polynomial f(z) whose roots have the same behavior as the integer 3 in the 3x + 1 problem. The sequence gives the degree of each polynomial. Example: with n = 17, the trajectory is (17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1) and we obtain, for z = 3, the following steps:

17;

17z + 1 = 52;

(17z + 1)/4 = 13;

z(17z + 1)/4 + 1 = 40;

(z(17z + 1)/4 + 1)/8 = 5;

z(z(17z + 1)/4 + 1)/8 + 1 = 16;

(z(z(17z + 1)/4 + 1)/8 + 1)/16 = 1 => f(z) = 17z^3 + z^2 + 4z - 480 = (z-3)(17z^2 + 52z + 160)= 0.

The polynomial g(z) = 17z^2 + 52z + 160 of degree 2 is connected with the number 17. The two roots z1 and z2 have the same behavior as the integer 3, and the 3*x + 1 problem, z1*x + 1 problem and z2*x + 1 problem are identical for x = 17. The following polynomials are given for x = 1, 3, 5, ..., 21.

1 -> z-3

3 -> (z-3)*(3z + 10)

5 -> 5*(z-3)

7 -> (z-3)*(7z^4 + 22z^3 + 68z^2 + 208z + 640)

9 -> (z-3)*(9z^5 + 28z^4 + 88z^3 + 272z^2 + 832z + 2560)

11 -> (z-3)*(11z^3 + 34z^2 + 104z + 320)

13 -> (z-3)*(13z + 40)

15 -> (z-3)*(15z^4 + 46z^3 + 140z^2 + 424z + 1280)

17 -> (z-3)*(17z^2 + 52z + 160)

19 -> (z-3)*(19z^5 + 58z^4 + 176z^3 + 544z^2 + 1664z + 5120)

21 -> 21*(z-3)

23 -> (z-3)*(23z^3 + 70z^2 + 212z + 640)

...

In the general case and for each number n, if the Collatz conjecture is true, the polynomial is of the form:

f(z) = (z-3)*g(z) = n*z^p + z^(p-1) + 2^a*z^(n-2) + 2^b*z^(n-3) + ... + 2^w*z + 2^r - 2^s

where

s is the number of divisions by 2 at the last step;

r is the number of divisions by 2 at before the last step;

a is the number of divisions by 2 at the first step;

b is the number of divisions by 2 at the second step.

Number of multiplicative finite groups G(p) with elements {T(2n+1,k)/pZ} where T(2n+1,k) is the reduced trajectory of the Collatz problem whose elements are all odd and p <= A075684(n) + 1.

A006666 and A006667 are the number of halving and tripling steps to reach 1 in 3x+1 problem.

Conjecture: k exists for all n.

In other words, given an integer n, there always exists at least an integer k and a pair of integers (a, b) such that n + k = 2^a/3^b where a is the number of halving steps to reach 1, and b is the number of tripling steps to reach 1, in the 3x+1 problem.

Definition of the (3x+1)-polynomials.

The 3x+1 problem is an exceptional case of the zx + 1 problem (for z real or complex). We associate each odd integer x with a polynomial f(z) whose roots have the same behavior as the integer 3 in the 3x + 1 problem.

The polynomial f(z) is called "(3x+1)-polynomials" and the problem zx + 1 generates the same number of iterations as the 3x + 1 problem requires to reach 1. The polynomial f(z) has interesting properties, for instance the study of the roots of f(z)= 0.

The following example shows the process.

Let’s consider x = 17. The corresponding reduced Collatz trajectory containing only odd numbers (17, 13, 5, 1) is obtained from the following steps:

start with x = 17;

step 1: (3*17 + 1)/4 = 52/4 = 13;

step 2: (3*(3*17 + 1)/4 + 1)/8 = 40/8 = 5;

step 3: (3*(3*(3*17 + 1)/4 + 1)/8 + 1)/16 = 16/16 = 1.

Step 4: substitute the number 3 by the variable z. So, we obtain the following equation:

f(z) = 17z^3 + z^2 + 4z - 480 = (z-3) g(z) = (z-3)(17z^2 + 52z + 160)= 0.

We would consider that the polynomial f(z) is associated with the integer 17.

The three roots are:

z0 = 3;

z1 = -1.529411765 + 2.659448131 I;

z2 = -1.529411765 - 2.659448131 I.

The roots z1 and z2 have the same behavior as the integer z0=3, and the 3*x + 1 problem, z1*x + 1 problem and z2*x + 1 problem are identical for x = 17 : we obtain the same number of iterations of the reduced Collatz function required to yield 1: 17 = 2*9-1 => A075680(9) = 3 iterations.

For example, with z1 we obtain the following steps:

(17*z1 + 1)/4 = -6.250000001 + 11.30265455*I

(z1*(17*z1 + 1)/4 + 1)/8 = -2.437500001 - 4.238495460*I

(z1*(z1*(17*z1 + 1)/4 + 1)/8 + 1)/16 = 1.

For each number x = 2n-1, if the Collatz conjecture is true, the polynomial f(z) is of the general form :

f(z) =(2n-1)*z^p + z^(p-1) + 2^a*z^(n-2) + 2^b*z^(n-3) + ... + 2^w*z + 2^r - 2^s = (z-3) g(z) with the property : degree(f(z)) = p = A075680(n), n>1.

s is the number of divisions by 2 at the last step

r is the number of divisions by 2 at before the last step

a is the number of divisions by 2 at the first step

b is the number of divisions by 2 at the second step

The trajectory starts with a minimum for odd n and with a maximum (see A351974) for even n (>=2). Since the trajectory always stops at 1 (a minimum) assuming the Collatz conjecture holds, a(n) is odd if n is odd and vice versa.

The terms in row n are T(n,0), T(n,1), ..., T(n, A258145(n)-2), and are the partial sums of the terms in row n of A351122.

In each row n, the terms also satisfy the equation 3* (3* (3* (3* ... (3* (2n+1) +1) + 2^T(n,0)) + 2^T(n,1)) + 2^T(n,2)) + ... = 2^T(n, A258145(n)-2); e.g., for n=4, and A258145(4)-2=5: 3* (3* (3* (3* (3* (3*9+1) +2^2) +2^3) +2^4) +2^6) +2^9 = 2^13.

For row n, the right-hand side of the equation above is 2^A166549(n+1). E.g., for the above example (n=4), the right-hand side is 2^A166549(4+1) = 2^13.

a(n) necessarily is the first odd term in any Collatz trajectory in which it occurs.