コラッツ予想

Math

というのは、別名「角谷予想」あるいは「3x+1問題」とも呼ばれ、以下のような命題の真偽値を問う問題のことを指す。

任意の0でない自然数nをとり、

  • nが偶数の場合、nを2で割る
  • nが奇数の場合、nに3をかけて1を足す

という操作を繰り返すと、有限回で1に到達する

（詳しくはWikipedia:コラッツの問題等を参照のこと）

この問題は、その見た目の易しさに反して現在も未解決になっているらしい。実は昔（小学生ぐらいの頃）、そんなことも知らずにこの問題を考えたことがあって、その時は（当たり前だけど）答えが出なかった覚えがある。最近このことを思い出してまた考えているうちに、面白い（かもしれない）発見があった。
自然数nを2進数で表すと、nを2で割るという操作は右に１ビットシフトすることに相当する。同様に、3をかけて1を足すという操作は、nとnを左に１ビットシフトした数と1を足すことに相当する。ここで見方を変えれば、これらの操作によってビットパターンの時間的な変化が生じていて、その意味では、ある種のセル・オートマトン（いわゆるライフゲーム）として捉えることもできるだろう。というわけで、そんなプログラムを作ってみた。

http://knzm.dip.jp:8080/CollatzApplet.html

（はてなダイアリーはJavaアプレットを直接ページに貼り付けられないのでこれはただの画像。リンクを辿ると外部ページでJavaアプレットが実行される）

無限の桁数を仮定して、１が立っているビットのうち最上位ビットと最下位ビットの間の長さを定義長とすると、元の問題は上の２種類のビット演算を繰り返すと定義長は１に収束する、ということと等価であることがわかる。超限帰納法を前提にすれば、定義長は元の数より短くなることを証明してもいい。とは言っても、この証明もやっぱり難しくてできないわけだが（問題の難しさが変わったわけではない）。一方で、ある数nからどのようにして1に向かうかということの直感的な表示の仕方としてはアリだと思う。

＜追記＞ひょっとしてここで考えたセル・オートマトンが仮にチューリング完全になることを示せれば、コラッツ問題をチューリングマシンの停止問題に帰着できるかも？ （ただの思いつきなので、全くナンセンスなことを言ってるような気もするけど）＜／追記＞
＜追記２＞と思ったけど、繰り上がりを考えると１時刻後の状態は近傍のセルの状態だけでは決まらないので、厳密にはセル・オートマトンにはならない気がしてきた＜／追記２＞

純粋に技術的な興味としては、ちょうど『Java並行処理プログラミング』(ISBN:4797337206)を読んでいて、Javaのマルチスレッドを真面目に考慮したプログラムが書いてみたかったというのがある。あと、Javaアプレットなんてここ数年書いてなかったので、久しぶりに書いてみたら楽しいだろうというのもあった。ちなみにソースは以下の通り。

  • CollatzApplet.java
import java.awt.BorderLayout;
import java.awt.Container;
import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;
import java.awt.event.MouseWheelEvent;
import java.awt.event.MouseWheelListener;
import java.math.BigInteger;
import javax.swing.BoxLayout;
import javax.swing.JApplet;
import javax.swing.JButton;
import javax.swing.JPanel;
import javax.swing.JSpinner;
import javax.swing.SpinnerNumberModel;
import javax.swing.SwingUtilities;
import javax.swing.event.ChangeEvent;
import javax.swing.event.ChangeListener;

public class CollatzApplet extends JApplet implements Runnable, ActionListener, ChangeListener, MouseWheelListener {
    public static final int SPEED_MIN = -3;
    public static final int SPEED_MAX = 3;
    public static final int NORMAL_WAIT = 500;

    private JButton btnPlay;
    private JButton btnStop;
    private JButton btnFast;
    private JButton btnSlow;
    private JSpinner spnValue;
    private SpinnerNumberModel spnValueModel;
    private CollatzCanvas canvas;
    private PeriodicUpdater updater;

