Playing with Collatz

collatz.txt

given that:
f(2n) = n/2
f(2n+1) = 3n+1

we can see that the pattern translates to a pattern of 4x+(0,1,2,3) such that:
(4x+0)/2 = 2n    (potentially 4x+2 or 4x+0)
(4x+1)   = 2n+1
(4x+2)/2 = 2n+1
(4x+3)   = 2n+1

so that (4x+2)/2 translates to (4x+{1,3})

2/2 = 1   (4x+1) ; 3*1+1  = 4  (4x)
6/2 = 3   (4x+3) ; 3*3+1  = 10 (4x+2)
10/2 = 5  (4x+1) ; 3*5+1  = 16 (4x)
14/2 = 7  (4x+3) ; 3*7+1  = 22 (4x+2)
18/2 = 9  (4x+1) ; 3*9+1  = 28 (4x)
22/2 = 11 (4x+3) ; 3*11+1 = 34 (4x+2)
26/2 = 13 (4x+1) ; 3*13+1 = 40 (4x)
30/2 = 15 (4x+3) ; 3*15+1 = 46 (4x+2)

as you can see from above 4x+{1,3} translates to 4x+{0,2}
so that we can say:

f(4x+1) -> f(4x+0)
f(4x+3) -> f(4x+2)

however, 4x+2 does not always go to 4x+1, it could go to 4x+3, how do we know? well:

f(4*1+3) -> f(4*5+2) -> f(4*2+3)  -> f(4*8+2)
f(4*8+2) -> f(4*4+1) -> f(4*13+0) -> f(4*6+2)
f(4*6+2) -> f(4*3+1) -> f(4*10+0) -> f(4*5+0)
f(4*5+0) -> f(4*2+2) -> f(4*1+1)  -> f(4*4+0)
f(4*4+0) -> f(4*2+0) -> f(4*1+0)  -> f(4*0+2)
f(4*0+2) -> f(4*0+1) -> f(4*1+0)  -> f(4*0+2)

f(4x+2) -> f(4y+3)  (x is odd)
f(4x+2) -> f(4y+1)  (x is even)

f(4*7+2) -> f(4x+3) ? : 30 / 2 -> 15 (4*3+3)
f(4*20+2) -> f(4x+1)? : 82 / 2 -> 41 (4*10+1)
f(4*11+2) -> f(4*5+3) : f(46) -> f(23)
f(4*18+2) -> f(4*9+1) : f(74) -> f(37)

if x is odd, transform 4x+2 to 4y+3  (move up)
if x is even, transform 4x+2 to 4y+1 (move down)

4x+1 always moves to 4y+0
4x+3 always moves to 4y+2
where y is floor(x/2)

f(4*0+2)  -> f(4*0+1) : f(2)  -> f(1)
f(4*1+2)  -> f(4*0+3) : f(6)  -> f(3)
f(4*2+2)  -> f(4*1+1) : f(10) -> f(5)
f(4*3+2)  -> f(4*1+3) : f(14) -> f(7)
f(4*4+2)  -> f(4*2+1) : f(18) -> f(9)
f(4*5+2)  -> f(4*2+3) : f(22) -> f(11)

we can see that
4x+2 -> 4y+3 when (x & 1)
4x+2 -> 4y+1 when !(x & 1)
4x+2 -> 4y+z ->
         y = floor(x/2)
		 z = 2 + -1^(x+1)

ok, so that explains 4x+2's pattern of transformation, how does 4x+1 transform x into y?
When we look at the following table what do we notice?

f(4*0+1) -> f(4*1+0)  : f(1)  -> f(4)
f(4*1+1) -> f(4*4+0)  : f(5)  -> f(16)
f(4*2+1) -> f(4*7+0)  : f(9)  -> f(28)
f(4*3+1) -> f(4*10+0) : f(13) -> f(40)
f(4*4+1) -> f(4*13+0) : f(17) -> f(52)
f(4*5+1) -> f(4*16+0) : f(21) -> f(64)
f(4*6+1) -> f(4*19+0) : f(25) -> f(76)
f(4*7+1) -> f(4*22+0) : f(29) -> f(88)

