-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathProblem12.html
215 lines (197 loc) · 6.95 KB
/
Problem12.html
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
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
<html>
<head>
<title>
Project Euler, Problem 12: Highly Divisible Triangular Number
</title>
<link rel="stylesheet" type="text/css" href="eulerStyle.css" />
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
</head>
<body>
<header>
<svg height="5rem" width="90vw">
<a href="https://dkallen78.github.io/Project-Euler-Files/projectEulerIndex.html">
<text id="euler" x="50%" y="50%" text-anchor="middle" dominant-baseline="middle">
Project Euler
</text>
</a>
</svg>
<br />
<svg height="4rem" width="90vw">
<a href="https://projecteuler.net/problem=12">
<text id="problemID" x="50%" y="50%" text-anchor="middle" dominant-baseline="middle">
Problem 12: Highly Divisible Triangular Number
</text>
</a>
</svg>
</header>
<nav>
<svg height="3rem" width="75vw">
<a href="https://dkallen78.github.io/Project-Euler-Files/Problem11.html">
<text x="0%" y="50%" text-anchor="start" dominant-baseline="middle">
Problem 11
</text>
</a>
<a href="https://dkallen78.github.io/Project-Euler-Files/Problem13.html">
<text x="100%" y="50%" text-anchor="end" dominant-baseline="middle">
Problem 13
</text>
</a>
</svg>
</nav>
<main>
<p>
The sequence of triangle numbers is generated by adding the natural numbers.
So the 7<sup>th</sup> triangle number would be
<math>
<mn>1</mn>
<mo>+</mo>
<mn>2</mn>
<mo>+</mo>
<mn>3</mn>
<mo>+</mo>
<mn>4</mn>
<mo>+</mo>
<mn>5</mn>
<mo>+</mo>
<mn>6</mn>
<mo>+</mo>
<mn>7</mn>
<mo>=</mo>
<mn>28</mn>
</math>.
The first ten terms would be:<br />
<div class="example">
1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...
</div>
<br />
Let us list the factors of the first seven triangle numbers:
<br /><br />
<div class="inset">
<span class="bold">1:</span> 1<br />
<span class="bold">3:</span> 1,3<br />
<span class="bold">6:</span> 1,2,3,6<br />
<span class="bold">10:</span> 1,2,5,10<br />
<span class="bold">15:</span> 1,3,5,15<br />
<span class="bold">21:</span> 1,3,7,21<br />
<span class="bold">28:</span> 1,2,4,7,14,28<br />
</div>
<br />
We can see that 28 is the first triangle number to have over five divisors.
<br /><br />
What is the value of the first triangle number to have over five hundred divisors?
</p>
<button id="problem" onclick="projectEulerProblem12()">
Find Number
</button>
<summary id="notes">
<div id="totalTime"></div>
<p>
I increment up through the triangle numbers until I find one with more than 500 factors.
<br /><br />
First I get a triangle number
(<a href="https://dkallen78.github.io/Project-Euler-Files/Problem6.html">problem 6</a>),
then I find the prime factors
(<a href="https://dkallen78.github.io/Project-Euler-Files/Problem3.1.html">problem 3</a>),
then I find the total number of factors by multiplying the exponents of the
prime factors together.
<br /><br />
###,###
</p>
</summary>
</main>
</body>
<script>
let triangleNumber = 3;
let currentTriangleNumber = 1;
let primeNumbers = [2];
let totalFactors;
let triangleFactors;
function projectEulerProblem12() {
let startTime = new Date();
do {
currentTriangleNumber = getTriangleNumber(triangleNumber);
triangleFactors = findPrimeFactors(currentTriangleNumber);
totalFactors = findTotalFactors(triangleFactors);
triangleNumber++;
}
while (totalFactors < 501);
console.log("Triangle Number " + triangleNumber + " is " + currentTriangleNumber);
console.log("Prime factors of " + currentTriangleNumber + ": " + triangleFactors);
console.log("Total factors of " + currentTriangleNumber + ": " + totalFactors);
let endTime = new Date();
let totalTime = endTime - startTime;
document.getElementById("totalTime").innerHTML = totalTime + " ms";
document.getElementById("notes").style.display = "block";
document.getElementById("problem").innerHTML = currentTriangleNumber;
}
//
//Gets the nth triangle number
function getTriangleNumber(number) {
return ((number * (number + 1)) / 2);
}
//
//Finds the prime factors
function findPrimeFactors(number) {
let factors = [];
//
//This loop divides out the powers of 2
while ((number % 2) === 0) {
factors.push(2);
number /= 2;
}
let numberToTest = 3;
//
//This loop divides out the odd numbers, since we work our way up from 3, we
//don't have to worry about adding an odd composite number to our list of factors
//because we will have removed it as a factor by having already divided out its prime
while ((numberToTest * numberToTest) <= number) {
if ((number % numberToTest) === 0) {
factors.push(numberToTest);
number /= numberToTest;
} else {
numberToTest += 2;
}
}
//
//Having removed the even numbers, and determined that our odd number doesn't divide our
//current number, we have determined that it must be a prime factor and add it to our list
if (number !== 1) {
factors.push(number);
}
return factors;
}
//
//Finds total factors based on the prime factors found
function findTotalFactors(factors) {
let factorCounter = [0];
let x = 0;
let y = 0;
//
//This loop organizes my factors by number of occurence.
while (x < (factors.length)) {
if (factors[x] === factors[x + 1]) {
factorCounter[y]++
} else {
factorCounter.push(0);
factorCounter[y]++;
y++;
}
x++;
}
//
//This loop adds one to every element of my array
for (let z = 0; z < factorCounter.length; z++) {
factorCounter[z]++;
}
let factorTotal = 1;
//
//This multiplies the powers of each factor together to find the total number
//of factors, though not the factors themselves.
for (let z = 0; z < (factorCounter.length); z++) {
factorTotal *= factorCounter[z];
}
return factorTotal;
}
</script>
</html>