DouKaku? 5127 malark: Max(f(n)) = 524 n =...(コラッツ・角谷の問題)

Comment detail

Max(f(n)) = 524
n =
  837799
Time: 2652[ms]

Athlon64 X2 5000+(2.6GHz) / Windows Vista HP x64 / JRE1.6.0_03

これが限界・・・1秒切りたいなぁ

package challenge120;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Challenge120 {

    private final static int LIM = 1 << 20; // 1<<20 = 2^20

    private final static Map<Long, Integer> CACHE = new HashMap<Long, Integer>();

    public static void main(final String[] args) {

        final long start = System.currentTimeMillis();

        int fnMax = 0;
        final List<Integer> fnMaxN = new ArrayList<Integer>();

        for (int n = 1; n <= LIM; n++) {
            final int fn = f(n);
            if (fn > fnMax) {
                fnMax = fn;
                fnMaxN.clear();
                fnMaxN.add(n);
            } else if (fn == fnMax) {
                fnMaxN.add(n);
            }
        }
        out(fnMax, fnMaxN);
        System.out.println("Time: " + (System.currentTimeMillis() - start)
                + "[ms]");
    }

    private static int f(final int n) {
        int fn = 0;
        for (long nTemp = n; nTemp != 1;) {
            final Integer cached = CACHE.get(nTemp);
            if (cached == null) {
                nTemp = (nTemp % 2 == 0) ? nTemp / 2 : nTemp * 3 + 1;
                fn++;
            } else {
                fn += cached;
                break;
            }
        }
        CACHE.put(Long.valueOf(n), fn);
        return fn;
    }

    private static void out(final int maxN, final List<Integer> fnMaxN) {

        System.out.println("Max(f(n)) = " + maxN);
        System.out.println("n =");
        for (final int n : fnMaxN) {
            System.out.println("  " + n);
        }
    }
}

Listではなく、ただの配列でキャッシュを実装するとかなり高速化できますね。

PentiumM 2GHz/Windows XP (32bit)で125msでした。

C:¥>java Dk120
f(837799)=524 in 125 ms

public class Dk120 {
    static final int maxN = (1 << 20);
    static final int cacheN = maxN;
    
    private static int[] cache = new int[cacheN+1];
    
    private static int colatz(long n) {
        if (n == 1) return 0;
        if (n <= cacheN && cache[(int)n] != 0) return cache[(int)n];
        
        int c = 1 + ((n % 2 == 0) ? colatz(n >> 1) : colatz(n * 3 + 1));
        if (n <= cacheN) cache[(int)n] = c;
        return c;
    }
    
    public static void main(String[] args) {
        int max = 1;
        int maxValue = 0;
        long start = System.currentTimeMillis();
        
        for (int i = 1; i <= maxN; i++) {
            int c = colatz(i);
            if (max < c) { max = c; maxValue = i; }
        }
        System.out.printf("f(%d)=%d in %d ms", maxValue, max, System.currentTimeMillis() - start);
    }    
}

DouKaku?

Comment detail

Index

Feed

Other

Link

Pathtraq