Meertens数
Posted feedbacks - Java
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 掛かりそうです。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 | 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));
}
}
}
|
nobsun
#4710()
Rating4/4=1.00
お題#100「正整数のゲーデル数化？」で定義した goedel を適用すると自分自身になるような数，すなわち goedel (n) == n となるような正整数 n を見つける関数を定義してください．
このような数のことをMeertens数と言うそうです．
32bitsの符号なし整数(あるいは10進10桁整数)までの範囲で探すのにどのくらい計算時間がかかったかをCPUのスペックとともに教えてください．また，その実装で64bit符号なし整数(あるいは10進20桁整数)までの範囲で探すのにどのくらい計算時間がかかりそうか見積ってください(もちろん実際に計算して計算時間を示していただくのでもかまいません)．
1 reply [ reply ]