Fortran bit intrinsics for fast Collatz sequence computation

1

The intrinsic functions shiftr and trailz can be very helpful in the computation of Collatz sequences. Given a current value x, an odd number, we can compute the next value, y, using

if (btest(x,0)) then
   v=3*x+1
else
   v = x
endif
nz=trailz(v); y=shiftr(v,nz); x =y

An advantage of this code is that the result, y, is also odd, which facilitates continuation of the calculation of the sequence. These lines can be placed in a DO loop to calculate an entire sequence with a specified initial value.

x=27
do i=1,41 ! 41 iterations are known to take us to 1
if (btest(x,0)) then
   v=3*x+1
else
   v = x
endif
nz=trailz(v); y=shiftr(v,nz)
print *, i,x,v,y; x =y
if(x.eq.1)exit !assumes truth of Collatz conjecture
end do
2

If, instead of starting with 27, we start with 49, we obtain a startling result: After just two 3x+1 steps and the appropriate number of halvings, we obtain 7, which is the square root of 49!