Project Euler 45

problem

Triangular numbers, pentagonal numbers, and hexagonal numbers are generated as follows.

Triangular number Tn = n (n + 1) / 2 1, 3, 6, 10, 15, ... Pentagonal number Pn = n (3n-1) / 2 1, 5, 12, 22, 35, ... Hexagonal number Hn = n (2n-1) 1, 6, 15, 28, 45, ... It turns out that T285 = P165 = H143 = 40755.

Find the following triangular, pentagonal, and hexagonal numbers. http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2045

Answer policy

Each term of a hexagonal number is an odd term of a triangular number, but I ignored this fact and thought about a mechanism that makes all terms equal for the time being.

  1. Make a list ang_list by combining the generator gene and the value value of each angle.
  2. The generator updates the value less than the maximum value ang_max until each value is equal. When the value is updated, set the flag to False.
  3. If the value value is not updated for all the corner numbers, the value value of each corner number is equal to the maximum value ang_max, that is, the values of all the corner numbers are equal, so the process ends.

code

from mytools import *


def t(n):
  return n*(n+1)/2

def p(n):
  return n*(3*n-1)/2

def h(n):
  return n*(2*n-1)

@get_time
@main_start
def main():
  #(TRI_START,PEN_START,HEX_START) = (2, 2, 2) 
  (TRI_START,PEN_START,HEX_START) = (286, 166, 144) 
  MAX = 10**8

  tri_gene = ( t(n) for n in xrange(TRI_START, MAX))
  pen_gene = ( p(n) for n in xrange(PEN_START, MAX))
  hex_gene = ( h(n) for n in xrange(HEX_START, MAX))
  ang_list = [
              {'value': tri_gene.next(), 'gene': tri_gene},
              {'value': pen_gene.next(), 'gene': pen_gene},
              {'value': hex_gene.next(), 'gene': hex_gene}
             ]

  ang_max = max(ang_list[0]['value'], ang_list[1]['value'], ang_list[2]['value']) 
  flag = False  
  while not flag:
    flag = True
    for ang in ang_list:
      if ang['value'] < ang_max:
         ang['value'] = ang['gene'].next()
         flag = False
         if ang['value'] > ang_max:
           ang_max = ang['value']
  print ang_max

main()

Recommended Posts

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 45
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
Project Euler 30
Project Euler 16
Project Euler 14
Project Euler 34
Project Euler 25
[Project Euler] problem1
Project Euler15 "Lattice Path"
Project Euler Original Method Group 1
What is Project Euler 3 Acceleration?
[Note] Project Euler in Python (Problem 1-22)
Functional programming in Python Project Euler 3
Project Euler # 5 "Minimum Multiples" in Python
Project Euler 4 Attempt to speed up
Functional programming in Python Project Euler 2
Project Euler 11 "Maximum product in grid"
Project Euler # 15 "Lattice Path" in Python
Project Euler # 4 "Maximum Palindrome" in Python
Project Euler 9 Retention of calculation results
Project Euler # 3 "Maximum Prime Factors" in Python
Project Euler # 11 "Maximum Product in Grid" in Python
Project Euler # 7 "1000 1st prime number" in Python
Project Euler # 16 "Sum of Powers" in Python
Project Euler # 9 "Special Pythagorean Triple" in Python
Project Euler # 14 "Longest Collatz Sequence" in Python
I wrote Project Euler 1 in one liner.
Project Euler # 2 "Even Fibonacci Numbers" in Python
Project Euler # 17 "Number of Characters" in Python
Project Euler # 1 "Multiples of 3 and 5" in Python
Project Euler # 8 "Maximum Product in Number String" in Python
Project Euler # 10 "sum of prime numbers" in Python
Project Euler 28 Inefficient Answer Proposal Create "Spiral Numbers"
Project Euler 4 Coding with a new approach fails.
Django Project Baseline
Project Euler # 12 "High Divisibility Triangular Number" in Python