数を題材にした簡単な問題集です。プログラムは拙作のページで作成した immutable な連結リストと遅延ストリームを使っています。もちろん、連結リストや遅延ストリームを使わなくても解くことができるので、興味のある方は挑戦してみてください。
なお、問題の詳しい説明は拙作のページ Puzzle DE Programming の「フィボナッチ数」, 「素数」, 「約数」をお読みくださいませ。
//
// playnum.java : 数で遊ぼう
//
// Copyright (C) 2017-2021 Makoto Hiroi
//
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import immutable.ImList;
import immutable.LazyStream;
import immutable.Pair;
public class playnum {
// Q01
// 素数列
static LazyStream<Long> primes =
LazyStream.cons(2L, () -> LazyStream.cons(3L, () -> LazyStream.cons(5L, () -> primesFrom(7))));
static long nextPrime(long n) {
while (true) {
var ps = primes;
while (true) {
long p = ps.first();
if (p * p > n) return n;
if (n % p == 0) break;
ps = ps.rest();
}
n += n % 6 == 5 ? 2 : 4;
}
}
static LazyStream<Long> primesFrom(long n) {
long p = nextPrime(n);
return LazyStream.cons(p, () -> primesFrom(p % 6 == 5 ? p + 2 : p + 4));
}
// Long バージョンの iota
static ImList<Long> iota(long n, long m) {
ImList<Long> xs = ImList.nil();
while (n <= m) {
xs = ImList.cons(m--, xs);
}
return xs;
}
// 区間ふるい
static ImList<Long> segmentSieve(long n, long m) {
var xs = iota(n, m);
var ps = primes;
while (true) {
long p = ps.first();
if (p * p > m) return xs;
xs = xs.filter(x -> x % p != 0 || x == p);
ps = ps.rest();
}
}
// Q02 メルセンヌ素数
// 累乗
static long power(long x, long n) {
if (n == 0) {
return 1L;
} else if (n == 1) {
return x;
} else {
long z = power(x, n / 2);
if (n % 2 == 1)
return x * z * z;
else
return z * z;
}
}
// 素数のチェック (試し割り)
static boolean isPrime(long n) {
var ps = primes;
while (true) {
long p = ps.first();
if (p * p > n) return true;
if (n % p == 0) return false;
ps = ps.rest();
}
}
static LazyStream<Long> mersenneNumber() {
return LazyStream.iterate(2L, x -> x + 1L)
.map(x -> power(2, x) - 1)
.filter(x -> isPrime(x));
}
// リュカ-レーマー・テスト (Lucas-Lehmer primality test)
static boolean lucasLehmerTest(long p) {
long m = power(2, p) - 1;
long x = 4;
for (long i = 0; i < p - 2; i++)
x = (x * x - 2) % m;
return x % m == 0;
}
static LazyStream<Long> mersenneNumberFast() {
return LazyStream.cons(3L, () -> LazyStream.iterate(2L, x -> x + 1L)
.filter(x -> lucasLehmerTest(x))
.map(x -> power(2, x) - 1));
}
// Q03
// フィボナッチ数列
static LazyStream<Long> makeFibo(long a, long b) {
return LazyStream.cons(a, () -> makeFibo(b, a + b));
}
static long fiboSum(long n) {
var fibo = makeFibo(1, 1);
long a = 0;
for (long x: fibo.takeWhile(x -> x <= n)) a += x;
return a;
}
// Q04
static LazyStream<Long> fiboPrime() {
return makeFibo(2, 3).filter(x -> isPrime(x));
}
// Q05
static Pair<Long, Long> factorSub(long n, long m) {
long c = 0;
while (n % m == 0) {
c++;
n /= m;
}
return Pair.pair(c, n);
}
// 素因数分解 (試し割り)
static List<Pair<Long, Long>> factorization(long n) {
var xs = new ArrayList<Pair<Long, Long>>();
var ps = primes;
while (true) {
long p = ps.first();
if (p * p > n) break;
var y = factorSub(n, p);
if (y.getFst() > 0) {
xs.add(Pair.pair(p, y.getFst()));
n = y.getSnd();
}
ps = ps.rest();
}
if (n > 1) xs.add(Pair.pair(n, 1L));
return xs;
}
// Q06
static long divisorNum(long n) {
return LazyStream.of(factorization(n)).map(x -> x.getSnd()).foldLeft((a, x) -> a * (x + 1), 1L);
}
// Q07
static long sigma(Pair<Long, Long> p) {
return iota(0, p.getSnd()).foldLeft((a, x) -> a + power(p.getFst(), x), 0L);
}
static long divisorSum(long n) {
return LazyStream.of(factorization(n)).map(x -> sigma(x)).foldLeft((a, x) -> a * x, 1L);
}
// Q08
// LazyStream.iota の Long バージョン
static LazyStream<Long> iotaLazy(long n, long m) {
if (n > m)
return LazyStream.nil();
else
return LazyStream.cons(n, () -> iotaLazy(n + 1, m));
}
static LazyStream<Long> factorSub(Pair<Long, Long> p) {
return iotaLazy(0, p.getSnd()).map(x -> power(p.getFst(), x));
}
static LazyStream<Long> product(LazyStream<Long> xs, LazyStream<Long> ys) {
return xs.flatMap(x -> ys.map(y -> x * y));
}
static List<Long> divisor(long n) {
var fs = factorization(n);
var xs = factorSub(fs.get(0));
for (int i = 1; i < fs.size(); i++) {
xs = product(xs, factorSub(fs.get(i)));
}
var ys = xs.take((int)divisorNum(n));
Collections.sort(ys);
return ys;
}
// Q09
static void perfectNumber(long n) {
for (long x = 2; x <= n; x++) {
if (divisorSum(x) - x == x) System.out.println(x);
}
}
// 別解 (メルセンヌ素数を Mn とすると、偶数の完全数は 2n-1 * Mn)
static LazyStream<Long> perfectNumber() {
return LazyStream.iterate(2L, x -> x + 1)
.filter(x -> isPrime(power(2, x) - 1))
.map(x -> power(2, x - 1) * (power(2, x) - 1));
}
// Q10
static LazyStream<Pair<Long, Long>> yuuaiNumber() {
return LazyStream
.iterate(2L, x -> x + 1)
.map(x -> Pair.pair(x, divisorSum(x) - x))
.filter(x -> {
long n = x.getFst();
long m = x.getSnd();
return n < m && divisorSum(m) - m == n;
});
}
public static void main(String[] args) {
System.out.println("----- Q01 -----");
System.out.println(segmentSieve(2, 100));
System.out.println(segmentSieve(100000, 100100));
System.out.println("----- Q02 -----");
System.out.println(mersenneNumber().take(7));
System.out.println(mersenneNumberFast().take(8));
System.out.println("----- Q03 -----");
System.out.println(fiboSum(100000000));
System.out.println(fiboSum(300000000));
System.out.println("----- Q04 -----");
System.out.println(fiboPrime().take(9));
System.out.println("----- Q05 -----");
System.out.println(factorization(24));
System.out.println(factorization(12345678));
System.out.println(factorization(123456789));
System.out.println(factorization(1234567890));
System.out.println(factorization(1111111111));
System.out.println("----- Q06 -----");
System.out.println(divisorNum(24));
System.out.println(divisorNum(12345678));
System.out.println(divisorNum(123456789));
System.out.println(divisorNum(1234567890));
System.out.println(divisorNum(1111111111));
System.out.println("----- Q07 -----");
System.out.println(divisorSum(24));
System.out.println(divisorSum(12345678));
System.out.println(divisorSum(123456789));
System.out.println(divisorSum(1234567890));
System.out.println(divisorSum(1111111111));
System.out.println("----- Q08 -----");
System.out.println(divisor(24));
System.out.println(divisor(12345678));
System.out.println(divisor(123456789));
System.out.println(divisor(1234567890));
System.out.println(divisor(1111111111));
System.out.println("----- Q09 -----");
perfectNumber(10000);
System.out.println(perfectNumber().take(6));
System.out.println("----- Q10 -----");
System.out.println(yuuaiNumber().takeWhile(x -> x.getSnd() < 100000));
}
}
$ javac playnum.java $ java playnum ----- Q01 ----- (2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97) (100003 100019 100043 100049 100057 100069) ----- Q02 ----- [3, 7, 31, 127, 8191, 131071, 524287] [3, 7, 31, 127, 8191, 131071, 524287, 2147483647] ----- Q03 ----- 165580140 701408732 ----- Q04 ----- [2, 3, 5, 13, 89, 233, 1597, 28657, 514229] ----- Q05 ----- [(2, 3), (3, 1)] [(2, 1), (3, 2), (47, 1), (14593, 1)] [(3, 2), (3607, 1), (3803, 1)] [(2, 1), (3, 2), (5, 1), (3607, 1), (3803, 1)] [(11, 1), (41, 1), (271, 1), (9091, 1)] ----- Q06 ----- 8 24 12 48 16 ----- Q07 ----- 60 27319968 178422816 3211610688 1246404096 ----- Q08 ----- [1, 2, 3, 4, 6, 8, 12, 24] [1, 2, 3, 6, 9, 18, 47, 94, 141, 282, 423, 846, 14593, 29186, 43779, 87558, 131337, 262674, 685871, 1371742, 2057613, 4115226, 6172839, 12345678] [1, 3, 9, 3607, 3803, 10821, 11409, 32463, 34227, 13717421, 41152263, 123456789] [1, 2, 3, 5, 6, 9, 10, 15, 18, 30, 45, 90, 3607, 3803, 7214, 7606, 10821, 11409, 18035, 19015, 21642, 22818, 32463, 34227, 36070, 38030, 54105, 57045, 64926, 68454, 108210, 114090, 162315, 171135, 324630, 342270, 13717421, 27434842, 41152263, 68587105, 82304526, 123456789, 137174210, 205761315, 246913578, 411522630, 617283945, 1234567890] [1, 11, 41, 271, 451, 2981, 9091, 11111, 100001, 122221, 372731, 2463661, 4100041, 27100271, 101010101, 1111111111] ----- Q09 ----- 6 28 496 8128 [6, 28, 496, 8128, 33550336, 8589869056] ----- Q10 ----- [(220, 284), (1184, 1210), (2620, 2924), (5020, 5564), (6232, 6368), (10744, 10856), (12285, 14595), (17296, 18416), (63020, 76084), (66928, 66992), (67095, 71145), (69615, 87633), (79750, 88730)]