## 0710: "Collatz Conjecture"

This forum is for the individual discussion thread that goes with each new comic.

Moderators: Moderators General, Prelates, Magistrates

Prior Semblance
Posts: 2
Joined: Sat Feb 06, 2010 2:39 am UTC

### Re: "Collatz Conjecture" Discussion

The conjecture seems like common sense to me. All even numbers divided by 2 constantly will eventually reach 1 unless they become odd and all the odd numbers will be turned even right away. Ridiculously large numbers would only change the amount of steps.

squareroot
Posts: 548
Joined: Tue Jan 12, 2010 1:04 am UTC
Contact:

### Re: "Collatz Conjecture" Discussion

Yes, but although the odd numbers become even, what if there is some even number that goes to an odd number than goes to an even number that goes to an even number that goes to an odd number etc. etc... until it eventually reaches the same even number again. Then, it would never reach 1. Or, since the odd->even operation increases the number by more than a factor of three, it might go to infinity (albeit zig-zag style, without ever dropping all the way back down to 1.
<signature content="" style="tag:html;" overused meta />
Good fucking job Will Yu, you found me - __ -

Chrisfs
Posts: 49
Joined: Fri Apr 10, 2009 7:54 pm UTC

### Re: "Collatz Conjecture" Discussion

I did this as a kid without even knowing the name or that it was a formal mystery. I just saw it in a math puzzle book.

-.Mateo.-
Posts: 264
Joined: Sun Jun 28, 2009 12:01 am UTC
Location: Location Location

### Re: "Collatz Conjecture" Discussion

Prior Semblance wrote:The conjecture seems like common sense to me. All even numbers divided by 2 constantly will eventually reach 1 unless they become odd and all the odd numbers will be turned even right away. Ridiculously large numbers would only change the amount of steps.

your first assumption is wrong, all even numbers WON'T eventually reach to 1, for example 6: 6/2 = 3. It's true that all odds will give you evens, but as long as the evens give you odds, you'll keep getting larger numbers: The shortes way to get from an odd to another odd is with only 1 even in between, that means that given an odd n, the shortest way to get to an odd is: (3n+1)/2, that new number will always be bigger than n (its 3n/2 +0.5).
Magus wrote:If history is to change, let it change. If the world is to be destroyed, so be it. If my fate is to die, I must simply laugh.

Just as you touch the energy of every life form you meet, so, too, will will their energy strengthen you.

RebeccaRGB
Posts: 336
Joined: Sat Mar 06, 2010 7:36 am UTC
Location: Lesbians Love Bluetooth
Contact:

### Re: "Collatz Conjecture" Discussion

I finally registered so I could say that I just wasted a couple hours on this:

http://www.kreativekorp.com/epsilon/collatz.jpg

Thanks Randall for taking me down with you.
Stephen Hawking: Great. The entire universe was destroyed.
Fry: Destroyed? Then where are we now?
Al Gore: I don't know. But I can darn well tell you where we're not—the universe!

SEE
Posts: 73
Joined: Mon Jun 30, 2008 1:58 pm UTC

### Re: "Collatz Conjecture" Discussion

Guys, it's already been checked up to 5 × 260. So you're going to have to use something bigger than 64-bit integers in your programming to find the disproving number. Get out the 128-bit or bignum libraries.

Or join the BOINC project for it http://boinc.thesonntags.com/collatz/, currently testing numbers in the 2.3 quintillion range.

aido179
Posts: 16
Joined: Thu Dec 04, 2008 5:03 pm UTC

### Re: "Collatz Conjecture" Discussion

my cs algorithms professor called this one the "hailstone algorithm". never mentioned collatz. unusual, i would expect it to be called hailstone, seems like a better buzzword.

marketdoctor
Posts: 10
Joined: Thu Sep 04, 2008 6:19 pm UTC

### Re: "Collatz Conjecture" Discussion

Collatz conjecture.

I realized I *almost* had a proof down cold, but all I could come up with was a proof of your existence in a higher power. (If you want to make it interesting, pull out a ten-pound note with Charles Darwin's picture on it...or if you don't have access to British currency, someone who shares a birthday with Darwin, like Lincoln. If I'm right, give it to my favorite charity for earthquake relief, if I'm wrong, give it to the charity of your choice for the same cause. Write it down now, so there won't be cheating.)

Now suppose there's a function f(x) where x is a positive integer and f(x) is the number of steps to reach 1 for the first time using the Collatz function. Suppose further we pick a number, N, that we want to see has a finite solution. Suppose further that that the maximum value for f(x) is bounded by f(3^3m) for any non-negative integer m, and the smallest is f(2^3m); the latter is trivial since for f(2^q) for integer q, the number of steps is q. Where that gets interesting is that f(4^3q) is only 2q, since f(4^q)=f(2^q* 2^q=f(2^2q). More clearly, suppose:

N=f(n) such that 4^3m < N < 2^3m for integer m and n.
S=f(3^3m)
T=f(2^3m), and
O=f(4^3m).

Then Collatz would be true as long as S(3^3m) were solvable, which would also explain why it's so hard to find a binary solution. (I can't even explain a finite binary solution a third of the time.) The problem is, as f(63,728,127)>f(129,140,163) shows us, max f(x) is NOT always 3^3m (obviously).

Spoiler:
So with 63,728,127, I thought I'd had it cold, but it's S>/=N> O> T.

The proof of your faith in a higher power is that you're now begging for one to make that pun go away.
If you feel better, Charles Darwin once visited Santiago, and they really could use the money. Lucky for you, I probably wrote down the same charity you did. (It was close enough.)

TimeSpaceMage
Posts: 23
Joined: Thu Nov 26, 2009 4:05 am UTC
Contact:

### Re: "Collatz Conjecture" Discussion

Arvedui wrote:I felt really odd and geeky because as soon as I read this comic, I wrote a quick Java program to test this.

Then I came here, and now I feel... inferior.

I feel like I belong here, hahaha.
Ironic, since it contradicts the premise of the comic.

tictactictac
Posts: 3
Joined: Sun Feb 14, 2010 11:13 pm UTC

### Re: "Collatz Conjecture" Discussion

i tried it out with 95, took almost an eternity

Okapi
Posts: 53
Joined: Thu Oct 30, 2008 8:37 pm UTC

### Re: "Collatz Conjecture" Discussion

When I get my computer hooked up again, I'll write a Python code to try everything to some arbitrarily large number. Then, since I just read Foucault's Pendulum, I will round it off by writing a program that imports a soul and uses it to find the true name of God. If I'm still hungry, I'll finish up by solving all the world's problems.

Really more relevant to Python, I guess, but I'm pretty sure such a program would be ten lines, tops.

Background_Noise
Posts: 53
Joined: Fri Feb 26, 2010 4:39 pm UTC

### Re: "Collatz Conjecture" Discussion

I'm writing a C++ program to run through testing numbers, and appending any that dont fit to a text file. A pointless exercise i imagine, as the test file will be blank.

But my god im rusty... didnt know one could lose ability at writing that quickly.

EDIT: Appeding to a file is of course pointless... the program will get stuck on that number if it cant be done...
Tea makes the world go around,

And coffee makes it go a bit faster.

leifbk
Posts: 33
Joined: Wed Nov 26, 2008 7:24 am UTC
Location: Bærum, Norway
Contact:

### Re: "Collatz Conjecture" Discussion

I've been fiddling with my PostgreSQL implementation again, and now it really flies, gobbling 1000 numbers a second on my ancient P4@3GHz:

Code: Select all

`CREATE TABLE collatz (    val         BIGINT primary key,    next_val    BIGINT,    max_val     BIGINT,    terms       INTEGER);CREATE OR REPLACE FUNCTION disp_seq(BIGINT) RETURNS TEXT AS dollardollarDECLARE    col collatz%ROWTYPE;     str TEXT;BEGIN    SELECT * FROM collatz WHERE val = \$1 INTO col;    str := col.val::TEXT;    IF col.val <> 1    THEN        str := str || ' ' || disp_seq(col.next_val);    END IF;    RETURN str;ENDdollardollar LANGUAGE PLPGSQL IMMUTABLE;CREATE OR REPLACE FUNCTION gen_collatz(BIGINT, BIGINT) RETURNS VOID AS dollardollar-- Proc to generate Collatz sequencesDECLARE    s BIGINT := \$1;    x BIGINT;    n BIGINT;    m BIGINT;    t INTEGER;    known BOOLEAN;    col collatz%ROWTYPE;BEGIN    WHILE s <= \$2 LOOP        x := s;        m := s;        t := 1;        known := FALSE;        WHILE x <> 1 AND known IS FALSE LOOP            IF x % 2 = 0 THEN                n := x / 2;            ELSE                n := x * 3 + 1;            END IF;            PERFORM * FROM collatz WHERE val = x;            IF NOT FOUND THEN                INSERT INTO collatz (val, next_val) VALUES (x, n);            END IF;            IF n > m THEN                m := n;            END IF;            x := n;            IF x < s THEN -- note: this test requires that all x < s are already in the db                known := TRUE;                SELECT * FROM collatz WHERE val = x INTO col;                t := t + col.terms;                IF col.max_val > m THEN                    m := col.max_val;                END IF;            ELSE                t := t + 1;            END IF;        END LOOP;        -- RAISE NOTICE 'Trajectory of %: %', s, disp_seq(s);        RAISE NOTICE '%: % terms, max %.', s, t, m;        UPDATE collatz SET max_val = m, terms = t WHERE val = s;        s := s + 1;    END LOOP;    RETURN;ENDdollardollar LANGUAGE PLPGSQL VOLATILE;`

For some reason, two consecutive dollar signs do strange and mysterious things to the formatting here. I've replaced them with the obvious text.

Note that an even number will never go through more than one iteration, when it will reach a number already in the database. The odd numbers may go through several iterations, but usually not many.

By the way, here's the high water mark below 2 millions:

Code: Select all

`collatz=> select * from collatz where max_val = (select val from collatz order by val desc limit 1);   val   | next_val |   max_val    | terms---------+----------+--------------+------- 1988859 |  5966578 | 156914378224 |   405(1 row)`

That's a max value of 156 billions, soaring high above the maximum 32 bit integer limit.

And my friends stopped calling a long time ago

RebeccaRGB
Posts: 336
Joined: Sat Mar 06, 2010 7:36 am UTC
Location: Lesbians Love Bluetooth
Contact:

### Re: "Collatz Conjecture" Discussion

After a few more hours of wasted time, I present Collatz Explorer, a Java Swing app to explore the Collatz graph. It uses BigIntegers so the sky's the limit.

Code: Select all

`/* * Collatz Explorer - Swing application to visually traverse the Collatz graph. * Copyright (c) 2010 Rebecca G. Bettencourt *  * Permission is hereby granted, free of charge, to any person * obtaining a copy of this software and associated documentation * files (the "Software"), to deal in the Software without * restriction, including without limitation the rights to use, * copy, modify, merge, publish, distribute, sublicense, and/or sell * copies of the Software, and to permit persons to whom the * Software is furnished to do so, subject to the following * conditions: *  * The above copyright notice and this permission notice shall be * included in all copies or substantial portions of the Software. *  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT * HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR * OTHER DEALINGS IN THE SOFTWARE. */import java.awt.*;import java.awt.event.*;import java.math.*;import javax.swing.*;public class CollatzExplorer extends JComponent implements MouseListener, KeyListener {   private static final long serialVersionUID = 1L;   private static final BigInteger ZERO = BigInteger.valueOf(0);   private static final BigInteger ONE = BigInteger.valueOf(1);   private static final BigInteger TWO = BigInteger.valueOf(2);   private static final BigInteger THREE = BigInteger.valueOf(3);   private static final BigInteger FOUR = BigInteger.valueOf(4);   private static final BigInteger SIX = BigInteger.valueOf(6);   private static final Color oneTwoFourColor = new Color(0xFF00FF00);   private static final Color oneTwoFourBacktraceColor = new Color(0xFF80FF80);   private static final Color divTwoColor = new Color(0xFF000000);   private static final Color divTwoBacktraceColor = new Color(0xFF808080);   private static final Color timesThreeMinusOneColor = new Color(0xFFFF0000);   private static final Color timesThreeMinusOneBacktraceColor = new Color(0xFFFF8080);   private static final String[] help = new String[] {      "Collatz Explorer",      "\u00A9 2010 Rebecca G. Bettencourt",      "",      "Click any number to move to that number",      "Up Arrow - Move up the current branch",      "Down Arrow - Move down the current branch",      "Left Arrow - Move to the top of the current branch or to the parent branch",      "Right Arrow - Move to the child branch",      "Backspace - Move towards the root of the graph",      "Enter - Move to the child branch or down the current branch",      "Home, Escape, ` - Move directly to the root of the graph",      "[ - Decrease spacing between columns (for smaller numbers)",      "] - Increase spacing between columns (for larger numbers)",      "\\ - Return to default spacing between columns",      "0 through 9, Backspace - Input a number",      "Enter - Move to the inputted number",      "Escape - Cancel input",      "F1, Help, Space, ? - Show help screen",   };      private BigInteger seed = FOUR;   private int rowHeight = 32;   private int colWidth = 96;   private StringBuffer input = null;   private boolean showHelp = false;      public CollatzExplorer() {      addMouseListener(this);      addKeyListener(this);      setFocusable(true);   }      public BigInteger getSeed() {      return seed;   }      public void setSeed(BigInteger seed) {      this.seed = (seed.compareTo(TWO) <= 0) ? FOUR : seed;      repaint();   }      protected void paintComponent(Graphics g) {      FontMetrics fmx = g.getFontMetrics();      int w = getWidth();      int h = getHeight();      // BACKGROUND      g.setColor(Color.white);      g.fillRect(0, 0, w, h);      g.setColor(new Color(0xFFFFFFF8));      g.fillRect(0, 0, w, rowHeight+rowHeight/2);      g.setColor(Color.yellow);      g.drawLine(0, rowHeight+rowHeight/2, w, rowHeight+rowHeight/2);      // LINES      if (seed.compareTo(TWO) <= 0 || seed.equals(FOUR)) {         g.setColor(oneTwoFourColor);         g.drawLine(colWidth/2, rowHeight, colWidth+colWidth/2, rowHeight);         g.drawLine(colWidth/2, rowHeight, colWidth, rowHeight*2);         g.drawLine(colWidth+colWidth/2, rowHeight, colWidth, rowHeight*2);      } else {         g.setColor(seed.mod(TWO).equals(ZERO) ? divTwoColor : timesThreeMinusOneColor);         g.drawLine(colWidth, rowHeight, colWidth, rowHeight*2);         BigInteger prev = seed.mod(TWO).equals(ZERO) ? seed.divide(TWO) : seed.multiply(THREE).add(ONE);         int colX = colWidth;         while (colX+colWidth/2 < w) {            if (prev.compareTo(TWO) <= 0 || prev.equals(FOUR)) {               g.setColor(oneTwoFourBacktraceColor);               g.drawLine(colX, rowHeight, colX+colWidth, rowHeight-12);               g.drawLine(colX, rowHeight, colX+colWidth, rowHeight+10);               g.drawLine(colX+colWidth, rowHeight-12, colX+colWidth, rowHeight+10);               break;            } else {               g.setColor(prev.mod(TWO).equals(ZERO) ? divTwoBacktraceColor : timesThreeMinusOneBacktraceColor);               g.drawLine(colX, rowHeight, colX+colWidth, rowHeight);               prev = prev.mod(TWO).equals(ZERO) ? prev.divide(TWO) : prev.multiply(THREE).add(ONE);               colX += colWidth;            }         }      }      g.setColor(divTwoColor);      g.drawLine(colWidth, rowHeight*2, colWidth, h);      {         BigInteger rowSeed = (seed.compareTo(TWO) <= 0) ? FOUR : seed;         int rowY = rowHeight*2;         while (rowY+rowHeight/2 < h) {            if (!rowSeed.equals(FOUR) && rowSeed.mod(SIX).equals(FOUR)) {               g.setColor(timesThreeMinusOneColor);               g.drawLine(colWidth, rowY, colWidth*2, rowY);               g.setColor(divTwoColor);               g.drawLine(colWidth*2, rowY, w, rowY);            }            rowSeed = rowSeed.shiftLeft(1);            rowY += rowHeight;         }      }      // NUMBERS      if (seed.compareTo(TWO) <= 0 || seed.equals(FOUR)) {         drawLabel(g, fmx, "1", colWidth/2, rowHeight, false);         drawLabel(g, fmx, "2", colWidth+colWidth/2, rowHeight, false);      } else {         BigInteger prev = seed.mod(TWO).equals(ZERO) ? seed.divide(TWO) : seed.multiply(THREE).add(ONE);         int colX = colWidth;         while (colX+colWidth/2 < w) {            if (prev.compareTo(TWO) <= 0 || prev.equals(FOUR)) {               drawLabel(g, fmx, prev.toString(), colX, rowHeight, colX != colWidth);               colX += colWidth;               if (colX+colWidth/2 < w) {                  drawLabel(g, fmx, "1", colX, rowHeight-12, true);                  drawLabel(g, fmx, "2", colX, rowHeight+10, true);               }               break;            } else {               drawLabel(g, fmx, prev.toString(), colX, rowHeight, colX != colWidth);               prev = prev.mod(TWO).equals(ZERO) ? prev.divide(TWO) : prev.multiply(THREE).add(ONE);               colX += colWidth;            }         }      }      {         BigInteger rowSeed = (seed.compareTo(TWO) <= 0) ? FOUR : seed;         int rowY = rowHeight*2;         while (rowY+rowHeight/2 < h) {            drawLabel(g, fmx, rowSeed.toString(), colWidth, rowY, false);            if (!rowSeed.equals(FOUR) && rowSeed.mod(SIX).equals(FOUR)) {               BigInteger colSeed = rowSeed.subtract(ONE).divide(THREE);               int colX = colWidth*2;               while (colX+colWidth/2 < w) {                  drawLabel(g, fmx, colSeed.toString(), colX, rowY, false);                  colSeed = colSeed.shiftLeft(1);                  colX += colWidth;               }            }            rowSeed = rowSeed.shiftLeft(1);            rowY += rowHeight;         }      }      // INPUT BOX      if (input != null) {         int dw = Math.max(200, fmx.stringWidth(input.toString())+50);         int dh = 60+fmx.getHeight()*2;         int dx = (w-dw)/2;         int dy = (h-dh)/2;         g.setColor(Color.black);         g.fillRect(dx, dy, dw, dh);         g.setColor(new Color(0xFF0080FF));         g.fillRect(dx+1, dy+1, dw-2, dh-2);         g.setColor(Color.cyan);         g.fillRect(dx+2, dy+2, dw-4, dh-4);         g.setColor(new Color(0xFF0080FF));         g.fillRect(dx+3, dy+3, dw-6, dh-6);         g.setColor(Color.black);         g.fillRect(dx+4, dy+4, dw-8, dh-8);         g.setColor(Color.white);         g.fillRect(dx+5, dy+5, dw-10, dh-10);         g.setColor(Color.black);         g.drawString("Number to search for:", dx+20, dy+20+fmx.getAscent());         g.fillRect(dx+20, dy+30+fmx.getAscent(), dw-40, 10+fmx.getHeight());         g.setColor(Color.white);         g.fillRect(dx+21, dy+31+fmx.getAscent(), dw-42, 8+fmx.getHeight());         g.setColor(Color.black);         g.drawString(input.toString(), dx+25, dy+35+fmx.getAscent()*2);      }      // HELP      if (showHelp) {         int th = fmx.getHeight() * help.length;         int tw = 0;         for (String line : help) {            int lw = fmx.stringWidth(line);            if (lw > tw) tw = lw;         }         int dw = tw+40;         int dh = th+40;         int dx = (w-dw)/2;         int dy = (h-dh)/2;         int tx = dx+20;         int ty = dy+20+fmx.getAscent();         g.setColor(Color.black);         g.fillRect(dx, dy, dw, dh);         g.setColor(new Color(0xFF0080FF));         g.fillRect(dx+1, dy+1, dw-2, dh-2);         g.setColor(Color.cyan);         g.fillRect(dx+2, dy+2, dw-4, dh-4);         g.setColor(new Color(0xFF0080FF));         g.fillRect(dx+3, dy+3, dw-6, dh-6);         g.setColor(Color.black);         g.fillRect(dx+4, dy+4, dw-8, dh-8);         g.setColor(Color.white);         g.fillRect(dx+5, dy+5, dw-10, dh-10);         g.setColor(Color.black);         for (String line : help) {            g.drawString(line, tx, ty);            ty += fmx.getHeight();         }      }   }      public void mouseEntered(MouseEvent e) {}   public void mouseExited(MouseEvent e) {}   public void mousePressed(MouseEvent e) {      requestFocusInWindow();   }   public void mouseReleased(MouseEvent e) {}   public void mouseClicked(MouseEvent e) {      if (showHelp) {         showHelp = false;         repaint();      } else if (input == null) {         int x = (e.getX() + colWidth/2) / colWidth;         int y = (e.getY() + rowHeight/2) / rowHeight;         if (y <= 1) {            if (x <= 1) {               setSeed(seed.mod(TWO).equals(ZERO) ? seed.divide(TWO) : seed.multiply(THREE).add(ONE));            } else {               while (x-->0) {                  setSeed(seed.mod(TWO).equals(ZERO) ? seed.divide(TWO) : seed.multiply(THREE).add(ONE));               }            }         } else {            BigInteger rowSeed = (seed.compareTo(TWO) <= 0) ? FOUR : seed;            rowSeed = rowSeed.shiftLeft(y-2);            if (x <= 1) {               setSeed(rowSeed);            } else if (rowSeed.mod(SIX).equals(FOUR)) {               BigInteger colSeed = rowSeed.subtract(ONE).divide(THREE);               colSeed = colSeed.shiftLeft(x-2);               setSeed(colSeed);            }         }      }   }      public void keyPressed(KeyEvent e) {      if (showHelp) {         showHelp = false;         repaint();      } else if (input != null) {         switch (e.getKeyCode()) {         case KeyEvent.VK_0:         case KeyEvent.VK_NUMPAD0:            input.append('0');            repaint();            break;         case KeyEvent.VK_1:         case KeyEvent.VK_NUMPAD1:            input.append('1');            repaint();            break;         case KeyEvent.VK_2:         case KeyEvent.VK_NUMPAD2:            input.append('2');            repaint();            break;         case KeyEvent.VK_3:         case KeyEvent.VK_NUMPAD3:            input.append('3');            repaint();            break;         case KeyEvent.VK_4:         case KeyEvent.VK_NUMPAD4:            input.append('4');            repaint();            break;         case KeyEvent.VK_5:         case KeyEvent.VK_NUMPAD5:            input.append('5');            repaint();            break;         case KeyEvent.VK_6:         case KeyEvent.VK_NUMPAD6:            input.append('6');            repaint();            break;         case KeyEvent.VK_7:         case KeyEvent.VK_NUMPAD7:            input.append('7');            repaint();            break;         case KeyEvent.VK_8:         case KeyEvent.VK_NUMPAD8:            input.append('8');            repaint();            break;         case KeyEvent.VK_9:         case KeyEvent.VK_NUMPAD9:            input.append('9');            repaint();            break;         case KeyEvent.VK_BACK_SPACE:            if (input.length() > 0) {               input.deleteCharAt(input.length()-1);               repaint();            }            break;         case KeyEvent.VK_ENTER:            if (input.length() > 0) {               setSeed(new BigInteger(input.toString()));            }            input = null;            repaint();            break;         case KeyEvent.VK_ESCAPE:         case KeyEvent.VK_CLEAR:            input = null;            repaint();            break;         case KeyEvent.VK_F1:         case KeyEvent.VK_HELP:         case KeyEvent.VK_SPACE:         case KeyEvent.VK_SLASH:            showHelp = true;            repaint();            break;         }      } else {         switch (e.getKeyCode()) {         case KeyEvent.VK_UP:            if (seed.mod(TWO).equals(ZERO)) {               setSeed(seed.divide(TWO));            }            break;         case KeyEvent.VK_DOWN:            setSeed(seed.shiftLeft(1));            break;         case KeyEvent.VK_LEFT:            if (seed.mod(TWO).equals(ZERO)) {               while (!(seed.compareTo(TWO) <= 0 || seed.equals(FOUR)) && seed.mod(TWO).equals(ZERO)) {                  setSeed(seed.divide(TWO));               }            } else {               setSeed(seed.multiply(THREE).add(ONE));            }            break;         case KeyEvent.VK_RIGHT:            if (seed.mod(SIX).equals(FOUR)) {               setSeed(seed.subtract(ONE).divide(THREE));            }            break;         case KeyEvent.VK_BACK_SPACE:            setSeed(seed.mod(TWO).equals(ZERO) ? seed.divide(TWO) : seed.multiply(THREE).add(ONE));            break;         case KeyEvent.VK_ENTER:            if (!seed.equals(FOUR) && seed.mod(SIX).equals(FOUR)) {               setSeed(seed.subtract(ONE).divide(THREE));            } else {               setSeed(seed.shiftLeft(1));            }            break;         case KeyEvent.VK_HOME:         case KeyEvent.VK_ESCAPE:         case KeyEvent.VK_CLEAR:         case KeyEvent.VK_BACK_QUOTE:            setSeed(FOUR);            break;         case KeyEvent.VK_OPEN_BRACKET:         case KeyEvent.VK_SUBTRACT:            colWidth -= 16;            if (colWidth < 32) colWidth = 32;            repaint();            break;         case KeyEvent.VK_CLOSE_BRACKET:         case KeyEvent.VK_ADD:            colWidth += 16;            repaint();            break;         case KeyEvent.VK_BACK_SLASH:         case KeyEvent.VK_MULTIPLY:         case KeyEvent.VK_DIVIDE:         case KeyEvent.VK_EQUALS:            colWidth = 96;            repaint();            break;         case KeyEvent.VK_0:         case KeyEvent.VK_NUMPAD0:            input = new StringBuffer("0");            repaint();            break;         case KeyEvent.VK_1:         case KeyEvent.VK_NUMPAD1:            input = new StringBuffer("1");            repaint();            break;         case KeyEvent.VK_2:         case KeyEvent.VK_NUMPAD2:            input = new StringBuffer("2");            repaint();            break;         case KeyEvent.VK_3:         case KeyEvent.VK_NUMPAD3:            input = new StringBuffer("3");            repaint();            break;         case KeyEvent.VK_4:         case KeyEvent.VK_NUMPAD4:            input = new StringBuffer("4");            repaint();            break;         case KeyEvent.VK_5:         case KeyEvent.VK_NUMPAD5:            input = new StringBuffer("5");            repaint();            break;         case KeyEvent.VK_6:         case KeyEvent.VK_NUMPAD6:            input = new StringBuffer("6");            repaint();            break;         case KeyEvent.VK_7:         case KeyEvent.VK_NUMPAD7:            input = new StringBuffer("7");            repaint();            break;         case KeyEvent.VK_8:         case KeyEvent.VK_NUMPAD8:            input = new StringBuffer("8");            repaint();            break;         case KeyEvent.VK_9:         case KeyEvent.VK_NUMPAD9:            input = new StringBuffer("9");            repaint();            break;         case KeyEvent.VK_F1:         case KeyEvent.VK_HELP:         case KeyEvent.VK_SPACE:         case KeyEvent.VK_SLASH:            showHelp = true;            repaint();            break;         }      }   }   public void keyReleased(KeyEvent e) {}   public void keyTyped(KeyEvent e) {}      private static void drawLabel(Graphics g, FontMetrics fmx, String str, int x, int y, boolean faded) {      int tw = fmx.stringWidth(str);      int tx = x-tw/2;      int th = fmx.getHeight();      int ty = y-th/2;      int tb = ty+fmx.getAscent();      g.setColor(faded ? Color.gray : Color.black);      g.fillRect(tx-4, ty-2, tw+8, th+4);      g.setColor(faded ? Color.white : new Color(0xFFEEEEEE));      g.fillRect(tx-3, ty-1, tw+6, th+2);      g.setColor(faded ? Color.gray : Color.black);      g.drawString(str, tx, tb);   }      public static void main(String[] args) {      JFrame f = new JFrame("Collatz Explorer");      CollatzExplorer ce = new CollatzExplorer();      f.setContentPane(ce);      f.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);      f.setSize(800, 600);      f.setLocationRelativeTo(null);      f.setVisible(true);   }}`

I never get any phone calls either.
Last edited by RebeccaRGB on Sun Mar 07, 2010 6:10 am UTC, edited 1 time in total.
Stephen Hawking: Great. The entire universe was destroyed.
Fry: Destroyed? Then where are we now?
Al Gore: I don't know. But I can darn well tell you where we're not—the universe!

squareroot
Posts: 548
Joined: Tue Jan 12, 2010 1:04 am UTC
Contact:

### Re: "Collatz Conjecture" Discussion

RebeccaRGB wrote:I finally registered so I could say that I just wasted a couple hours on this:

http://www.kreativekorp.com/epsilon/collatz.jpg

Thanks Randall for taking me down with you.

I always think it's cool, somehow, to look at a document like that and think, "Hey! That's what the inside of you scanner looks like!" And then I feel like a spy...
P.S. I really would like to see this expanded to the dyadic rationals in a way that makes sense... I posted an idea earlier that made some sense, but now I realize there's a very simple function that just turns any non-integer into some integer, after which the normal functions is used. And I personally don't appreciate the whole 2*sin(pi*x)etc.... stuff.
<signature content="" style="tag:html;" overused meta />
Good fucking job Will Yu, you found me - __ -

reffu
Posts: 11
Joined: Thu Feb 25, 2010 5:42 am UTC

### Re: "Collatz Conjecture" Discussion

The easy way to explain this is that multiplying an odd number by 3 and adding one results in an even number. If done enough times the even number will be a power of 2 which when divided by 2 will reduce the power to 0.
Multiply by 3 can be changed to any odd number and would work the same way.
"With great power comes bigger batteries and longer recharge times"

Dropzone
Posts: 405
Joined: Sun Dec 30, 2007 10:12 pm UTC
Location: North Lincs., UK

### Re: "Collatz Conjecture" Discussion

RebeccaRGB wrote:After a few more hours of wasted time, I present Collatz Explorer, a Java Swing app to explore the Collatz graph. It uses BigIntegers so the sky's the limit.

Code: Select all

`cooode`

I never get any phone calls either.

Okay, this is pretty awesome. Here's an appletified version of it for those who don't have a Java compiler handy: http://www.dcs.shef.ac.uk/~aca06mf/collatz/

Krikkit_Robot
Posts: 74
Joined: Mon Aug 17, 2009 3:43 am UTC
Contact:

### Re: "Collatz Conjecture" Discussion

Not sure why I even bothered, but here it is anyway.

It will probably make anyone with any programing experience weep, but it works

Spoiler:

Code: Select all

`def overlord():    count = [0]    steps = [0]    series = []    def promp():        print 'Collatz Conjecture'        A = input ('Please select any positive integer. ')        count[0] = A        ifelse1()    def ifelse1():        G = count[0]        if G > 1:            ifelse()        if G < 1:            print ' '            print 'POSITIVE INTEGERS'            print ' '            promp()        if G == 1:            series.append (1)            F = steps[0]            print ' '            print 'Complete: '            print ' '            print 'Steps: ' + str(F)            print ' '            print 'series'            print series[:]            print ' '            overlord()    def ifelse():        B = count[0]        series.append (B)        if B%2 == 0:            step()                    print ' '            print 'Step'            print steps[:]            print 'Function - Even'            print 'New Value:'            C = B / 2            print C            count[0] = C            ifelse1()        else:            step()            print ' '            print 'Step'            print steps[:]            print 'Function - Odd'            print 'New Value:'            H = B * 3            I = H + 1            print I            count[0] = I            ifelse1()    def step():        D = steps[0]        E = D + 1        steps[0] = E    promp()overlord()`

This is what happens when you only learn programing from and youtube tutorials

boring bore
Posts: 270
Joined: Mon Aug 17, 2009 5:23 am UTC
Location: Don't stalk me, it's not worth it

### Re: "Collatz Conjecture" Discussion

DT_ wrote:
boring bore wrote:I don't think doing (3x+1)/2 infinitely to any natural number will continually result in a natural number. Take any odd number that works for the Collatz conjecture, for example, 11: doing (3x+1)/2 infinitely gives you 11-->17-->26-->14.5, which is not a natural number and will only get worse from there.

11 -> 34 -> 17 -> 52 -> 26 -> 13 -> 40 -> 20 -> 10 -> 5 -> 16 -> 8 -> -> 4 -> 2 -> 1.

The sequence of numbers produced are always natural numbers, because given a natural number n, 3n + 1 is a natural number for all odd n (for all n in general, but in particular for all odd n) and n/2 is a natural number for all even n.

Of course I know what the rules of the conjecture are. I was saying if a number could withstand (3x+1)/2 infinitely (excluding any other rules) without becoming even, then the conjecture would be disproved.

It is not necessary for a number that disproves the Collatz conjecture to follow this; however, a number that does follow it will disprove the conjecture.

Guys you should totally register for this and join the xkcd team! Rath358 started us off and we're kinda small so the more people who join us, the better for our team and, hopefully, for humanity!

Nevvy
Posts: 7
Joined: Fri Mar 05, 2010 8:18 am UTC

### Re: "Collatz Conjecture" Discussion

reffu wrote:The easy way to explain this is that multiplying an odd number by 3 and adding one results in an even number. If done enough times the even number will be a power of 2 which when divided by 2 will reduce the power to 0.
Multiply by 3 can be changed to any odd number and would work the same way.

Great, now prove that every number will eventually reach a power of two.

Is it provable that there can only be the one loop at the bottom?

boring bore
Posts: 270
Joined: Mon Aug 17, 2009 5:23 am UTC
Location: Don't stalk me, it's not worth it

### Re: "Collatz Conjecture" Discussion

Nevvy wrote:Is it provable that there can only be the one loop at the bottom?

...One loop at the bottom? Is this another of those smart things I don't understand? It sounds like you're talking about 1-4-2-1 to me...

Guys you should totally register for this and join the xkcd team! Rath358 started us off and we're kinda small so the more people who join us, the better for our team and, hopefully, for humanity!

Dan04
Posts: 2
Joined: Sun Mar 07, 2010 7:33 am UTC

### Re: "Collatz Conjecture" Discussion

As mentioned previously, it would be sufficient to prove that every number leads to a smaller number. Obviously, this is true for even numbers, so any counterexample would be odd.

Breaking the positive odd numbers down into remainder modulo 16:

• n=16m+1 → 48m+4 → 24m+2 → 12m+1, which is less than n if m≥1 (n≥17)
• n=16m+3 → 48m+10 → 24m+5 → 72m+16 → 36m+8 → 18m+4 → 9m+2, which is always less than n
• n=16m+5 → 48m+16 → 12m+8 → 6m+4 → 3m+2, which is always less than n
• n=16m+7 → 48m+22 → 24m+11 → 72m+34 → 36m+17 → 108m+52 → 54m+26 → 27m+13, which may be even or odd depending on m.
• n=16m+9 → 48m+28 → 24m+14 → 12m+7, which is always less than n
• n=16m+11 → 48m+34 → 24m+17 → 72m+52 → 36m+26 → 18m+13 → 54m+40 → 27m+20, which may be even or odd depending on m.
• n=16m+13 → 48m+40 → 24m+20 → 12m+10 → 6m+5, which is always less than n
• n=16m+15 → 48m+46 → 24m+23 → 72m+70 → 36m+35 → 108m+106 → 54m+53 → 162m+160 → 81m+80, which may be even or odd depending on m.

Therefore, any counterexample n to the Collatz Conjecture must satisfy one of the following:

• n mod 16 = 1 and n < 17 (satisfied only by n=1, which is not a counterexample)
• n mod 16 = 7
• n mod 16 = 11
• n mod 16 = 15

Dan04
Posts: 2
Joined: Sun Mar 07, 2010 7:33 am UTC

### Re: "Collatz Conjecture" Discussion

Breaking it down one step further, n mod 16 ∈ {7, 11, 15} is equivalent to n mod 32 ∈ {7, 11, 15, 23, 27, 31} .

• n = 32m+7 → 96m+22 → 48m+11 → 144m+34 → 72m+17 → 216m+52 → 108m+26 → 54m+13 → 162m+40 → 81m+20, which may be even or odd depending on m.
• n = 32m+11 → 96m+34 → 48m+17 → 144m+52 → 72m+26 → 36m+13 → 108m+40 → 54m+20 → 27m+10, which is always less than n.
• n = 32m+15 → 96m+46 → 48m+23 → 144m+70 → 72m+35 → 216m+106 → 108m+53 → 324m+160 → 162m+80 → 81m+40, which may be even or odd depending on m.
• n = 32m+23 → 96m+70 → 48m+35 → 144m+106 → 72m+53 → 216m+160 → 108m+80 → 54m+40 → 27m+20, which is always less than n.
• n = 32m+27 → 96m+82 → 48m+41 → 144m+124 → 72m+62 → 36m+31 → 108m+94 → 54m+47 → 162m+142 → 81m+71, which may be even or odd depending on m.
• n = 32m+31 → 96m+94 → 48m+47 → 144m+142 → 72m+71 → 216m+214 → 108m+107 → 324m+322 → 162m+161 → 486m+484 → 243m+242, which may be even or odd depending on m.

So the counterexample must have n mod 32 ∈ {7, 15, 27, 31}.

TerrorBite
Posts: 1
Joined: Sun Mar 07, 2010 8:57 am UTC

### Re: "Collatz Conjecture" Discussion

Naturally, I wrote some code to explore this after reading the comic.

My first quick python script just calculated the series from 1 to 100. I made it generate a CSV which I pasted into a spreadsheet to generate an interesting graph of sequence length per input number.

My second piece of code reverse-calculates the Collatz numbers from the root up, up to 20 levels, and graphs the results using twopi from the graphviz suite. I present the results of my effort for your enjoyment:

(Note, this code is intended to run under Linux or a similar system.]

Code: Select all

`#!/usr/bin/env pythonfrom os import execvpfrom sys import argv# This python script generates a graph that shows 20 levels of the Collatz Conjecture.# You will need graphviz installed to run this Python script.# Check argumentsif len(argv) < 2:    print "Usage: %s outputfile.png" % argv[0]    exit(1)filename=argv[1]level = [1] # The root of the tree contains only "1"results = {} # This will hold the relationships for the graph# Loop 20 timesfor c in range(20):    newlevel = set() # This will be the set of numbers in the level above us    for x in level: # We now loop through each number in our current level        # There will only sometimes be an odd multiple of 3 (plus one) above us        # When (x-1) mod 3 is 0, x is an even number half the time        # So we check against (x-4) mod 6 because we don't want to find evens        odd = (x-1)/3 if not (x-4)%6 else 0        if odd > 1: # We don't want 1 (the root) or 0 (no odd found)            newlevel.add(odd) # Put this into the next level            results[odd] = x # Add a relationship to the graph        newlevel.add(x*2); # There will always be an even number above us        results[x*2] = x # Add a relationship to the graph    # Finally, advance to the next level    level = newlevel# Technically, 1 is odd so 1*3+1 = 4. If included though, this tends to make 2 and 1 overlap on the graph, which is ugly.# Uncomment to include this relationship:# results[1] = 4;# Now we write the graph out to a file in dot format so that graphviz can read itf = open('/tmp/collatz.dot', 'w')# For aesthetic reasons we set 8 as the centre node instead of 1f.write('digraph G {\n    size="16,16";\n    root=8;\n    splines=true;\n')for x in results:    f.write("    %d -> %d;\n" % (x, results[x]))f.write('}\n')f.close()print "Generated %d nodes\nBuilding graph..." % len(results)# Finally, execute the graphviz process that generates the PNG fileexecvp('twopi', ('twopi', '/tmp/collatz.dot', '-Tpng:cairo', '-o', filename, '-Nfontsize=18'))# Our story ends here as twopi has replaced the python process`

I've attached the graph generated by this code. It's pretty.
Attachments
Collatz Conjecture diagram

lobedir
Posts: 2
Joined: Tue Dec 08, 2009 10:31 pm UTC

### Re: "Collatz Conjecture" Discussion

Dan04 wrote:As mentioned previously, it would be sufficient to prove that every number leads to a smaller number. Obviously, this is true for even numbers, so any counterexample would be odd.

Breaking the positive odd numbers down into remainder modulo 16:

• n=16m+1 → 48m+4 → 24m+2 → 12m+1, which is less than n if m≥1 (n≥17)
• n=16m+3 → 48m+10 → 24m+5 → 72m+16 → 36m+8 → 18m+4 → 9m+2, which is always less than n
• n=16m+5 → 48m+16 → 12m+8 → 6m+4 → 3m+2, which is always less than n
• n=16m+7 → 48m+22 → 24m+11 → 72m+34 → 36m+17 → 108m+52 → 54m+26 → 27m+13, which may be even or odd depending on m.
• n=16m+9 → 48m+28 → 24m+14 → 12m+7, which is always less than n
• n=16m+11 → 48m+34 → 24m+17 → 72m+52 → 36m+26 → 18m+13 → 54m+40 → 27m+20, which may be even or odd depending on m.
• n=16m+13 → 48m+40 → 24m+20 → 12m+10 → 6m+5, which is always less than n
• n=16m+15 → 48m+46 → 24m+23 → 72m+70 → 36m+35 → 108m+106 → 54m+53 → 162m+160 → 81m+80, which may be even or odd depending on m.

Therefore, any counterexample n to the Collatz Conjecture must satisfy one of the following:

• n mod 16 = 1 and n < 17 (satisfied only by n=1, which is not a counterexample)
• n mod 16 = 7
• n mod 16 = 11
• n mod 16 = 15

Nice! (just noticed the WP article has an 'optimization' section, that also mentions the mod method).

But, allow me to point this out: it appears that dividing your potentially infinite search space by factor n (whatever that n might be, given more and better optimizations) still requires exactly the same leap of faith: that a counterexample /can/ be found in a reasonable amount of time. Let me explain what I mean (an informal argument, not a proof): The reductions seem to be that of some factor k. Assume there is no counter-example. Then we're screwed anyway, the search won't halt, and we'll never know why. Assume there is a counter-example. We'll find it after n steps. This n might be very large. Think 'age of universe' long. Then reduction by factor k (as long as k is below ~13 billion) just doesn't really cut it. Assume n is relatively low. Then it's certainly nice to know that we reach the proof (by counterexample) a bit faster (say, in 100 years rather than 1000), but it doesn't really change the game. Both durations (100 or 1000) are what I would call 'within reasonable time'.

Hm, not sure if I made my point really that clear... I guess what I'm saying is, those optimizations certainly make sense if you want to win some academic competition how many steps you have processed so far. But I don't see how it fundamentally changes the prospect of finding an experimental solution.

Labot2001
Posts: 15
Joined: Fri Nov 14, 2008 2:24 am UTC
Location: The Internet
Contact:

### Re: "Collatz Conjecture" Discussion

I also wrote up a bit of code in Java for the conjecture.

Spoiler:

Code: Select all

`/* ==================== Collatz Conjecture ==================== * Mark Hood 2010 * Creative Commons Attribution Only * ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ * This program does what it says. The user is prompted for a * positive integer n and an amount of iterations z. The inte- * ger n is then tested through the Collatz Conjecture, repeat- * ing trials until either n equals 1 or the amount of trials * run equals z. After exiting the loop, a print statement * declares n's final value and the amount of iterations * the program ran. * ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ * This program is dedicated to my girlfriend Gina for putting * up with my uber-geeky, sudden urge to write this program * after seeing xkcd comic #710; and to my friend Georgiy for * dealing with my persistent WHAT IS HAPPENING cries for help, * most of which more often then not resulted in him pointing * out that I was missing a semicolon :) */import java.util.Scanner;public class Collatz{   public static void main(String [] args){      int n = 0;  //number the program submits to the Collatz Conjecture      int z = 0;  //number of iterations until loop exits      int counter = 0;  //counts actual iterations      Scanner input = new Scanner(System.in);      boolean npositive = false; //if n is greater than 1, this is true      boolean zpositive = false; //if z is greater than 0, this is true            while(npositive == false){          System.out.println("Starting integer:");  //prompts user for a value for n         n = input.nextInt();         if(n > 1){ //changes npositive to true if n is greater than 1            npositive = true;         }else{            System.out.println("Please input a whole number value greater than 1.");  //error message         }      }            while(zpositive == false){            System.out.println("How many interations should the program run before timing out?");  //prompts user for an iterations cap            z = input.nextInt();            if(z > 0){  //changes zpositive to true if n is greater than 0               zpositive = true;            }else{               System.out.println("Please input a positive integer.");  //error message            }         }                while(z > 0){  //loop runs so long as the iterations cap hasn't reached 0                if(n == 1){                   break; //loop ends if n is 1                }else if(n%2 == 1){  //if n is odd, then let n = 3n+1                   n = 3*n+1;                   counter = counter+1;  //counter goes up by 1                }else if (n%2 == 0){  //if n is even, then let n = n/2                   n = n/2;                   counter = counter+1;  //counter goes up by 1                }z = z-1;  //subtracts 1 from z for each iteration ran             }          System.out.println("The final outcome is " + n + ", after running for " + counter + " iterations.");      }}`

For those of you who want to try it out, you can set a cap on the amount of iterations it runs so that it doesn't run 1189339480718728 times and crash your computer.

greenknight04
Posts: 1
Joined: Sun Mar 07, 2010 4:46 pm UTC

### Re: "Collatz Conjecture" Discussion

Was inspired to write out a collatz method in ruby by this comic. Enjoy:

Code: Select all

`def collatz (n)   print n.to_s + "\n"   if n == 1      return   elsif n % 2 == 0 #if even      collatz(n/2)   elsif n % 2 == 1 #if odd      collatz((3*n)+1)   else      return   endendc = gets.strip.to_iif c < 0   print "cannot use a negative number!\n"   exitelse   collatz c   print "Done.\n"end`

FunPika
Posts: 3
Joined: Sun Mar 07, 2010 3:14 pm UTC

### Re: "Collatz Conjecture" Discussion

Out of boredom...I wrote code in Microsoft Small Basic for the conjecture.

Also have it running here (need Silverlight).

Code: Select all

`TextWindow.WriteLine( "Collatz Conjecture" )TextWindow.WriteLine( "Any number you enter must be greater than 1. Decimal numbers will be rounded to the nearest integer. ")Sub enternum  TextWindow.Write("Please enter a number: ")  n = TextWindow.ReadNumber()  n = Math.Round( n ) ' Round a decimal number to the nearest whole number.   If n <= 1 Then ' If the number is less than or equal to 1 do not continue.     TextWindow.WriteLine("The number must be greater than 1")    enternum()  EndIfEndSubWhile 1 = 1 ' Infinite Loop  enternum()  TextWindow.WriteLine( "Starting with the number " + n )  steps = 0  While n > 1 ' End loop if n reaches 1.     r = Math.Remainder(n, 2) ' Check if number is even or odd.     If (r = 0) Then      ' Number is even. Divide it by 2.       n = n / 2     Else      ' Number is odd. Multiply it by 3 and then add 1.       n = 3 * n + 1    EndIf    TextWindow.WriteLine( n )    steps = steps + 1 ' Update steps counter.   EndWhile  TextWindow.WriteLine( "The program has reached a solution of 1." )  TextWindow.WriteLine( "This took " + steps + " steps." ) ' Show how many steps it took. EndWhile`

sharky3112
Posts: 2
Joined: Sun Mar 07, 2010 5:00 pm UTC
Location: Germany

### Re: "Collatz Conjecture" Discussion

hi!
great comic, like most of yours!
i've never heard about the collatz-probleme before reading the comic, but i had to wikipedia it. after writing a little java-program and testing every number up to 2147483647 (java-int-maximum) i'm still fascinated.
Keep at it!
sharky3112

leifbk
Posts: 33
Joined: Wed Nov 26, 2008 7:24 am UTC
Location: Bærum, Norway
Contact:

### Re: "Collatz Conjecture" Discussion

sharky3112 wrote:hi!
great comic, like most of yours!
i've never heard about the collatz-probleme before reading the comic, but i had to wikipedia it. after writing a little java-program and testing every number up to 2147483647 (java-int-maximum) i'm still fascinated.
Keep at it!
sharky3112

If you wrote a Java program and tested more than two billion values in it in about 60 hours, I'm very, very impressed.

squareroot
Posts: 548
Joined: Tue Jan 12, 2010 1:04 am UTC
Contact:

### Re: "Collatz Conjecture" Discussion

leifbk wrote:
sharky3112 wrote:hi!
great comic, like most of yours!
i've never heard about the collatz-probleme before reading the comic, but i had to wikipedia it. after writing a little java-program and testing every number up to 2147483647 (java-int-maximum) i'm still fascinated.
Keep at it!
sharky3112

If you wrote a Java program and tested more than two billion values in it in about 60 hours, I'm very, very impressed.

But if you do it the "smart" way - that is, keeping a table of all the values you've confirmed to go to zero and stopping as soon as you reach one of those - it's not so impressive computationally. But for that matter, it is more impressive programmatically.
<signature content="" style="tag:html;" overused meta />
Good fucking job Will Yu, you found me - __ -

Gldm
Posts: 5
Joined: Tue Mar 04, 2008 10:11 am UTC

### Re: "Collatz Conjecture" Discussion

Wait, this isn't proven? I thought it was one of those "well it's easy once you know how to look at it" type problems. The longest chains are always numbers that are (2^n)-1, and the shortest are ones with repeating alternate 1s and 0s. Thought this was because it's a binary string sorter.

Try doing it on paper in binary, you'll see what I mean. Dividing by 2 is just a simple right shift, and 3x+1 is take the original number, left shift, add, add 1. Every number goes through a sequence where zeros "bubble" through the string, and eventually you get a repeating pattern of alternating 1s and 0s of a given length. The 3x of that forms a solid string of 1s, and the +1 then makes it a leading 1 with all 0s, which then right shifts out (it's a power of 2).

