DouKaku? 5238 squld: Javaにはunsigned型が無いため...(Meertens数)

Comment detail

Javaにはunsigned型が無いため、BigIntegerを使いました。

PentiumM 2.1GHzのパソコンで16桁まで計算させたところ

1桁 10ms
2桁 0ms
3桁 0ms
4桁 0ms
5桁 20ms
6桁 411ms
7桁 10ms
Found Meertens 81312000
8桁 721ms
9桁 100ms
10桁 291ms
11桁 931ms
12桁 3074ms
13桁 9153ms
14桁 26809ms
15桁 76971ms
16桁 219435ms

となりました。
1桁増えるごとに3倍の時間が掛かるようです。
従って、20桁では
219435ms×3^(20-16)=17774235ms≒7.5H
掛かりそうです。

import java.math.BigInteger;

public class Meertens {
    private static final BigInteger PRIMES[] = { new BigInteger("2"), new BigInteger("3"), new BigInteger("5"), new BigInteger("7"), new BigInteger("11"), new BigInteger("13"), new BigInteger("17"), new BigInteger("19"), new BigInteger("23"), new BigInteger("29"), new BigInteger("31"), new BigInteger("37"), new BigInteger("41"), new BigInteger("43"), new BigInteger("47"), new BigInteger("53"), new BigInteger("59"), new BigInteger("61"), new BigInteger("67"), new BigInteger("71") };

    private static void searchMeertens(int aKeta, int aDepth, BigInteger aR, BigInteger aN, BigInteger aNMax) {
        aKeta--;
        aN = aN.multiply(BigInteger.TEN);
        for (int i = aDepth == 0 ? 1 : 0; i < 10; i++) {
            if (i != 0) {
                aR = aR.multiply(PRIMES[aDepth]);
                if (aR.compareTo(aNMax) > 0) {
                    return;
                }
                aN = aN.add(BigInteger.ONE);
            }
            if (aKeta >= 0) {
                searchMeertens(aKeta, aDepth + 1, aR, aN, aNMax);
            } else {
                if (aR.compareTo(aN) > 0) {
                    return;
                }
                if (aR.equals(aN)) {
                    System.out.println("Found Meertens " + aN);
                }
            }
        }
    }

    public static void main(String[] args) {
        BigInteger tNMax = BigInteger.TEN;
        for (int i = 0; i < 16; i++) {
            tNMax = tNMax.multiply(BigInteger.TEN);
            long tStart = System.currentTimeMillis();
            searchMeertens(i, 0, BigInteger.ONE, BigInteger.ZERO, tNMax);
            System.out.printf("%d桁 %dms\n", i + 1, (System.currentTimeMillis() - tStart));
        }
    }
}

DouKaku?

Comment detail

Index

Feed

Other

Link

Pathtraq