Upon inspection we can see that given a number of the form 4x+1 will result in a number whose form is 4y+0 where y = 3x+1, so:
f(4x+1) -> 4 * (3 * x + 1)

f(4*22+1) -> 4 * (3 * 22 + 1) = 4 * 67 = 268
f(89)      -> f(268)

f(4*101+1) -> 4 * (3 * 101 + 1) = 4 * 304 = 1216
f(405)     -> f(1216)

Now that we've figured out the pattern of transformation for numbers of the form 4x+1, the only number remaining is
numbers of the form 4x+3. Here's another table to help us out:

f(4*0+3) -> f(4*2+2)  : f(3)  -> f(10)
f(4*1+3) -> f(4*5+2)  : f(7)  -> f(22)
f(4*2+3) -> f(4*8+2)  : f(11) -> f(34)
f(4*3+3) -> f(4*11+2) : f(15) -> f(46)
f(4*4+3) -> f(4*14+2) : f(19) -> f(58)

We can see, that much like 4x+1, 4x+3 uses a similar formula, the only difference? instead of y=3n+1, we have y=3n+2
f(4x+3) -> 4 * (3 * x + 2) + 2

f(4*22+3) -> 4 * (3 * 22 + 2) + 2 = 4 * 68 + 2 = 274
f(91)     -> f(274)

f(4*43+3) -> 4 * (3 * 43 + 2) + 2 = 4 * 131 + 2 = 526
f(175)    -> f(526)

Lets recap, originally we defined the function as follows:
f(2n)   -> n/2
f(2n+1) -> 3n+1

but with our new found knowledge we can define it further as:
f(4n+0)   -> n/2
f(4n+1)   -> 4 * (3 * (n/4) + 1)
f(4n+2)   -> 4 * floor(n/8) + (2 + -1^((n/4)+1))
f(4n+3)   -> 4 * (3 * (n/4) + 2) + 2

By following this function through we can see that:

f(4x+1) will always generate a number that is of the form 4x+0
f(4x+3) will always generate a number that is of the form 4x+2
f(4x+2) will split based on whether or not a given x is odd or even
f(4x+0) will always result in halving the number, this could lead back to forms of 4x+{0,1,2,3}

Now, lets follow an example value. What we're interested in now is what is going on with x:

       x
28 = 4*7 + 0  :: 7 = 3*2 + 1    ::  7 = 4*1 + 3
14 = 4*3 + 2  :: 3 = 3*1 + 0    ::  3 = 4*0 + 3
 7 = 4*1 + 3  :: 1 = 3*0 + 1    ::  1 = 4*0 + 1

88 = 4*22+ 0  ::22 = 3*7 + 1    :: 22 = 4*5 + 2
44 = 4*11+ 0  ::11 = 3*3 + 2    :: 11 = 4*2 + 3
22 = 4*5 + 2  :: 5 = 3*1 + 2    ::  5 = 4*1 + 1
11 = 4*2 + 3  :: 2 = 3*0 + 2    ::  2 = 4*0 + 2

68 = 4*17+ 0  ::17 = 3*5 + 2    :: 17 = 4*4 + 1
34 = 4*8 + 2  :: 8 = 3*2 + 2    ::  8 = 4*2 + 0
17 = 4*4 + 1  :: 4 = 3*1 + 1    ::  4 = 4*1 + 0

104= 4*26+ 0  ::26 = 3*8 + 2    :: 26 = 4*6 + 2
52 = 4*13+ 0  ::13 = 3*4 + 1    :: 13 = 4*3 + 1
26 = 4*6 + 2  :: 6 = 3*2 + 0    ::  6 = 4*1 + 2
13 = 4*3 + 1  :: 3 = 3*1 + 0    ::  3 = 4*0 + 3