So for any arbitrary binary number, the process involves continually shifting left or right and adding itself or 1. The +1 makes a cascade ripple carry leftwards converting 1s to 0s until it reaches the first 0, which becomes a 1, then the 0s are shifted out. So the rightmost zero has effectively "bubbled" out the end. The point is 1s are added on the 3x+1 pass and 0s are eliminated in the /2 pass. So eventually any string will reduce to the number 1 because the zeros bubble out. The reason it works is because the *saturation* or percentage of digits that repeat decreases.

E.g. longest (number of steps) case for 4 digits (15 or 1111):
1111
11110 add 2x (30) to get 3x
101101 (45) add 1 to get 3x+1
101110 (46) divide by 2 to get 23
10111 (23) which is non-saturated, because even though we're larger than 15 there are still only 4 1s and we've added a 0, reducing saturation.
101110 add 2x (46) to get 3x
1000101 (69) add 1 to get 3x+1
1000110 (70) divide by 2 to get 35
100011 (35) and now even though we're larger than 15 we've dumped a 1, but it'll be back due to the 3 0s, which "hide" it. Remember repeats are bad.
1000110 x2 (70) and add to get 3x
1101001 (105) add 1 to get 3x+1
1101010 (106) divide by 2
110101 (53) now we have 6 digits but still only 4 ones and longest repeat count is 2 so saturation is still lower than 35, 23, or 15.
1101010 x2 (106) add to get 3x
10011111 (159) now +1 for 3x+1
10100000 (160) and lots of divisions (remove 5 0s)
101 (5) and then there were 2 1s left!
1010 (10) x2 and add for 3x
1111 (15) +1 for 3x+1
10000 (16) divide to get rid of 0s
1 (1) done!

