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

Postby Prior Semblance » Sat Mar 06, 2010 5:08 am UTC

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

Postby squareroot » Sat Mar 06, 2010 5:26 am UTC

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

Postby Chrisfs » Sat Mar 06, 2010 6:11 am UTC

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.

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

Re: "Collatz Conjecture" Discussion

Postby -.Mateo.- » Sat Mar 06, 2010 6:49 am UTC

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.

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

Re: "Collatz Conjecture" Discussion

Postby RebeccaRGB » Sat Mar 06, 2010 7:38 am UTC

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!

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

Re: "Collatz Conjecture" Discussion

Postby SEE » Sat Mar 06, 2010 9:46 am UTC

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

Postby aido179 » Sat Mar 06, 2010 11:55 am UTC

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

Postby marketdoctor » Sat Mar 06, 2010 3:16 pm UTC

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.)

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

Re: "Collatz Conjecture" Discussion

Postby TimeSpaceMage » Sat Mar 06, 2010 3:43 pm UTC

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

Postby tictactictac » Sat Mar 06, 2010 7:16 pm UTC

i tried it out with 95, took almost an eternity :P

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

Re: "Collatz Conjecture" Discussion

Postby Okapi » Sat Mar 06, 2010 8:41 pm UTC

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

Postby Background_Noise » Sat Mar 06, 2010 9:33 pm UTC

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

Postby leifbk » Sat Mar 06, 2010 9:54 pm UTC

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 dollardollar
DECLARE
    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;
END
dollardollar LANGUAGE PLPGSQL IMMUTABLE;


CREATE OR REPLACE FUNCTION gen_collatz(BIGINT, BIGINT) RETURNS VOID AS dollardollar
-- Proc to generate Collatz sequences
DECLARE
    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;
END
dollardollar 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 :(

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

Re: "Collatz Conjecture" Discussion

Postby RebeccaRGB » Sun Mar 07, 2010 12:35 am UTC

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. :D
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

Postby squareroot » Sun Mar 07, 2010 2:22 am UTC

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... :twisted:
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

Postby reffu » Sun Mar 07, 2010 3:01 am UTC

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"

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

Re: "Collatz Conjecture" Discussion

Postby Dropzone » Sun Mar 07, 2010 3:20 am UTC

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. :D

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/

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

Re: "Collatz Conjecture" Discussion

Postby Krikkit_Robot » Sun Mar 07, 2010 5:26 am UTC

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
Image

User avatar
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

Postby boring bore » Sun Mar 07, 2010 7:10 am UTC

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.
Image
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

Postby Nevvy » Sun Mar 07, 2010 7:17 am UTC

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?

User avatar
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

Postby boring bore » Sun Mar 07, 2010 7:20 am UTC

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...
Image
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

Postby Dan04 » Sun Mar 07, 2010 8:27 am UTC

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

Postby Dan04 » Sun Mar 07, 2010 8:50 am UTC

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

Postby TerrorBite » Sun Mar 07, 2010 10:25 am UTC

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 python
from os import execvp
from 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 arguments
if 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 times
for 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 it
f = open('/tmp/collatz.dot', 'w')
# For aesthetic reasons we set 8 as the centre node instead of 1
f.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 file
execvp('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. :D
Attachments
frob.png
Collatz Conjecture diagram

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

Re: "Collatz Conjecture" Discussion

Postby lobedir » Sun Mar 07, 2010 10:46 am UTC

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.

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

Re: "Collatz Conjecture" Discussion

Postby Labot2001 » Sun Mar 07, 2010 3:01 pm UTC

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

Postby greenknight04 » Sun Mar 07, 2010 4:48 pm UTC

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
   end
end

c = gets.strip.to_i
if c < 0
   print "cannot use a negative number!\n"
   exit
else
   collatz c
   print "Done.\n"
end

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

Re: "Collatz Conjecture" Discussion

Postby FunPika » Sun Mar 07, 2010 4:57 pm UTC

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

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()
  EndIf
EndSub
While 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

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

Re: "Collatz Conjecture" Discussion

Postby sharky3112 » Sun Mar 07, 2010 5:13 pm UTC

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

Postby leifbk » Sun Mar 07, 2010 6:19 pm UTC

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. :roll:

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

Re: "Collatz Conjecture" Discussion

Postby squareroot » Sun Mar 07, 2010 6:55 pm UTC

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. :roll:

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

Postby Gldm » Sun Mar 07, 2010 8:52 pm UTC

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.

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

Re: "Collatz Conjecture" Discussion

Postby ShadowAurora » Sun Mar 07, 2010 8:58 pm UTC

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 :shock: . Is it just because I running windows, or because Graphing calculators are designed exclusively for floating point operations?

User avatar
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

Postby bmonk » Sun Mar 07, 2010 9:17 pm UTC

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

Postby squareroot » Sun Mar 07, 2010 10:29 pm UTC

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

Postby Korbl » Sun Mar 07, 2010 11:24 pm UTC

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

:wink:

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

Postby Ribenalion » Mon Mar 08, 2010 12:43 am UTC

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

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.

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

Re: "Collatz Conjecture" Discussion

Postby phlip » Mon Mar 08, 2010 1:33 am UTC

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

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

Postby Robstickle » Mon Mar 08, 2010 3:38 am UTC

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

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.

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

Re: Collatz Conjecture

Postby Eikinkloster » Mon Mar 08, 2010 4:24 am UTC

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!


Return to “Individual XKCD Comic Threads”

Who is online

Users browsing this forum: Pfhorrest and 115 guests