Project Euler # 12 "High Divisibility Triangular Number" in Python

Problem 12 "Advanced Divisibility Triangular Number"

The sequence of triangular numbers is represented by the sum of natural numbers, the 7th triangular number is 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. The first 10 terms of the triangular number are:

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

Becomes. The divisors of the first 7 terms are listed below.

 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

From this we can see that the 7th triangular number 28 is the first triangular number with more than 5 divisors. Then, some of the first triangular numbers have divisors more than 500.

Python


import math

# limit = 5
limit = 500

def compute_factors(num):
  factors = [1]
  if(num == 1): return factors
  for i in range(2, int(math.floor(math.sqrt(num))) + 1):
    if(num % i == 0):
      factors.append(i)
  factors_rev = list(factors)
  factors_rev.reverse()
  for i in factors_rev:
    fac = num // i
    if(fac not in factors):
      factors.append(fac)
  return factors

triangular_nums = [1]
factors = []
n = 2
while True:
  triangular_num = triangular_nums[n-1-1] + n
  triangular_nums.append(triangular_num)
  factors = compute_factors(triangular_num)
  if(len(factors) > limit):
    break
  n += 1

result = triangular_nums[-1]

print result
print result == 76576500
print n
print factors[:10]

result


76576500
True
12375
[1, 2, 3, 4, 5, 6, 7, 9, 10, 11]

Recommended Posts

Project Euler # 12 "High Divisibility Triangular Number" in Python
Project Euler # 7 "1000 1st prime number" in Python
Project Euler # 17 "Number of Characters" in Python
Project Euler # 8 "Maximum Product in Number String" in Python
[Note] Project Euler in Python (Problem 1-22)
Functional programming in Python Project Euler 3
Project Euler # 5 "Minimum Multiples" in Python
Functional programming in Python Project Euler 2
Project Euler # 15 "Lattice Path" in Python
Project Euler # 4 "Maximum Palindrome" in Python
Project Euler # 3 "Maximum Prime Factors" in Python
Project Euler # 11 "Maximum Product in Grid" in Python
Project Euler # 16 "Sum of Powers" in Python
Project Euler # 14 "Longest Collatz Sequence" in Python
Project Euler # 2 "Even Fibonacci Numbers" in Python
Project Euler # 1 "Multiples of 3 and 5" in Python
Project Euler # 10 "sum of prime numbers" in Python
Project Euler # 13 "Sum of Large Numbers" in Python
Project Euler # 6 "Difference in sum of squares" in Python
Prime number 2 in Python
Number recognition in images with Python
Infinite prime number generator in Python3
Study, number guessing game in Python
Project Euler 11 "Maximum product in grid"
Project Euler 7
Project Euler 47
Project Euler 31
Project Euler 38
Project Euler 17
Project Euler 8
Project Euler 23
Project Euler 22
Project Euler 19
Project Euler 50
Project Euler 42
Project Euler 32
Project Euler 35
Project Euler 36
Project Euler 46
Project Euler 48
Project Euler 6
Project Euler 44
Project Euler 39
Project Euler 40
Project Euler 49
Project Euler 29
Project Euler 27
Project Euler 41
Project Euler 18
Project Euler 13
I wrote Project Euler 1 in one liner.
Project Euler 30
Project Euler 16
Project Euler 14
Project Euler 34
Project Euler 25
Output the number of CPU cores in Python
Prime number enumeration and primality test in Python
Quadtree in Python --2
Python in optimization
CURL in python