<< problem 349 - Langton's ant | Prime generating integers - problem 357 >> |
Problem 351: Hexagonal orchards
(see projecteuler.net/problem=351)
A hexagonal orchard of order n is a triangular lattice made up of points within a regular hexagon with side n.
The following is an example of a hexagonal orchard of order 5:
Highlighted in green are the points which are hidden from the center by a point closer to it.
It can be seen that for a hexagonal orchard of order 5, 30 points are hidden from the center.
Let H(n) be the number of points hidden from the center in a hexagonal orchard of order n.
H(5) = 30. H(10) = 138. H(1 000) = 1177848.
Find H(100 000 000).
My Algorithm
All six "triangles" of such a hexagon can be treated equal. I count only the points of the upper-right triangle and multiply the result by 6.
The point in the centre doesn't belong to any triangle and is never hidden.
All points can be thought of as fractions: the points on the right side of centre is 1/1.
The next ring (actually: part of a ring, I'm only looking at one six-th of it) is 1/2 and 2/2, then 1/3, 2/3, 3/3, followed by 1/4, 2/4, 3/4 and 4/4.
Finally the outer-most ring consists of 1/5, 2/5, 3/5, 4/5 and 5/5 for a total of 15 points.
The total number is equivalent to the triangular number T(n) = n(n+1)/2 (with T(5) = 15, see en.wikipedia.org/wiki/Triangular number)
The hidden points are 2/2, 3/3, 2/4, 4/4 and 5/5. Those are exactly the fractions that are not proper fractions:
both numerator and denominator share a common factor such that gcd(n,d) > 1.
The bruteForce()
algorithm checks the gcd() of all fractions. It finds H(1000) within less than 0.04 seconds but becomes very slow for larger values (I assume it's O(n^2 log n)).
However, I've seen similar problems before: counting how often a certain number if coprime to other numbers can be done with Euler's totient function (see en.wikipedia.org/wiki/Euler's totient function).
The guys at Project Euler seem to really like this function because of its namesake ...
Anyway, the number of visible points in a (partial) ring i is phi(i). Then the number of hidden points in that (partial) ring i is i - phi(i).
The number of hidden points in a full ring is therefore 6 * (i - phi(i)).
The solution for an orchard of order n is
(1) sum_{i=1..n} 6 * (i - phi(i))
(2) 6 * sum_{i=1..n} (i - phi(i))
(3) 6 * (sum_{i=1..n} i - sum_{i=1..n} phi(i))
(4) 6 * (n(n+1)/2 - sum_{i=1..n} phi(i))
All I need is an efficient way to compute phi(i) for all i <= 10^8; that's the totient summary function (see mathworld.wolfram.com/TotientSummatoryFunction.html).
If I compute all phi(x) at once with a sieve then I need more than 400 MByte RAM which is more than the inofficial limit of Project Euler
(see sumPhi()
, it takes about 3.5 seconds to finish).
So I rewrote that sieve to work in a segmented way (see sumPhiSliced()
): compute phi(x) for 0 < x < 10^6, then 10^6 <= x < 2 * 10^6, and so on.
The memory consumption shrinks down to just 30 MByte and the program actually becomes a bit faster because of better cache locality (3.1 seconds, minus 0.4 seconds).
Admittedly, the code isn't that nice to look at: I added my prime sieve from my toolbox and it takes quite some code to properly handle all edge cases.
Interactive test
You can submit your own input to my program and it will be instantly processed at my server:
This is equivalent toecho 1000 | ./351
Output:
Note: the original problem's input 100000000
cannot be entered
because just copying results is a soft skill reserved for idiots.
(this interactive test is still under development, computations will be aborted after one second)
My code
… was written in C++11 and can be compiled with G++, Clang++, Visual C++. You can download it, too.
#include <iostream>
#include <vector>
// ---------- gcd() can be found in my toolbox, as well as my fast prime sieve ----------
// greatest common divisor
template <typename T>
T gcd(T a, T b)
{
while (a != 0)
{
T c = a;
a = b % a;
b = c;
}
return b;
}
// odd prime numbers are marked as "true" in a bitvector
std::vector<bool> sieve;
// return true, if x is a prime number
bool isPrime(unsigned int x)
{
// handle even numbers
if ((x & 1) == 0)
return x == 2;
// lookup for odd numbers
return sieve[x >> 1];
}
// find all prime numbers from 2 to size
void fillSieve(unsigned int size)
{
// store only odd numbers
const unsigned int half = (size >> 1) + 1;
// allocate memory
sieve.resize(half, true);
// 1 is not a prime number
sieve[0] = false;
// process all relevant prime factors
for (unsigned int i = 1; 2*i*i < half; i++)
// do we have a prime factor ?
if (sieve[i])
{
// mark all its multiples as false
unsigned int current = 3*i+1;
while (current < half)
{
sieve[current] = false;
current += 2*i+1;
}
}
}
// ---------- problem-specific code ----------
// count all fractions i/j where i is coprime to j
unsigned long long bruteForce(unsigned int limit)
{
unsigned long long hidden = 0;
for (unsigned int i = 1; i <= limit; i++)
for (unsigned int j = 1; j <= i; j++)
if (gcd(i, j) != 1)
hidden++;
return hidden;
}
// needs almost half a GByte RAM
unsigned long long sumPhi(unsigned int limit)
{
// similar to http://www.geeksforgeeks.org/eulers-totient-function-for-all-numbers-smaller-than-or-equal-to-n/
// alternatives can be found here: https://codegolf.stackexchange.com/questions/26739/super-speedy-totient-function
// the sum
unsigned long long result = 1; // phi(1) = 1
// allocate enough memory, fill with 1,2,3,4,...
std::vector<unsigned int> phi(limit + 1);
for (unsigned int i = 0; i < phi.size(); i++)
phi[i] = i;
// look for prime numbers
for (unsigned int i = 2; i <= limit; i++)
{
result += phi[i];
// composite number, already computed phi(i)
if (phi[i] != i)
continue;
// phi(prime) = prime - 1
phi[i]--; // was initially phi[i] = prime
result--;
// adjust all multiples
for (auto j = 2 * i; j <= limit; j += i)
phi[j] = (phi[j] / i) * (i - 1);
}
return result;
}
// adjustable memory consumption
unsigned long long sumPhiSliced(unsigned int limit, unsigned int segmentSize = 1000000)
{
// the sum
unsigned long long result = 1; // phi(1) = 1
// find all primes
fillSieve(limit);
// store them
std::vector<unsigned int> primes = { 2 };
primes.reserve(limit * 6 / 100); // about 6 million primes < 10^8
for (unsigned int i = 3; i <= limit; i += 2)
if (isPrime(i))
primes.push_back(i);
// release memory
sieve.clear();
sieve.shrink_to_fit();
// allocate memory for a single segment
std::vector<unsigned int> phi(segmentSize);
// start with phi(2)
for (unsigned int from = 2; from <= limit; from += segmentSize)
{
auto to = from + segmentSize;
if (to > limit)
to = limit + 1;
// actual size is always identical to segmentSize except for the last slice
auto size = to - from;
// fill with from, from+1, from+2, ...
for (unsigned int i = 0; i < size; i++)
phi[i] = from + i;
// process all multiples of all primes in the current segments
for (unsigned int p = 0; p < primes.size(); p++)
{
auto current = primes[p];
// find smallest multiple in current slice
auto minJ = 2 * current;
if (minJ < from)
{
minJ = (from / current) * current;
if (minJ < from)
minJ += current;
}
// adjust all multiples
for (auto j = minJ; j < to; j += current)
{
auto index = j - from;
phi[index] = (phi[index] / current) * (current - 1);
}
// don't forget about the primes
if (current >= from && current < to)
phi[current - from]--;
}
// add all phi of the current slice
for (unsigned int i = 0; i < size; i++)
result += phi[i];
}
return result;
}
int main()
{
unsigned int limit = 100000000; // 10^8
std::cin >> limit;
// slow brute-force
//unsigned long long result = bruteForce(limit);
// fast algorithm
auto triangle = (unsigned long long)limit * (limit + 1) / 2;
#define SLICED
#ifdef SLICED
auto result = triangle - sumPhiSliced(limit);
#else
auto result = triangle - sumPhi(limit);
#endif
// the previous code analyzed only one sixth of the hexagon
result *= 6;
std::cout << result << std::endl;
return 0;
}
This solution contains 35 empty lines, 42 comments and 6 preprocessor commands.
Benchmark
The correct solution to the original Project Euler problem was found in 3.1 seconds on an Intel® Core™ i7-2600K CPU @ 3.40GHz.
Peak memory usage was about 31 MByte.
(compiled for x86_64 / Linux, GCC flags: -O3 -march=native -fno-exceptions -fno-rtti -std=gnu++11 -DORIGINAL
)
See here for a comparison of all solutions.
Note: interactive tests run on a weaker (=slower) computer. Some interactive tests are compiled without -DORIGINAL
.
Changelog
September 26, 2017 submitted solution
September 26, 2017 added comments
Difficulty
Project Euler ranks this problem at 25% (out of 100%).
Similar problems at Project Euler
Problem 214: Totient Chains
Note: I'm not even close to solving all problems at Project Euler. Chances are that similar problems do exist and I just haven't looked at them.
Links
projecteuler.net/thread=351 - the best forum on the subject (note: you have to submit the correct solution first)
Code in various languages:
C++ github.com/Meng-Gen/ProjectEuler/blob/master/351.cc (written by Meng-Gen Tsai)
C++ github.com/roosephu/project-euler/blob/master/351.cpp (written by Yuping Luo)
C github.com/LaurentMazare/ProjectEuler/blob/master/e351.c (written by Laurent Mazare)
Java github.com/thrap/project-euler/blob/master/src/Java/Problem351.java (written by Magnus Solheim Thrap)
Those links are just an unordered selection of source code I found with a semi-automatic search script on Google/Bing/GitHub/whatever.
You will probably stumble upon better solutions when searching on your own. Maybe not all linked resources produce the correct result and/or exceed time/memory limits.
Heatmap
Please click on a problem's number to open my solution to that problem:
green | solutions solve the original Project Euler problem and have a perfect score of 100% at Hackerrank, too | |
yellow | solutions score less than 100% at Hackerrank (but still solve the original problem easily) | |
gray | problems are already solved but I haven't published my solution yet | |
blue | solutions are relevant for Project Euler only: there wasn't a Hackerrank version of it (at the time I solved it) or it differed too much | |
orange | problems are solved but exceed the time limit of one minute or the memory limit of 256 MByte | |
red | problems are not solved yet but I wrote a simulation to approximate the result or verified at least the given example - usually I sketched a few ideas, too | |
black | problems are solved but access to the solution is blocked for a few days until the next problem is published | |
the flashing problem is the one I solved most recently |
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 | 216 | 217 | 218 | 219 | 220 | 221 | 222 | 223 | 224 | 225 |
226 | 227 | 228 | 229 | 230 | 231 | 232 | 233 | 234 | 235 | 236 | 237 | 238 | 239 | 240 | 241 | 242 | 243 | 244 | 245 | 246 | 247 | 248 | 249 | 250 |
251 | 252 | 253 | 254 | 255 | 256 | 257 | 258 | 259 | 260 | 261 | 262 | 263 | 264 | 265 | 266 | 267 | 268 | 269 | 270 | 271 | 272 | 273 | 274 | 275 |
276 | 277 | 278 | 279 | 280 | 281 | 282 | 283 | 284 | 285 | 286 | 287 | 288 | 289 | 290 | 291 | 292 | 293 | 294 | 295 | 296 | 297 | 298 | 299 | 300 |
301 | 302 | 303 | 304 | 305 | 306 | 307 | 308 | 309 | 310 | 311 | 312 | 313 | 314 | 315 | 316 | 317 | 318 | 319 | 320 | 321 | 322 | 323 | 324 | 325 |
326 | 327 | 328 | 329 | 330 | 331 | 332 | 333 | 334 | 335 | 336 | 337 | 338 | 339 | 340 | 341 | 342 | 343 | 344 | 345 | 346 | 347 | 348 | 349 | 350 |
351 | 352 | 353 | 354 | 355 | 356 | 357 | 358 | 359 | 360 | 361 | 362 | 363 | 364 | 365 | 366 | 367 | 368 | 369 | 370 | 371 | 372 | 373 | 374 | 375 |
376 | 377 | 378 | 379 | 380 | 381 | 382 | 383 | 384 | 385 | 386 | 387 | 388 | 389 | 390 | 391 | 392 | 393 | 394 | 395 | 396 | 397 | 398 | 399 | 400 |
401 | 402 | 403 | 404 | 405 | 406 | 407 | 408 | 409 | 410 | 411 | 412 | 413 | 414 | 415 | 416 | 417 | 418 | 419 | 420 | 421 | 422 | 423 | 424 | 425 |
426 | 427 | 428 | 429 | 430 | 431 | 432 | 433 | 434 | 435 | 436 | 437 | 438 | 439 | 440 | 441 | 442 | 443 | 444 | 445 | 446 | 447 | 448 | 449 | 450 |
451 | 452 | 453 | 454 | 455 | 456 | 457 | 458 | 459 | 460 | 461 | 462 | 463 | 464 | 465 | 466 | 467 | 468 | 469 | 470 | 471 | 472 | 473 | 474 | 475 |
476 | 477 | 478 | 479 | 480 | 481 | 482 | 483 | 484 | 485 | 486 | 487 | 488 | 489 | 490 | 491 | 492 | 493 | 494 | 495 | 496 | 497 | 498 | 499 | 500 |
501 | 502 | 503 | 504 | 505 | 506 | 507 | 508 | 509 | 510 | 511 | 512 | 513 | 514 | 515 | 516 | 517 | 518 | 519 | 520 | 521 | 522 | 523 | 524 | 525 |
526 | 527 | 528 | 529 | 530 | 531 | 532 | 533 | 534 | 535 | 536 | 537 | 538 | 539 | 540 | 541 | 542 | 543 | 544 | 545 | 546 | 547 | 548 | 549 | 550 |
551 | 552 | 553 | 554 | 555 | 556 | 557 | 558 | 559 | 560 | 561 | 562 | 563 | 564 | 565 | 566 | 567 | 568 | 569 | 570 | 571 | 572 | 573 | 574 | 575 |
576 | 577 | 578 | 579 | 580 | 581 | 582 | 583 | 584 | 585 | 586 | 587 | 588 | 589 | 590 | 591 | 592 | 593 | 594 | 595 | 596 | 597 | 598 | 599 | 600 |
601 | 602 | 603 | 604 | 605 | 606 | 607 | 608 | 609 | 610 | 611 |
I scored 13,486 points (out of 15700 possible points, top rank was 17 out of ≈60000 in August 2017) at Hackerrank's Project Euler+.
My username at Project Euler is stephanbrumme while it's stbrumme at Hackerrank.
Look at my progress and performance pages to get more details.
Copyright
I hope you enjoy my code and learn something - or give me feedback how I can improve my solutions.
All of my solutions can be used for any purpose and I am in no way liable for any damages caused.
You can even remove my name and claim it's yours. But then you shall burn in hell.
The problems and most of the problems' images were created by Project Euler.
Thanks for all their endless effort !!!
<< problem 349 - Langton's ant | Prime generating integers - problem 357 >> |