OFFSET
1,2
COMMENTS
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
LINKS
Michel Lagneau, Coefficients
EXAMPLE
Triangle begins:
1, -3,
3, 1, -30,
5, -15,
7, 1, 2, 4, 16, -1920,
9, 1, 4, 8, 16, 64, -7680,
11, 1, 2, 8, -960,
13, 1, -120,
15, 1, 2, 4, 8, -3840,
17, 1, 4, -480,
19, 1, 2, 16, 32, 128, -15360,
21, -63,
23, 1, 2, 4, -1920,
25, 1, 4, 8, 64, 128, 512, -61440,
The corresponding polynomials are:
+----+-----------------------------------------------------------+
| x | Polynomials f(z) including the factor (z - 3) |
+----+-----------------------------------------------------------+
| 1 | z - 3 |
| 3 | 3z^2 + z - 30 |
| 5 | 5z - 15 |
| 7 | 7z^5 + z^4 + 2z^3 + 4z^2 + 16^z - 1920 |
| 9 | 9z^6 + z^5 + 4z^4 + 8z^3 + 16z^2 + 64z - 7680 |
| 11 | 11z^4 + z^3 + 2z^2 + 8z - 960 |
| 13 | 13z^2 + z -120 |
| 15 | 15z^5 + z^4 + 2z^3 + 4z^2 + 8z - 3840 |
| 17 | 17z^3 + z^2 + 4z - 480 |
| 19 | 19z^6 + z^5 + 2z^4 + 16z^3 + 32z^2 + 128z - 15360 |
| 21 | 21z - 63 |
| 23 | 23z^4 + z^3 + 2z^2 + 4z - 1920 |
+----+-----------------------------------------------------------+
+----+-----------------------------------------------------------+
| x | Polynomials f(z)/(z - 3) |
+----+-----------------------------------------------------------+
| 1 | 1 |
| 3 | 3z + 10 |
| 5 | 5 |
| 7 | 7z^4 + 22z^3 + 68z^2 + 208z +640 |
| 9 | 9z^5 + 28z^4 + 88z^3 + 272z^2 + 832z + 2560 |
| 11 | 11z^3 + 34z^2 + 104z + 320 |
| 13 | 13z + 40 |
| 15 | 15z^4 + 46z^3 + 140z^2 + 424z + 1280 |
| 17 | 17z^2 + 52z + 160 |
| 19 | 19z^5 + 58z^4 + 176z^3 + 544z^2 + 1664z + 5120 |
| 21 | 21 |
| 23 | 23z^3 + 70 z^2 + 212z + 640 |
+----+-----------------------------------------------------------+
MAPLE
for m from 1 by 2 to 27 do: T:=array(1..50, [0$50]):U:=array(1..50, [0$50]):
n:=m:ii:=2:xx1:=2:pp1:=0:s:=0:U[1]:=n:U[2]:=1:
for q from 1 to 100 while(xx1<>1)do:
n1:=3*n+1:
for p from 1 to 50 do:
p1:=2^p:x1:=floor(n1/p1):x0:=irem(n1, p1):
if x0=0 and xx1<> 1
then
pp1:=p:xx1:=x1:
else
fi:
od:
T[ii]:=pp1:n1:=x1:n:=xx1:ii:=ii+1:od:s:=0:
for j from 1 to ii-3 do:
s:=s+T[j]:U[j+2]:=2^s:
od:
s:=s+T[ii-2]:s1:=2^s:s:=s+T[ii-1]:
s2:=2^s:U[ii]:=s1-s2:
W:=array(1..ii-1, [0$ii-1]):
W[1]:=U[1]:
for l from 2 to ii-1 do:
W[l]:=U[l+1]:
od:
print(m):
print(W):
od:
CROSSREFS
KEYWORD
sign,tabf
AUTHOR
Michel Lagneau, Mar 30 2016
STATUS
approved