|
%I #16 Nov 01 2021 16:53:58
%S 1,-3,3,1,-30,5,-15,7,1,2,4,16,-1920,9,1,4,8,16,64,-7680,11,1,2,8,
%T -960,13,1,-120,15,1,2,4,8,-3840,17,1,4,-480,19,1,2,16,32,128,-15360,
%U 21,-63,23,1,2,4,-1920,25,1,4,8,64,128,512,-61440
%N Triangle read by rows, the coefficients of the (3x+1)-polynomials.
%C Definition of the (3x+1)-polynomials.
%C 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.
%C 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.
%C The following example shows the process.
%C Let’s consider x = 17. The corresponding reduced Collatz trajectory containing only odd numbers (17, 13, 5, 1) is obtained from the following steps:
%C start with x = 17;
%C step 1: (3*17 + 1)/4 = 52/4 = 13;
%C step 2: (3*(3*17 + 1)/4 + 1)/8 = 40/8 = 5;
%C step 3: (3*(3*(3*17 + 1)/4 + 1)/8 + 1)/16 = 16/16 = 1.
%C Step 4: substitute the number 3 by the variable z. So, we obtain the following equation:
%C f(z) = 17z^3 + z^2 + 4z - 480 = (z-3) g(z) = (z-3)(17z^2 + 52z + 160)= 0.
%C We would consider that the polynomial f(z) is associated with the integer 17.
%C The three roots are:
%C z0 = 3;
%C z1 = -1.529411765 + 2.659448131 I;
%C z2 = -1.529411765 - 2.659448131 I.
%C 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.
%C For example, with z1 we obtain the following steps:
%C (17*z1 + 1)/4 = -6.250000001 + 11.30265455*I
%C (z1*(17*z1 + 1)/4 + 1)/8 = -2.437500001 - 4.238495460*I
%C (z1*(z1*(17*z1 + 1)/4 + 1)/8 + 1)/16 = 1.
%C For each number x = 2n-1, if the Collatz conjecture is true, the polynomial f(z) is of the general form :
%C 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.
%C s is the number of divisions by 2 at the last step
%C r is the number of divisions by 2 at before the last step
%C a is the number of divisions by 2 at the first step
%C b is the number of divisions by 2 at the second step
%H Michel Lagneau, <a href="/A271082/a271082.pdf">Coefficients</a>
%e Triangle begins:
%e 1, -3,
%e 3, 1, -30,
%e 5, -15,
%e 7, 1, 2, 4, 16, -1920,
%e 9, 1, 4, 8, 16, 64, -7680,
%e 11, 1, 2, 8, -960,
%e 13, 1, -120,
%e 15, 1, 2, 4, 8, -3840,
%e 17, 1, 4, -480,
%e 19, 1, 2, 16, 32, 128, -15360,
%e 21, -63,
%e 23, 1, 2, 4, -1920,
%e 25, 1, 4, 8, 64, 128, 512, -61440,
%e The corresponding polynomials are:
%e +----+-----------------------------------------------------------+
%e | x | Polynomials f(z) including the factor (z - 3) |
%e +----+-----------------------------------------------------------+
%e | 1 | z - 3 |
%e | 3 | 3z^2 + z - 30 |
%e | 5 | 5z - 15 |
%e | 7 | 7z^5 + z^4 + 2z^3 + 4z^2 + 16^z - 1920 |
%e | 9 | 9z^6 + z^5 + 4z^4 + 8z^3 + 16z^2 + 64z - 7680 |
%e | 11 | 11z^4 + z^3 + 2z^2 + 8z - 960 |
%e | 13 | 13z^2 + z -120 |
%e | 15 | 15z^5 + z^4 + 2z^3 + 4z^2 + 8z - 3840 |
%e | 17 | 17z^3 + z^2 + 4z - 480 |
%e | 19 | 19z^6 + z^5 + 2z^4 + 16z^3 + 32z^2 + 128z - 15360 |
%e | 21 | 21z - 63 |
%e | 23 | 23z^4 + z^3 + 2z^2 + 4z - 1920 |
%e +----+-----------------------------------------------------------+
%e +----+-----------------------------------------------------------+
%e | x | Polynomials f(z)/(z - 3) |
%e +----+-----------------------------------------------------------+
%e | 1 | 1 |
%e | 3 | 3z + 10 |
%e | 5 | 5 |
%e | 7 | 7z^4 + 22z^3 + 68z^2 + 208z +640 |
%e | 9 | 9z^5 + 28z^4 + 88z^3 + 272z^2 + 832z + 2560 |
%e | 11 | 11z^3 + 34z^2 + 104z + 320 |
%e | 13 | 13z + 40 |
%e | 15 | 15z^4 + 46z^3 + 140z^2 + 424z + 1280 |
%e | 17 | 17z^2 + 52z + 160 |
%e | 19 | 19z^5 + 58z^4 + 176z^3 + 544z^2 + 1664z + 5120 |
%e | 21 | 21 |
%e | 23 | 23z^3 + 70 z^2 + 212z + 640 |
%e +----+-----------------------------------------------------------+
%p for m from 1 by 2 to 27 do: T:=array(1..50,[0$50]):U:=array(1..50,[0$50]):
%p n:=m:ii:=2:xx1:=2:pp1:=0:s:=0:U[1]:=n:U[2]:=1:
%p for q from 1 to 100 while(xx1<>1)do:
%p n1:=3*n+1:
%p for p from 1 to 50 do:
%p p1:=2^p:x1:=floor(n1/p1):x0:=irem(n1,p1):
%p if x0=0 and xx1<> 1
%p then
%p pp1:=p:xx1:=x1:
%p else
%p fi:
%p od:
%p T[ii]:=pp1:n1:=x1:n:=xx1:ii:=ii+1:od:s:=0:
%p for j from 1 to ii-3 do:
%p s:=s+T[j]:U[j+2]:=2^s:
%p od:
%p s:=s+T[ii-2]:s1:=2^s:s:=s+T[ii-1]:
%p s2:=2^s:U[ii]:=s1-s2:
%p W:=array(1..ii-1,[0$ii-1]):
%p W[1]:=U[1]:
%p for l from 2 to ii-1 do:
%p W[l]:=U[l+1]:
%p od:
%p print(m):
%p print(W):
%p od:
%Y Cf. A075680, A171870.
%K sign,tabf
%O 1,2
%A _Michel Lagneau_, Mar 30 2016
| 