<< problem 381 - (prime-k) factorial | Harshad Numbers - problem 387 >> |
Problem 386: Maximum length of an antichain
(see projecteuler.net/problem=386)
Let n be an integer and S(n) be the set of factors of n.
A subset A of S(n) is called an antichain of S(n) if A contains only one element or if none of the elements of A divides any of the other elements of A.
For example: S(30) = \{1, 2, 3, 5, 6, 10, 15, 30\}
\{2, 5, 6\} is not an antichain of S(30).
\{2, 3, 5\} is an antichain of S(30).
Let N(n) be the maximum length of an antichain of S(n).
Find sum{N(n)} for 1 <= n <= 10^8
My Algorithm
Each number can be factorized into prime numbers. A factor f_i doesn't divide any other factor f_j if:
- f_i and f_j don't share any prime factors or
- if they share prime factors then at least one not not all of their exponents of f_i are greater-or-equal than f_j
- e.g. 60 = 2^2 * 3^1 * 5^1: if f_i = 2^1 * 3^1 and f_j = 5^1 then they are a valid antichain
- but if f_i = 2^2 * 3^1 and f_j = 2^1 * 3^1 then they aren't
search()
computes all factorizations by recursively merging prime numbers in every possible way such that the product remains below limit
.#Those factors are forwarded to
evaluate()
which converts the factors to their exponents, e.g. 60 = 2 * 2 * 3 * 5 = 2^2 * 3^1 * 5^1 becomes {2, 1, 1}
.The interesting thing is that the bases don't matter (they were 2, 3 and 5 in that case) during antichain computation.
Even more, I can't easily re-order them:
std::sort
puts them in ascending order such that the total number of distinct exponents is just over 800(so that memoization can keep the runtime low).
The core functionality is hidden in
antichain()
: based on a list of exponents it recursively determines the maximum length of an antichain.Over the course of multiple days I wrote that function with lots of trial'n'error. It looks simple now but trust me, I typed heaps of ugly code before coming up with the final version ...
It basically "chops off" the exponents from the list by observing that the sum of the exponents of the longest antichain is at most half that of the total sum.
Note
Some code is devoted to memory efficiency, e.g. re-using static containers. It's definitely not the most readable solution I published !
Interactive test
You can submit your own input to my program and it will be instantly processed at my server:
This is equivalent toecho 100 | ./386
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>
#include <map>
#include <algorithm>
// ---------- standard prime sieve from my toolbox ----------
// 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;
// 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 ----------
// compute antichain of exponents, "from" and "to" are iterators like "begin" and "end"
template <typename T>
unsigned int antichain(T from, T to, unsigned int half)
{
// compute sum of exponents
unsigned int sum = 0;
unsigned int numExponents = 0;
for (auto x = from; x != to; x++)
{
sum += *x;
numExponents++;
}
// too few ? => empty antichain
if (sum < half || numExponents == 0)
return 0;
// reduced to a trivial case ? => antichain has one element
if (half == 0 || numExponents == 1)
return 1;
// iterate over all combinations of the first exponent and the remaining exponents
unsigned int result = 0;
for (unsigned int i = 0; i <= *from; i++)
result += antichain(std::next(from), to, half - i);
return result;
}
// "compress" list of prime factors with exponent = 1, e.g. 2,2, 3, 5
// to a list of prime factors with exponents >= 1 => 2^2, 3^1, 5^1 => 2,1,1
// and then compute max. antichain
unsigned int evaluate(const std::vector<unsigned int>& factors)
{
// all factors are sorted, let's count them to get the exponents
// e.g. { 2,2,2,3,5,5 } becomes { 3,1,2 } because it's 2^3 * 3^1 * 5^2
static std::vector<unsigned int> exponents; // static => avoid frequent memory allocations
exponents = { 1 };
for (size_t i = 1; i < factors.size(); i++)
if (factors[i] == factors[i - 1])
exponents.back()++; // same factor as before, increment the last exponent
else
exponents.push_back(1); // new prime factor, add a new exponent 1
// actually the bases don't matter at all, hence I can sort the exponents
// => reduces the number of distinct "exponents" containers considerably
std::sort(exponents.begin(), exponents.end());
// memoize
static std::map<std::vector<unsigned int>, unsigned int> cache;
auto lookup = cache.find(exponents);
if (lookup != cache.end())
return lookup->second;
// compute maximum antichain
auto result = antichain(exponents.begin(), exponents.end(), factors.size() / 2);
cache[exponents] = result;
return result;
}
// generate all numbers and their prime factorization recursively and then compute their max. antichain length
unsigned int search(unsigned int limit, unsigned int current = 1, unsigned int largestFactor = 1)
{
unsigned int result = 0;
// 1 cannot be factored into prime factors, so manually add its antichain size
static std::vector<unsigned int> factors;
if (factors.empty())
result = 1;
// allocate memory for one more prime factor (value doesn't matter, 0 is just a placeholder)
factors.push_back(0);
// each new prime factor must not be smaller then the previously largest
for (auto prime = largestFactor; prime <= limit; prime++)
{
if (!isPrime(prime))
continue;
// found a new number
auto next = (unsigned long long)current * prime;
if (next > limit)
break;
// process number: find length of its longest antichain
factors.back() = prime;
result += evaluate(factors);
// can I multiply it by some larger-or-equal prime ? (and still stay within the limit)
if (next * prime <= limit)
result += search(limit, next, prime); // search numbers with one more prime factor
}
factors.pop_back();
return result;
}
int main()
{
unsigned int limit = 100000000;
std::cin >> limit;
// run prime sieve
fillSieve(limit);
std::cout << search(limit) << std::endl;
return 0;
}
This solution contains 24 empty lines, 35 comments and 4 preprocessor commands.
Benchmark
The correct solution to the original Project Euler problem was found in 8.9 seconds on an Intel® Core™ i7-2600K CPU @ 3.40GHz.
Peak memory usage was about 8 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
November 3, 2017 submitted solution
November 3, 2017 added comments
Difficulty
Project Euler ranks this problem at 40% (out of 100%).
Links
projecteuler.net/thread=386 - the best forum on the subject (note: you have to submit the correct solution first)
Code in various languages:
Python github.com/Meng-Gen/ProjectEuler/blob/master/386.py (written by Meng-Gen Tsai)
C++ github.com/roosephu/project-euler/blob/master/386.cpp (written by Yuping Luo)
C++ github.com/smacke/project-euler/blob/master/cpp/386.cpp (written by Stephen Macke)
C github.com/LaurentMazare/ProjectEuler/blob/master/e386.c (written by Laurent Mazare)
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 | |
[new] | the flashing problem is the one I solved most recently |
I stopped working on Project Euler problems around the time they released 617.
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 | 612 | 613 | 614 | 615 | 616 | 617 | 618 | 619 | 620 | 621 | 622 | 623 | 624 | 625 |
626 | 627 | 628 | 629 | 630 | 631 | 632 | 633 | 634 | 635 | 636 | 637 | 638 | 639 | 640 | 641 | 642 | 643 | 644 | 645 | 646 | 647 | 648 | 649 | 650 |
651 | 652 | 653 |
I scored 13526 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 381 - (prime-k) factorial | Harshad Numbers - problem 387 >> |