math 競技プログラミング

Highly divisible triangular numberの計算

Project Euler Problem 12の解説

公開日: 2021-01-14

  概要
目的 Project Euler Problem 12の解説
参考 高校数学の美しい物語～定期試験から数学オリンピックまで800記事～

1. 今回のスコープ

  • Project Euler Problem 12の解説

Project Euler Problem 12の問題分

The sequence of triangle numbers is generated by adding the natural numbers. So the 7th triangle number would be 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. The first ten terms would be:

    1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...

Let us list the factors of the first seven triangle numbers:

     1: 1
     3: 1,3
     6: 1,2,3,6
    10: 1,2,5,10
    15: 1,3,5,15
    21: 1,3,7,21
    28: 1,2,4,7,14,28

We can see that 28 is the first triangle number to have over five divisors. What is the value of the first triangle number to have over five hundred divisors?

2. 前提

  • 連続する整数は互いに素

命題: 「連続する整数は互いに素」の解説

  • (高校数学の美しい物語～定期試験から数学オリンピックまで800記事～より抜粋です)

背理法で証明する。 $n$ と $n+1$ が互いに素でないと仮定する。このとき，$n$ と $n+1$ の両方を割り切る整数 $p(\geq 2)$が存在する。 p の倍数どうしの差も p の倍数なので，$(n+1)$−n=1 も $p$ の倍数となる。これは $p\geq 2$ に矛盾。

3. プログラミング方針

モジュール

  • find_factors: 任意の自然数の約数の個数を計算する関数
  • find_factors_triangular_number: 今回の本丸。約数の数が入力された自然数より多い最小の三角数を返す関数

(1) 任意の自然数の約数の個数を計算する関数

  • 今回は個数だけ良いので変える値は整数とします（リストや配列だとメモリを食べてしまうので）。
  • searchの範囲は$\sqrt{N}$までとします。
  • searchの範囲内でとある数が約数であると認められた場合、その約数に対応する約数が$\sqrt{N}$以上に存在することに留意
  • 正の平方根が自然数の場合だけ注意

疑似コード

PROCEDURE find_factors(int N)

    SET max_integer to root sqrt of N
    SET result to 0
    SET factor_candidate to 1

    FOR (factor_candidate; factor_candiate <= max_integer; factor_candiate++, step 1)
        IF N % factor_candidate ==0:
            result += 2
        END IF
    END FOR

    IF N == max_integer**2:
        result -= 1
    
    RETURN result  
END

(2) 約数の数が入力された自然数より多い最小の三角数を返す関数

n番目の三角数T(n)は

\[T(n) = \frac{n\times (n+1)}{2}\]

と表せます。このとき、隣り合う正の整数は互いに素なのでT(n)の約数の個数($P(T(n))$と表記する)はnが偶数の場合

\[P(T(n)) = P(n/2)\times P(n+1)\]

と表せます。これを整理すると以下のようになります。

P(T(1)) = P(1) × P(2/2)
P(T(2)) = P(2/2) × P(3)
P(T(3)) = P(3) × P(4/2)
 
(以下略)

なので、n thの三角数の約数の個数を計算するとき、その計算式の第一項がn-1 thの三角数の約数の個数の式の第二項と対応することがわかるので、これを使います。

疑似コード

PROCEDURE find_factors_triangular_number(N):
    
    SET INT result to 0
    SET INT 1st_term to 1
    SET INT 2nd_term to 0
    SET INT i to 0

    WHILE result < N:
        i = i + 1

        IF (i+1) % 2 ==0:
            2nd_term = find_factors(int((i + 1)/2))
        ELSE:
            2nd_term = find_factors((i +1))
        END IF
        
        result = 1st_term * 2nd_term
        1st_term = 2nd_term
    
    END WHILE

    RETURN i*(i+1)/2

4. Pythonでの実行コード

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
40
41

def find_factors(num):
    res = 0
    i = 1
    max_counter = int(num**(1/2))
    
    while (i <= max_counter):
        if num % i ==0:
            res += 2
        i+=1

    if num == max_counter**2:
        res -= 1
    
    return res


def find_factors_triangular_number(N):
    
    res = 0
    current_fac = 1
    next_fac = 0
    index_num = 0

    while res < N:
        index_num+=1
        if (index_num+1) % 2 ==0:
            next_fac = find_factors(int((index_num + 1) / 2))
        else:
            next_fac = find_factors((index_num + 1))
        
        res = current_fac * next_fac
        current_fac = next_fac

    return int(index_num*(index_num + 1) / 2)

def main():
    i = 500
    print(i, find_factors_triangular_number(i))

if __name__ == "__main__":
    main()

5. C言語でのソースコード

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
40
41
42
43
44
45
46
47
48
49
50

#include <stdio.h>
#include <math.h>

int find_factors(int N)
{
    int max_integer = 0;
    int result = 0;
    int factor_candidate = 1;

    max_integer = (int)sqrt(N);

    for (; factor_candidate <= max_integer; factor_candidate++)
    {
        if (N % factor_candidate == 0)
            result += 2;
    }

    if (N == max_integer*max_integer)
        result -= 1;
    
    return result;
}

int find_factors_triangular_number(int N)
{
    int result = 0;
    int first_term = 1;
    int second_term = 0;
    int i = 0;

    while (result < N)
    {
        i++;

        if ((i+1) % 2 == 0)
            second_term = find_factors(((i + 1) / 2));
        else
            second_term = find_factors((i + 1));
        
        result = first_term * second_term;
        first_term = second_term;
    }
    return i*(i+1)/2;
}


void main(void)
{
    printf("%d", find_factors_triangular_number(500));
}
Share Buttons
 Share on:
Feature Tags
Leave a Comment
(注意：GitHub Accountが必要となります）
CONTENTS