The numbers seem semi-random in terms of their value, but if you instead look at it like a machine that operates on the binary strings of numbers and is designed to "reduce repeat runs" it makes more sense. Bubbles of zeros appear during the process that make the actual value grow, but the number of consecutive digits of the same value doesn't. The really easy to reduce cases are the alternating pattern ones, because they go in 2 steps. So I guess it's really about reducing continual runs of the same digit to that alternating pattern, since both long strings of 1s and long strings of 0s (with at least one 1 to the right) seem to have a similar effect of being more work to reduce.

Posts: 1
Joined: Sun Mar 07, 2010 8:48 pm UTC

### Re: "Collatz Conjecture" Discussion

I don't really get why, but for whatever reason when I tried some people's Python codings for some very large numbers (1e40ish) it took like 5 minutes to calculate whereas on my Ti-nspire it took about 5 seconds. In fact, my nspire can do 1e999 in less then half a minute . Is it just because I running windows, or because Graphing calculators are designed exclusively for floating point operations?

bmonk
Posts: 662
Joined: Thu Feb 18, 2010 10:14 pm UTC
Location: Schitzoed in the OTT between the 2100s and the late 900s. Hoping for singularity.

### Re: "Collatz Conjecture" Discussion

boring bore wrote:It's always interesting to me how, when mathematics has advanced so unbelievably far, a problem an elementary schooler (or maybe a middle schooler, depending on their education) could easily grasp is able to be a puzzle for the world's greatest mathematicians. So, as far as I can tell, we're basically trying to find whether there exists an odd number that can be put through (3x+1)/2, or 1.5x+.5, infinitely without becoming a non-natural number. Had I only just seen the problem and committed no thought or research to it, my first thought would be that a mathematician would have no trouble with this; it seems that isn't so!