80 = 4*20+ 0  ::20 = 3*6 + 2    :: 20 = 4*5 + 0
40 = 4*10+ 0  ::10 = 3*3 + 1    :: 10 = 4*2 + 2
20 = 4*5 + 0  :: 5 = 3*1 + 2    ::  5 = 4*1 + 1
10 = 4*2 + 2  :: 2 = 3*0 + 2    ::  2 = 4*0 + 2
 5 = 4*1 + 1  :: 1 = 3*0 + 1    ::  1 = 4*0 + 1
 
16 = 4*4 + 0  :: 4 = 3*1 + 1    ::  4 = 4*1 + 0
 8 = 4*2 + 0  :: 2 = 3*0 + 2    ::  2 = 4*0 + 2
 4 = 4*1 + 0  :: 1 = 3*0 + 1    ::  1 = 4*0 + 1
 2 = 4*0 + 2  :: 0 = 3*0 + 0    ::  0 = 4*0 + 0
 1 = 4*0 + 1  :: 0 = 3*0 + 0    ::  0 = 4*0 + 0
 

So we can see from this pattern, that x for the most part likes to divide itself in half, but not always. I wonder what the rule is.

Let's consider this:

n /= 2 if !(n & 1)
n = 3n+1 if (n & 1)

3n+1 -> (n + n + n + 1) 
since we know that n must be odd in order to be evaluated as 3n+1 we could say that:
(n + n + n + 1) -> (2m+1 + 2m+1 + 2m+1 + 1) where m is (n-1)/2

eg:
(3 + 3 + 3 + 1) -> (2*1+1 + 2*1+1 + 2*1+1 + 1) = (3 + 3 + 3 + 1) -> (3 + 3 + 3 + 1) = 10

we can also say that:
(2m+1 + 2m+1 + 2m+1 + 1) -> (2m + 2m + 2m + 1 + 1 + 1 + 1) -> (6m + 4) = 10
(2*1+1 + 2*1+1 + 2*1+1 + 1) = (2*1 + 2*1 + 2*1 + 1 + 1 + 1 + 1) = (6*1 + 4) = 10
(2m + 2m + 2m) -> 3(2m) -> 6m

what about m=2
(5 + 5 + 5 + 1) -> (2*2+1 + 2*2+1 + 2*2+1 + 1) -> (2*2 + 2*2 + 2*2 + 1 + 1 + 1 + 1) -> (6*2 + 4) = 16
(17 + 17 + 17 + 1) -> (2*8+1 + 2*8+1 + 2*8+1 + 1) -> (2*8 + 2*8 + 2*8 + 1 + 1 + 1 + 1) -> (6*8 + 4) = 52

so now we can define f() as:
f(2n) -> n/2
f(2n+1) -> 4 + 6((n-1)/2)

Thinking of it like this we can see the transformation as:
f( 1) -> 4 + (6*0) = 4
f( 2) -> 2 / 2     = 1
f( 3) -> 4 + (6*1) = 10
f( 4) -> 4 / 2     = 2
f( 5) -> 4 + (6*2) = 16
f( 6) -> 6 / 2     = 3
f( 7) -> 4 + (6*3) = 22
f( 8) -> 8 / 2     = 4
f( 9) -> 4 + (6*4) = 28
f(10) -> 10 / 2    = 5
f(11) -> 4 + (6*5) = 34
f(12) -> 12 / 2    = 6
f(13) -> 4 + (6*6) = 40
f(14) -> 14 / 2    = 7
f(15) -> 4 + (6*7) = 46

4*2 + 6*2 = 8 + 12 = 20
4*3 + 6*3 = 12 + 18 = 30
4*4 + 6*4 = 16 + 24 = 40
4*5 + 6*5 = 20 + 30 = 50

f'(3) -> 
       (4 + (6 * (((4 + (6 * ((3-1)/2)))/2)-1)/2))/2^4

