Project-Euler/Problem0012.py at master · leguims/Project-Euler · GitHub

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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
Enonce = """
Highly divisible triangular number

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?
"""

import EulerTools
from operator import add
from functools import reduce
from math import ceil

# Iterator style
class TriangularNumber:
    def __init__(self, start=1, end=None, highest_value=None):
        self.current = 0
        self.index = start-1
        self.index_max = end
        self.highest_value = highest_value

    def __iter__(self):
        return self

    def __next__(self):
        if self.index_max is not None:
            if self.index == self.index_max :
                raise StopIteration
        self.index = self.index + 1
        self.current = self.value(self.index)
        if self.highest_value is not None:
            if (self.highest_value < self.current) :
                raise StopIteration
        return self.current

    def value(self, rank):
        return int((rank+1)*rank/2) # 1+2+3...+(N-2)+(N-1)+N = (N+1)*N/2

def main():
    print(40*"=")
    print(Enonce)
    print(40*"-")

    import time

    Solution = []
    size = 100 #10 #6
    current_size = 0
    start = time.perf_counter()
    rank_power = 1
    factors = set()
    #TriangularNumber().value(pow(10, 1))
    #TriangularNumber().value(pow(10, 5))
    #TriangularNumber().value(pow(10, 10))
    #TriangularNumber().value(pow(10, 20))
    while len(factors) < size:
        triangular = TriangularNumber().value(pow(2, rank_power))
        #print(f"triangular value {triangular}")
        factors.clear()
        factors.add(1)
        factors.add(triangular)
        for factor in EulerTools.PrimeFactorRepeated(highest_value=triangular):
            #print(factor)
            factors.add(factor)
            factors.add(int(triangular/factor))
        #print(f"triangular value {triangular} : {factors}")
        #print(f"triangular value {triangular} have {len(factors)} factors : {factors}")
        print(f"{round(time.perf_counter()-start,2)}s : rank_power = {rank_power} : triangular value {triangular} have {len(factors)} factors : {factors}")
        if len(factors) >= size:
            print(f"triangular value {triangular} have {len(factors)} factors : {factors}")
            break
        rank_power = rank_power + ceil((size - len(factors))/10)
    end = time.perf_counter()
    print(f"{Solution} en {round(end-start,2)} secondes")
    #print(f"List of prime factor of {number} : {Solution}")
    return

    Solution = []
    size = 40 #10 #6
    current_size = 0
    start = time.perf_counter()
    for triangular in TriangularNumber():
        #print(f"triangular value {triangular}")
        factors = set([1, triangular])
        for factor in EulerTools.PrimeFactorRepeated(highest_value=triangular):
            #print(factor)
            factors.add(factor)
            factors.add(int(triangular/factor))
        #print(f"triangular value {triangular} : {factors}")
        #print(f"triangular value {triangular} have {len(factors)} factors : {factors}")
        if len(factors) >= current_size:
            print(f"{round(time.perf_counter()-start,2)}s : triangular value {triangular} have {len(factors)} factors : {factors}")
            current_size = len(factors) + 1
        if len(factors) >= size:
            print(f"triangular value {triangular} have {len(factors)} factors : {factors}")
            break
    end = time.perf_counter()
    print(f"{Solution} en {round(end-start,2)} secondes")
    #print(f"List of prime factor of {number} : {Solution}")

    print(40*"-")
    print("Solution = {}".format(Solution))
    print(40*"=")

if __name__ == "__main__":
    # execute only if run as a script
    main()