The other side of this truth is that no area of Mathematics is necessarily finished--not like, say, the mechanics of a billiards table is (essentially) finished. There is always the chance that a new way of looking at something simple leads to a new problem, and perhaps a whole new set of problems or a new theory to develop.

It means that even duffers and amateurs have a chance.

Czhorat wrote:
eviloatmeal wrote:Ok, so is there a simple explanation why odds need to be multiplied by 3? It seems to work by just adding one, and logically, it should, no?

I think this is the core of the joke: that the "Collatz Conjecture" is based on a completely arbitrary set of rules. Depending on how cynical you are, it can be about the lonliness of pure mathematics as opposed to something with a practical application or the impracticality of the same.

In either words, one could argue that one is wasting ones time trying to prove something completely arbitrary and if no consequence to anyone OR that one is learning something about pure math about which, sadly, the average person won't care. [emphasis added]

Either way it earned me a chuckle and even taught me a little something. Not a bad comic.

That's one interpretation of the role of mathematicians: they keep trying to come up with more and more esoteric and useless systems--and someone else will come along, some scientist or engineer, and figure out some way to apply it to the world. Which just spurs the mathematicians to try harder.
Having become a Wizard on n.p. 2183, the Yellow Piggy retroactively appointed his honorable self a Temporal Wizardly Piggy on n.p.1488, not to be effective until n.p. 2183, thereby avoiding a partial temporal paradox. Since he couldn't afford two philosophical PhDs to rule on the title.