    private int speed;

    public CollatzApplet() {
        btnPlay = new JButton("Play >");
        btnStop = new JButton("Stop");
        btnFast = new JButton("Fast >>");
        btnSlow = new JButton("<< Slow");
        canvas = new CollatzCanvas();

        updater = new PeriodicUpdater(this, NORMAL_WAIT);

        spnValueModel = new SpinnerNumberModel();
        spnValueModel.setMinimum(1);
        spnValue = new JSpinner(spnValueModel);
        JSpinner.NumberEditor editor = new JSpinner.NumberEditor(spnValue);
        editor.getTextField().setEditable(true);
        spnValue.setEditor(editor);

        spnValue.addMouseWheelListener(this);
        spnValueModel.addChangeListener(this);

        JPanel pnlControl = new JPanel();
        pnlControl.add(btnSlow);
        pnlControl.add(btnPlay);
        pnlControl.add(btnStop);
        pnlControl.add(btnFast);

        btnPlay.addActionListener(this);
        btnStop.addActionListener(this);
        btnFast.addActionListener(this);
        btnSlow.addActionListener(this);

        JPanel pnlValue = new JPanel();
        pnlValue.setLayout(new BoxLayout(pnlValue, BoxLayout.X_AXIS));
        pnlValue.add(spnValue);

        Container container = getContentPane();
        container.setLayout(new BorderLayout());
        container.add(pnlValue, BorderLayout.NORTH);
        container.add(canvas, BorderLayout.CENTER);
        container.add(pnlControl, BorderLayout.SOUTH);
    }

    public void init() {
        String value = getParameter("value");
        if (value == null) {
            spnValueModel.setValue(1);
        } else {
            spnValueModel.setValue(new BigInteger(value));
        }
        updateButtonState();
    }

    public void updateButtonState() {
        if (updater.isPlaying()) {
            btnPlay.setEnabled(false);
            btnStop.setEnabled(true);
            btnFast.setEnabled(speed < SPEED_MAX);
            btnSlow.setEnabled(speed > SPEED_MIN);
            spnValue.setEnabled(false);
        } else {
            btnPlay.setEnabled(true);
            btnStop.setEnabled(false);
            btnFast.setEnabled(false);
            btnSlow.setEnabled(false);
            spnValue.setEnabled(true);
        }
    }

    public void updateWait() {
        double msec = NORMAL_WAIT * Math.exp(-speed * Math.log(2));
        long wait = Math.round(msec);
        updater.setPeriod(wait);
    }

    // Runnable
    public void run() {
        BigInteger value = canvas.getValue();
        if (value.testBit(0)) {
            value = value.multiply(BigInteger.valueOf(3)).add(BigInteger.ONE);
        } else {
            value = value.shiftRight(1);
        }

        canvas.setValue(value);
        canvas.repaint();
    }

    // ActionListener
    public void actionPerformed(ActionEvent ev) {
        Object src = ev.getSource();
        if (src == btnPlay) {
            updater.setPlaying(true);
            updateButtonState();
        } else if (src == btnStop) {
            updater.setPlaying(false);
            spnValueModel.setValue(canvas.getValue());
            updateButtonState();
        } else if (src == btnFast) {
            if (speed < SPEED_MAX) {
                speed++;
                updateWait();
                updateButtonState();
            }
        } else if (src == btnSlow) {
            if (speed > SPEED_MIN) {
                speed--;
                updateWait();
                updateButtonState();
            }
        }
    }

    // ChangeListener
    public void stateChanged(ChangeEvent ev) {
        canvas.setValue(spnValueModel.getNumber().longValue());
    }

    // MouseWheelListener
    public void mouseWheelMoved(MouseWheelEvent e) {
        int delta = - e.getWheelRotation() * spnValueModel.getStepSize().intValue();
        int oldValue = spnValueModel.getNumber().intValue();
        Integer newValue = new Integer(oldValue + delta);
        Comparable min = spnValueModel.getMinimum();
        Comparable max = spnValueModel.getMaximum();
        if (((min == null) || (newValue.compareTo((Integer) min) >= 0)) &&
            ((max == null) || (newValue.compareTo((Integer) max) <= 0))) {
            spnValue.setValue(newValue);
        }
    }
}

