A171870 For odd numbers x, a(x) is the number of complex numbers z in the zx + 1 problem giving the same number of iterations as the 3x + 1 problem requires to reach 1.

0, 1, 0, 4, 5, 3, 1, 4, 2, 5, 0, 3, 6, 40, 4, 38, 7, 2, 5, 10, 39, 8, 3, 37, 6, 6, 1, 40, 9, 9, 4, 38, 7, 7, 2, 36, 41, 2, 5, 10, 5, 39, 0, 8, 8, 32, 3, 37, 42, 6, 6, 30, 11, 35, 40, 23, 1, 9, 4, 9, 33, 14, 38, 14, 43, 7, 7, 12, 31, 12, 2, 36, 41, 41, 5, 2, 10, 29, 10, 17, 34, 5, 39, 22, 15, 44, 8

Offset: 1

Author

Michel Lagneau, Dec 30 2009, May 18 2010

Keywords

• nonn

Comments

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.

Examples

			For x=17, a(9)=2 is in the sequence because the associated polynomial of 17 is 17z^2 + 52z + 160 with degree 2.
		

Links

• Jeffrey C. Lagarias, The 3x+1 problem: An annotated bibliography arXiv:math/0309224

Programs

Mathematica

nextOddK[n_] := Module[{m=3n+1}, While[EvenQ[m], m=m/2]; m]; (* assumes odd n *) Table[m=n; cnt=0; If[n>1, While[m=nextOddK[m]; cnt++; m!=1]]; cnt-1, {n, 1, 200, 2}]

Formula

a(n) = A075680(n) - 1.

Extensions

Partially edited by N. J. A. Sloane, May 22 2010