squareroot
Posts: 548
Joined: Tue Jan 12, 2010 1:04 am UTC
Contact:

### Re: "Collatz Conjecture" Discussion

Gldm wrote:Wait, this isn't proven? I thought it was one of those "well it's easy once you know how to look at it" type problems. The longest chains are always numbers that are (2^n)-1, and the shortest are ones with repeating alternate 1s and 0s. Thought this was because it's a binary string sorter.

But that's not true. 27 has more steps than 31. 27 has 4 ones, while 31 has 5. In fact, the path of 27 passes through 31. Nice idea, though..
<signature content="" style="tag:html;" overused meta />
Good fucking job Will Yu, you found me - __ -

Korbl
Posts: 35
Joined: Tue Feb 10, 2009 1:41 am UTC

### Re: "Collatz Conjecture" Discussion

Apteryx wrote:How long before someone critics it on its humour?.

This theory would be of interest to solipsists, and they wouldn't care if no-one rang* them.

*It just occurred to me that Americans say "call", we say "ring". Ours isn't confusing, "Ring your sister will you" means use a phone.
"Call your sister will you", could mean phone, or step outside and yell.

yes, but you silly brits also say "knock up" to mean to go to someone's place and wake them up by knocking.
Silly brits. I love England.

Ribenalion
Posts: 2
Joined: Sat Aug 09, 2008 2:04 pm UTC
Location: England

