Collatz Conjecture Progress

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

Posts: 52
Joined: Wed Aug 26, 2009 8:35 am UTC

Collatz Conjecture Progress

Postby frog42 » Tue May 06, 2014 7:05 pm UTC

From what I can tell off of Wikipedia and Wolfram, it doesn't look like this is currently known. Regrettably, I live in a social vacuum of mathematical pursuits, so I've come here in the hopes that someone can tell me if this is really new information or simply a retread.

Brief Collatz Conjecture refresher: Take any number. If it's odd, multiply by 3 and add 1. If it's even divide by 2. Rinse and repeat and all numbers should eventually reduce to 1.

The "Path" to 1 can be simply notated by recording the number of times you repeat the even number procedure between odd number procedures.

Example for test number 5: [4] #Notice we can then add "2,2,2..." ad infinitum to demonstrate the loop of 1-4-2-1-4-2...
Example for test number 7: [1,1,2,3,4]
Example for test number 6: [X,1,4] #Notice that starting with an even number, we record an "X" for each initial even procedure. This will make sense later.

The "Verbose Path" tracks the individual even/odd procedures performed. A "0" represents that we have not yet reached the last even procedure.

Example for test number 5: [0,0,0,0,4] #The zeros respectively indicate that the first number of the Path will not be X, 1, 2 and 3.
Example for test number 7: [0,1,1,0,2,0,0,3,0,0,0,4] #Notice we only need to discard "X" as a possibility in the beginning.
Example for test number 6: [X,0,1,0,0,0,4] #Here we lock in "X", then discard the possibility of [X,X...] with the first occurrence of "0".

The Verbose Path maps directly onto a binary representation of the test number. [Disclaimer: Someone taught you to read numbers backwards. If you read left-to-right, it makes much more sense to have the smallest placeholder on the left and the largest on the right. That's how I taught myself to notate binary, and it's an important factor in this next part. So please keep in mind that these binary numbers are "backwards". With that in mind, we can add infinite 0's to the right of a number without changing its value.]

For instance, any binary number that begins with 10100 (5) will follow the Verbose Path of [0,0,0,0,4...]. Let's look at the Verbose Path for 101000001 (261): [0,0,0,0,4,0,2,0,0,0,4,1,1,0,2,0,0,3,0,0,0,4]. Notice the Verbose Path for 5 takes five digits to resolve to 1, so 1011 (13) will only follow the same Verbose Path for the first three places, then it will diverge: [0,0,0,3,0,0,0,4]. Now we can look at the Verbose Path for 101100001 (269) to confirm it follows the same path as 1011: [0,0,0,3,0,0,0,4,1,0,0,3,1,0,2,0,0,3,0,0,0,4].

So the "seemingly random" distribution of odd and even numbers presented by the Collatz Conjecture is determined entirely by the binary representation of the number. Next, I converted my Verbose Path's 0's to a polarity-switchable bit and represented the non-0 digits as polarity-switching 0's. I call this the "Wave Path". The last example (269) thereby becomes: [1,1,1,0,-1,-1,-1,0,0,1,1,0,0,-1,0,1,1,0,-1,-1,-1,0]. If you map these out, it forms a wave, which always ends in a perfect sine wave caused by the 1-2-4 loop, represented in Wave Path notation as [0,1,0,-1,0,1...].

My current hypothesis is that the Collatz Conjecture forms a self-correcting wave. Each binary "1" acts like a pebble dropped in a lake in series. I also sometimes envision it as being more closely related to orbital mechanics (of which I admittedly know nothing beyond an old planetary orbit simulator game from my middle school years). I believe there can be some set of uniform rules that indicate the Wave Path of any binary number. I might also note that interesting symmetries are observed in the Wave Paths. 27 and 31 are virtually mirrored, then 25 and 33, the 23 and 35.

So the question is this: have I actually found out anything new or just stumbled blindly upon pre-trod territory? I've found a lot more while satisfying my curiosity on this topic. This is just my latest path of inquiry.

Posts: 52
Joined: Wed Aug 26, 2009 8:35 am UTC

Re: Collatz Conjecture Progress

Postby frog42 » Tue May 06, 2014 10:09 pm UTC

Here's some simple Python analysis code if that helps anyone. Each of the procedures is designed to accept the previous procedure's output as input. (i.e. collatz > verbose_path > wave_path) Sorry I didn't really comment it at all, but as I mentioned, I live in a social vacuum in regards to these pursuits. Also, I don't really have any programming experience, but hopefully since it's Python it's still fairly readable.

Code: Select all

import string
digs = string.digits + string.lowercase

def int2base(x, base): #converts an integer into my form of binary
    if x==0:
      return '0'
   digits = []
   while x:
      digits.append(digs[x % base])
      x /= base
   return ''.join(digits)

def collatz(n): #outputs the Path to 1
   path = []
   power = 0
   x = n
   while x % 2 == 0:
      x = x/2
   while x > 1:
      if x % 2 == 0:
         power += 1
         x = x/2
         if x % 2 == 1:
            power = 0
         x = (x*3) +1
   return path

def verbose_path(p): #converts the Path to Verbose Path
   verbose = []
   while p[0] == 0:
   p[0] = p[0] + 1
   while len(p) > 0:
      if p[0] > 1:
         p[0] = p[0] - 1
   return verbose

def wave_path(p): #converts Verbose Path to Wave Path
   wave = []
   polarity = 1
   while p[0] == "1":
   while len(p) > 0:
      if p[0] == 0:
         while len(p) > 0 and p[0] == 1:
         if polarity == 1:
            polarity = -1
            polarity = 1
   print(wave.count(1) - wave.count(-1))
   return wave

#for i in range(5,271):  #probably not that interesting for anyone but me
#   if i % 2 != 0:
#      print("------" + str(i))
#      print(int2base(i, 2))
#      wave_path(verbose_path(collatz(i)))

n = 269 #Change this number to test other numbers.

User avatar
Forest Goose
Posts: 377
Joined: Sat May 18, 2013 9:27 am UTC

Re: Collatz Conjecture Progress

Postby Forest Goose » Thu May 15, 2014 6:00 am UTC

I've seen, but don't remember exactly where, something along the lines you are discussing - though in different terms.

Aren't you, basically, doing the following (example for 7):

Trajectory: 7 -> 22 -> 11 -> 34 -> 17 -> 52 -> 26 -> 13 -> 40 -> 20 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1
Parity: 1010100100010000
Run Length of 0's: 1,1,2,3,4?

At any rate:

Define 1(x) = 3x + 1 and 0(x) = x / 2 on the rationals. Then, for any finite binary string you get an action by composition. Each of these actions will be of the form x |-> (Ax + b)/ 2^n (A a power of 3, b some goofy sum of elements 3^i*2^j). The following is fairly simple to prove: if B is a binary word starting with 1 and ending in 0 and x an odd integer, then Bx is an integer iff Bx is the |B|th element in x's Collatz trajectory. Finally, using this, if you solve for when Bx is an integer, you will get solutions mod 2^n - these solutions correspond back to your observation about the binary number forms of naturals implying they have related trajectories for a set number of iterations.

Ultimately, all of this, really, just gives the basis for the 2-adic extension - albeit from the less direct, but more informative route of the action of the Collatz function, opposed to just saying "use 3x + 1 and x/2 on Z2".

*I wrote this quick, forgive poor wording choices.
Forest Goose: A rare, but wily, form of goose; best known for dropping on unsuspecting hikers, from trees, to steal sweets.

Return to “Mathematics”

Who is online

Users browsing this forum: No registered users and 14 guests