こんにちは。「Javaを復習する初心者」です。
Project Eulerという数学の問題サイトがあります。そのサイトのProblem 26から30を解いてみました。
Problem 26
自分なり直訳してみました。
単位分数は1を含む。単位分数で分母が2から10のものは次で与えられる。
- 1/2 = 0.5
- 1/3 = 0.(3)
- 1/4 = 0.25
- 1/5 = 0.2
- 1/6 = 0.1(6)
- 1/7 = 0.(142857)
- 1/8 = 0.125
- 1/9 = 0.(1)
- 1/10 = 0.1
ここで0.1(6)は0.166666…を表し、1桁の循環節を持つ。1/7は6桁の循環節を持つ。
d < 1000の値で1/dが最も長い循環節を持つものを求めよ。
ソース
int maxRecurringCycle = 0;
int decimal = 0;
for (int i = 2; i < 1000; i++) {
List<Integer> list = new ArrayList<>();
int target = 1;
int rem;
int recurringCycle;
while (true) {
target *= 10;
if (target < i) {
list.add(null);
continue;
}
// 余り
rem = target % i;
if (rem == 0) {
recurringCycle = 0;
break;
} else if (list.contains(rem)) {
recurringCycle = list.size() - list.indexOf(rem) + 1;
break;
}
list.add(rem);
target = rem;
}
if (maxRecurringCycle < recurringCycle) {
maxRecurringCycle = recurringCycle;
decimal = i;
}
}
System.out.println(decimal);割り算を繰り返し、0以外の同じ余りが出現するかを判定します。余りが0ならば割り切れるということになります。Listに余りを格納して、0以外の余りが出現するかどうかを判定しています。
while文の最初のif文では条件がtrueの場合に、listにnullを格納しています。これは商の部分に0を書いて次の位で余りを求める箇所に対応する部分です。listのサイズで循環節の長さを求めるための処置です。
Problem 27
自分なり直訳してみました。
Eulerは以下の2次式を発見した。
$n^2 + n + 41$
0から39の連続した整数nで40個の素数を生成する。しかしながら、nが40では, 40^2 + 40 + 41 = 40(40 + 1) + 41は41で割り切れ、またnが41のときは41^2 + 41 + 41は明らかに41で割り切れる。
$n^2 – 79n + 1601$という式が発見された。nが0から79の連続した値に対して、80個の素数を生成する。係数−79と1601の積は−126479である。
以下の2次式を考える。
$n^2 + an + b$, ここで |a| < 1000かつ|b|<1000であり、
|n|はnの絶対値、つまり、|11| = 11そして|-4| = 4。
n=0から初めて、連続する値で素数を生成する2次式に対して最大長になる場合の、係数aとbの積を求めよ。
ソース
private int coff_a = 0;
private int coff_b = 0;
private void test() {
int maxLength = 0;
int a = 0, b = 0;
for (int i = 0; i < 1000; i++) {
for (int j = 0; j < 1000; j++) {
int length;
length = getLength(i, j);
if (maxLength < length) {
maxLength = length;
a = coff_a;
b = coff_b;
}
length = getLength(i, -j);
if (maxLength < length) {
maxLength = length;
a = coff_a;
b = coff_b;
}
length = getLength(-i, j);
if (maxLength < length) {
maxLength = length;
a = coff_a;
b = coff_b;
}
length = getLength(-i, -j);
if (maxLength < length) {
maxLength = length;
a = coff_a;
b = coff_b;
}
}
}
System.out.println(a * b);
}
private int valueFrom(int n) {
return n * n + coff_a * n + coff_b;
}
private boolean checkPrimaryOf(int n) {
if (n <=1) {
return false;
}
for (int i = 2; i <= (int)Math.sqrt(n); i++) {
if (n % i == 0) {
return false;
}
}
return true;
}
private int getLength(int a, int b) {
coff_a = a;
coff_b = b;
int n = 0;
while (checkPrimaryOf(valueFrom(n))) {
n ++;
}
return n;
}2次式の値はvalueFromメソッドで取得しています。係数は引数にしても良かったのですが、今回はフィールドにしました。
係数を与えて、n=0から順番に値が素数かどうかを求めてます。getLengthメソッドがその個所です。素数の判定はcheckPrimaryOfメソッドで行っています。素数は定義から1より大きい自然数なので、最初にif文を追加しています。引数が負の数、0、1の場合は素数ではないので最初に判定してfalseをreturnしています。
Problem 28
自分なり直訳してみました。
21 22 23 24 25 20 7 8 9 10 19 6 1 2 11 18 5 4 3 12 17 16 15 14 13
対角線の合計は101である。
同じように作った1001個の螺旋では対角線の合計を求めよ。
ソース
private final int SIZE = 1001;
private final int[][] NUMS = new int[SIZE][SIZE];
private int row, col;
private int number = 0;
private void test() {
// 1
row = SIZE / 2 + 1 - 1;
col = SIZE / 2 + 1 - 1;
setNumber();
// 2
col ++;
setNumber();
// 3
row ++;
setNumber();
// 4
col --;
setNumber();
// 5
col --;
setNumber();
// 6
row --;
setNumber();
// 7
row --;
setNumber();
// 8
col ++;
setNumber();
// 9
col ++;
setNumber();
while (col < SIZE - 1) {
moveSpiral();
}
int sum = 0;
for (int i = 0; i < NUMS.length; i++) {
sum += NUMS[i][i];
sum += NUMS[i][SIZE - 1 - i];
}
sum --;
System.out.println(sum);
}
private void moveSpiral() {
// 右に進む
col ++;
setNumber();
int steps;
// 下に進む
steps = (SIZE / 2 - row) * 2 + 1;
for (int i = 1; i <= steps; i++) {
row ++;
setNumber();
}
// 左に進む
steps ++;
for (int i = 1; i <= steps; i++) {
col --;
setNumber();
}
// 上に進む
for (int i = 1; i <= steps; i++) {
row --;
setNumber();
}
// 右に進む
for (int i = 1; i <= steps; i++) {
col ++;
setNumber();
}
}
private void setNumber() {
number ++;
NUMS[row][col] = number;
}1から9までは直に設定し、そのあとはmoveSpiralメソッドで右に1つ進み、下、左、上、右という順に数字を埋める処理をしています。
Problem 29
自分なり直訳してみました。
同じ数を除いて、以下のように15個の異なる項を得る。
4, 8, 9, 16, 25, 27, 32, 64, 81, 125, 243, 256, 625, 1024, 3125
2 ≤ a ≤ 100と2 ≤ b ≤ 100の場合はそのような列は異なる項をいくつ持つか。
ソース
Set<BigInteger> set = new HashSet<>();
for (int a = 2; a <= 100; a++) {
BigInteger bigIntegerBase = new BigInteger(String.valueOf(a));
BigInteger bigInteger = bigIntegerBase;
for (int b = 2; b <= 100; b++) {
bigInteger = bigInteger.multiply(bigIntegerBase);
set.add(bigInteger);
}
}
System.out.println(set.size());べき乗は念のためBigIntegerを使って計算しました。重複を除く操作はHashSetに値を格納することで実現できます。
Problem 30
自分なり直訳してみました。
各桁の4乗の和で表すことができる数は3つのみである。
1634 = 1^4 + 6^4 + 3^4 + 4^4
8208 = 8^4 + 2^4 + 0^4 + 8^4
9474 = 9^4 + 4^4 + 7^4 + 4^4
ただし、1 = 1^4は含めない。
それらの数の和は1634 + 8208 + 9474 = 19316である。
各桁の5乗で表すことができる数の全ての和を求めよ。
ソース
private void test() {
int bound = getBound();
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < 10; i++) {
map.put(i, (int)Math.pow(i, 5));
}
List<Integer> list = new ArrayList<>();
for (int i = 2; i < bound; i++) {
int[] digits = split(i);
int sum = 0;
for (int digit : digits) {
sum += map.get(digit);
}
if (i == sum) {
list.add(i);
}
}
int sum = 0;
for (int num : list) {
sum += num;
}
System.out.println(sum);
}
private int getBound() {
int a = (int)Math.pow(9, 5);
int bound = 1;
while (bound < a) {
a += a;
bound *= 10;
}
return bound;
}
private int[] split(int n) {
String s = String.valueOf(n);
int[] digits = new int[s.length()];
for (int i = 0; i < digits.length; i++) {
digits[i] = s.charAt(i) - '0';
}
return digits;
}各桁のべき乗を求めるため、数字から各桁用の配列に格納するメソッドsplitを自作しました。