### Re: "Collatz Conjecture" Discussion

Is the arrow between 7 and 22 wrong? Pretty sure it should be to the 21 below it

Edit: Spotted the +1 now. Completely makes sense now. I think I need to learn to read guys...
Last edited by Ribenalion on Mon Mar 08, 2010 6:01 pm UTC, edited 1 time in total.

phlip
Restorer of Worlds
Posts: 7573
Joined: Sat Sep 23, 2006 3:56 am UTC
Location: Australia
Contact:

### Re: "Collatz Conjecture" Discussion

Ribenalion wrote:Is the arrow between 7 and 22 wrong? Pretty sure it should be to the 21 below it

Last time I checked, 3*7+1 == 22. Did they change the rules of arithmetic while I was out getting lunch? 'Cause I hate it when that happens.

Code: Select all

`enum ಠ_ಠ {°□°╰=1, °Д°╰, ಠ益ಠ╰};void ┻━┻︵​╰(ಠ_ಠ ⚠) {exit((int)⚠);}`
[he/him/his]

Robstickle
Posts: 326
Joined: Sat Nov 28, 2009 10:07 am UTC

### Re: "Collatz Conjecture" Discussion

phlip wrote:
Ribenalion wrote:Is the arrow between 7 and 22 wrong? Pretty sure it should be to the 21 below it

Last time I checked, 3*7+1 == 22. Did they change the rules of arithmetic while I was out getting lunch? 'Cause I hate it when that happens.

The axioms we were using were as it turns out wrong. Yes that's right wrong. How can axioms be wrong you ask? They just are. You're going to have to relearn maths I'm afraid.

Eikinkloster
Posts: 211
Joined: Tue Jun 30, 2009 1:07 pm UTC
Location: Brazil

### Re: Collatz Conjecture

syko_lozz wrote:I am not enough of a geek to have heard this one before
but I AM enough of a geek to find it pretty cool

sigh, the lonely, uncool middle again

You are not THAT alone though
Chaos Reigns!