class PeriodicUpdater implements Runnable {
    private Thread thread;
    private Runnable proc;
    private volatile long period = 0;
    private volatile boolean playing = false;

    public synchronized long getPeriod() { return period; }

    public synchronized void setPeriod(long period) {
        this.period = period;
        if (thread != null)
            thread.interrupt();
    }

    public synchronized boolean isPlaying() { return playing; }

    public synchronized void setPlaying(boolean value) {
        playing = value;
        if (playing && (thread == null)) {
            thread = new Thread(this);
            thread.start();
        } else if ((! playing) && (thread != null)) {
            try {
                thread.interrupt();
                thread.join();
            } catch (InterruptedException ex) {
            }
            thread = null;
        }
    }

    public PeriodicUpdater(Runnable proc, long period) {
        this.proc = proc;
        this.period = period;
    }

    public PeriodicUpdater(Runnable proc) {
        this(proc, 0);
    }

    public void run() {
        while (playing) {
            try {
                if (period > 0)
                    Thread.sleep(period);
                SwingUtilities.invokeLater(proc);
            } catch (InterruptedException ex) {
            }
        }
    }
}
  • CollatzCanvas.java
import java.awt.AWTEvent;
import java.awt.Color;
import java.awt.Dimension;
import java.awt.Graphics;
import java.awt.Image;
import java.awt.event.ComponentEvent;
import java.math.BigInteger;
import javax.swing.JComponent;

public class CollatzCanvas extends JComponent {
    public final int MIN_BITS = 4;

    private Image imgBuffer;
    private BigInteger value;
    private int bitlen = MIN_BITS;

    public BigInteger getValue() { return value; }

    public void setValue(BigInteger value) {
        if (value.signum() <= 0)
            throw new ArithmeticException("Must be positive!");

        this.value = value;
        int len = value.bitLength();

        while (bitlen < len) {
            bitlen *= 2;
        }
        while ((bitlen / 4 > len) && (bitlen / 2 > MIN_BITS)) {
            bitlen /= 2;
        }

        repaint();
    }

    public void setValue(long value) {
        setValue(BigInteger.valueOf(value));
    }

    public CollatzCanvas() {
        enableEvents(AWTEvent.COMPONENT_EVENT_MASK);
        value = BigInteger.ONE;
    }

    public void processComponentEvent(ComponentEvent ev) {
        super.processComponentEvent(ev);

        if (ev.getID() == ComponentEvent.COMPONENT_RESIZED) {
            imgBuffer = null;
        }
    }

    public void paint(Graphics g) {
        Dimension dim = getSize();

        if (imgBuffer == null) {
            imgBuffer = createImage(dim.width , dim.height);
        }

        Graphics gbuf = imgBuffer.getGraphics();
        gbuf.setColor(Color.white);
        gbuf.fillRect(0 , 0 , dim.width , dim.height);

        int circle_radius = (int) Math.round(dim.width / bitlen * 0.4);
        gbuf.setColor(Color.red);
        for (int i = 0; i < bitlen; i++) {
            double x = dim.width * (1- (i + 0.5) / bitlen);
            double y = dim.height / 2;
            if (value.testBit(i)) {
                gbuf.fillOval((int) x - circle_radius , (int) y - circle_radius , circle_radius * 2 , circle_radius * 2);
            } else {
                gbuf.drawOval((int) x - circle_radius , (int) y - circle_radius , circle_radius * 2 , circle_radius * 2);
            }
        }

        gbuf.setColor(Color.black);
        gbuf.drawString("val = " + value, 20, 20);

        g.drawImage(imgBuffer , 0 , 0 ,this);
    }
}