f'(6) ->
	   (4 + (6 * (((4 + (6 * (((6/2)-1)/2)))/2)-1)/2))/2^4
	   
f'(n) -> the number of times n gets divided by 2 before reaching 1, or rather:
f'(1)    -> 0
f'(2n)   -> 1 + f(n/2)
f'(2n+1) -> 1 + f(3n+1)

A quick ruby script can be used to obtain a visual expansion of this expansion:
--------------------------------------
#! /usr/bin/env ruby

def form dsp, n
  str = ""

  if (n & 1) == 1
    str = "(4 + (6 * ((#{dsp}-1)/2)))"
    n = 3*n+1
  else
    str = "(#{dsp}/2)"
    n = n / 2;
  end

  [ str, n ]
end

n = 27
n = ARGV[0].to_i if ARGV[0].to_i > 0
dsp = n.to_s

while n != 1
  dsp, n = form(dsp, n)
end

puts dsp
puts n   # should always print 1.
--------------------------------------

so f'(27) yields something that looks like this:
(((((4 + (6 * ((((((((4 + (6 * ((((4 + (6 * ((((4 + (6 * ((((((4 + (6 * (((((((4 + (6 * (((((4 + (6 * (((((4 + (6 * (((((((4 + (6 * ((((4 +
(6 * ((((4 + (6 * ((((4 + (6 * ((((((4 + (6 * ((((4 + (6 * ((((4 + (6 * ((((4 + (6 * ((((4 + (6 * ((((4 + (6 * (((((4 + (6 * ((((4 + (6 *
(((((4 + (6 * ((((4 + (6 * ((((4 + (6 * ((((((4 + (6 * (((((4 + (6 * ((((4 + (6 * ((((4 + (6 * ((((4 + (6 * (((((4 + (6 * ((((4 + (6 *
((((4 + (6 * (((((4 + (6 * ((((4 + (6 * (((((4 + (6 * (((((4 + (6 * ((((4 + (6 * ((((4 + (6 * ((((4 + (6 * ((((4 + (6 * (((((4 + (6 *
((((4 + (6 * ((27-1)/2)))/2)-1)/2)))/2)/2)-1)/2)))/2)-1)/2)))/2)-1)/2)))/2)-1)/2)))/2)-1)/2)))/2)/2)-1)/2)))/2)/2)-1)/2)))/2)-1)/2)))/2)/
2)-1)/2)))/2)-1)/2)))/2)-1)/2)))/2)/2)-1)/2)))/2)-1)/2)))/2)-1)/2)))/2)-1)/2)))/2)/2)-1)/2)))/2)/2)/2)-1)/2)))/2)-1)/2)))/2)-1)/2)))/2)/
2)-1)/2)))/2)-1)/2)))/2)/2)-1)/2)))/2)-1)/2)))/2)-1)/2)))/2)-1)/2)))/2)-1)/2)))/2)-1)/2)))/2)/2)/2)-1)/2)))/2)-1)/2)))/2)-1)/2)))/2)-1)/2)))/
2)/2)/2)/2)-1)/2)))/2)/2)-1)/2)))/2)/2)-1)/2)))/2)/2)/2)/2)-1)/2)))/2)/2)/2)-1)/2)))/2)-1)/2)))/2)-1)/2)))/2)/2)/2)/2)/2)-1)/2)))/2)/2)/2)/2)

If we count the number of times /2 appears we can find the answer to be 111 times, and same:

f'(7) yields:
(((((4 + (6 * ((((((4 + (6 * (((((4 + (6 * ((((4 + (6 * ((((4 + (6 * ((7-1)/2)))/2)-1)/2)))/2)-1)/2)))/2)/2)-1)/2)))/2)/2)/2)-1)/2)))/2)/2)/2)/2)

If we count the number of times /2 appears in this equation, we will find 16.

Can this formula be reversed?

XXX
TODO: CONTINUE WORKING ON THIS!