Tìm số tam giác có số lượng ước số là 500 ?

Problem 12: Highly divisible triangular number

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?

Đề bài

Chuỗi các số tam giác được định nghĩa bằng cách cộng thêm tuần tự các số vào tổng.

Ví dụ: Số thứ 7 trong chuỗi là 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28.

10 số đầu tiên được tính là: 1: 1 2: 1 + 2 = 3 3: 1 + 2 + 3 = 6 4: 1 + 2 + 3 + 4 = 10 5: 1 + 2 + 3 + 4 + 5 = 15 6: 1 + 2 + 3 + 4 + 5 + 6 = 21 7: 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28 8: 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 = 36 9: 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 = 45 10: 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10 = 55

Các ước số tương ứng của chúng (không kể chính nó) là: 1: 1 –> 0 3: 1, 3 –> 1 ước 6: 1, 2, 3, 6 –> 3 ước 10: 1, 2, 5, 10 –> 3 ước 15: 1, 3, 5, 15 –> 3 ước 21: 1, 3, 7, 21 –> 3 ước 28: 1, 2, 4, 7, 14, 28 –> 5 ước.

Chúng ta có thể thấy 28 là số đầu tiên trong chuỗi tam giác số có 5 ước số.

Hãy tìm số đầu tiên của chuỗi tam giác số có 500 ước số.

Phân tích đề bài:

Để hiểu được đề bài của bài này, tôi đã mất khá nhiều thời gian để tìm hiểu “The sequence of triangle numbers” có nghĩa là gì.

Cuối cùng mãi mới hiểu được ý nghĩa của nó và giải thích ở đề bài phía trên.

Quay lại giải quyết bài toán, chúng ta phải giải quyết các vấn đề:

Vấn đề 1: Tính tổng các số đến N –> sum_numbers Vấn đề 2: Tìm kiếm danh sách các ước số của sum_numbers. Vấn đề 3: Nếu ước số đã chạm mức 500 thì dừng lại.

Đi vào giải từng vấn đề Vấn đề 1: Công thức tính tổng các số tự nhiên liên tiếp thì chúng ta đã có: sum_numbers = N * (N + 1) / 2

Vấn đề 2: Tìm ước số của 1 số. Có nhiều phương pháp để giải quyết bài toán này nhưng tôi không có nhiều thời gian để tìm hiểu và giải thích, vì vậy tôi đưa ra cách làm “trâu bò” như sau:


def count_divisor_of_number(number):
    sqrt_number = int(math.sqrt(number))
    count_divsor = 0
    for index in range(1, sqrt_number + 1):
        if not number % index:
            count_divsor += 2
    if sqrt_number * sqrt_number == number:
        count_divsor -= 1
    return count_divsor

Giờ bắt đầu chạy từ N = 0 đến vô cùng thôi.

import math

DIVISOR_COUNT = 500


def count_divisor_of_number(number):
    sqrt_number = int(math.sqrt(number))
    count_divsor = 0
    for index in range(1, sqrt_number + 1):
        if not number % index:
            count_divsor += 2
    if sqrt_number * sqrt_number == number:
        count_divsor -= 1
    return count_divsor


def find_first_triangle_number():
    sum_numbers = 3
    next_number = 3
    while count_divisor_of_number(sum_numbers) < DIVISOR_COUNT:
        sum_numbers += next_number
        next_number += 1
    return sum_numbers


if __name__ == "__main__":
    import time
    start = time.time()
    result = find_first_triangle_number()
    done = time.time()
    print("The first triangle number with over {} divisors is: {}".format(DIVISOR_COUNT, result))
    elapsed = done - start
    print("elapsed time: {}s".format(elapsed))

Thời gian chạy trên máy của tôi:

The first triangle number with over 500 divisors is: 76576500
elapsed time: 3.9072110652923584s

4 seconds, cũng tạm ổn cho bài toán “vét cạn”.

Ở đây tôi giảm được một số vòng lặp và phép so sánh. Bao gồm: Đặt sum_numbers = 3, next_number = 3 –> Bắt đầu vòng lặp với số tam giác thứ 2.

Làm như này, tôi sẽ bỏ qua được việc kiểm tra number <= 1 ở function count_divisor_of_number.

Source-code: PE-012