<< problem 265 - Binary Circles | Billionaire - problem 267 >> |
Problem 266: Pseudo Square Root
(see projecteuler.net/problem=266)
The divisors of 12 are: 1,2,3,4,6 and 12.
The largest divisor of 12 that does not exceed the square root of 12 is 3.
We shall call the largest divisor of an integer n that does not exceed the square root of n the pseudo square root (PSR) of n.
It can be seen that PSR(3102)=47.
Let p be the product of the primes below 190.
Find PSR(p) mod 10^16.
My Algorithm
The product of all primes below 190 is 2 * 3 * 5 * 7 * ... * 181 = 5397346292805549782720214077673687806275517530364350655459511599582614290.
That number is obviously too large for my poor C++ compiler ... but its logarithm isn't:
log(2) + log(3) + log(5) + ... + log(181) = log(53973462...2614290) approx 167.472
My program looks for an optimal subsets of those primes where
log(p_1) + log(p_2) + ... + log(p_n) approx 167.472 / 2 approx 83.736 = (because log(sqrt{x}) = log(x) / 2)
There are 2^42 approx 4.4 * 10^12 subsets. And again, I have a number that is too large for my computer ...
But there is hope - I split those 42 primes into two equally-sized sets:
the container left
will be "responsible" for the first 21 primes, and right
will control the next 21 primes.
Now there are 2^21 approx 2.1 million subsets of each left
and right
.
For each of those subsets I compute the logarithm of the product of its primes and a bitmask that indicates which primes were used.
If the n-th bit is set the n-th prime was used (that's the case for left
) or the (n+21)-th prime was used (right
).
For each value of left
I need to find the largest value of right
such that their sum doesn't exceed 83.736 (logRoot
).
std::upper_bound
can perform this task very fast if the input data is sorted (but it returns an iterator that is "one step too far").
Until now, all computations were based on logarithms. I could try e^{best sum} but rounding issues produce only garbage.
That's why I have to look at the bitmasks of the best combination of values from left
and right
.
I multiply all used primes according to leftMask
and rightMask
and repeatedly apply modulo 10^16.
Note
Programming languages with proper support for large number probably don't need to deal with logarithms.
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 | ./266
Output:
Note: the original problem's input 190
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 <algorithm>
#include <cmath>
// all primes below 190
std::vector<unsigned int> primes =
{
2, 3, 5, 7, 11, 13, 17, 19, 23, 29,
31, 37, 41, 43, 47, 53, 59, 61, 67, 71,
73, 79, 83, 89, 97, 101, 103, 107, 109, 113,
127, 131, 137, 139, 149, 151, 157, 163, 167, 173,
179, 181
};
// store a subsets logarithm and a bitmask of used primes
struct LogAndBitmask
{
// logarithm of product of used primes
double logarithm;
// bitmask of used primes
unsigned int bitmask;
// for std::sort and std::upper_bound
bool operator<(const LogAndBitmask& other) const
{
return logarithm < other.logarithm;
}
};
int main()
{
unsigned int maxPrime = 190;
std::cin >> maxPrime;
// keep only relevant primes
while (primes.back() > maxPrime)
primes.pop_back();
// compute logarithm of all primes
double logProduct = 0;
std::vector<double> logPrimes;
for (auto p : primes)
{
auto current = log(p);
logPrimes.push_back(current);
logProduct += current;
}
// log(sqrt(x)) = log(x) / 2
double logRoot = logProduct / 2;
// subdivides primes into two equally-sized sets (21 elements each)
const auto half = primes.size() / 2;
// generate all subsets of the lower half of the primes (left)
// and all subsets of the upper half of the primes (right)
// key is the logarithm of product of the used primes, value is the bitmask
// (if n-th bit is set, then the n-th prime is used)
std::vector<LogAndBitmask> right;
for (unsigned int bitmask = 0; bitmask < (1ULL << half); bitmask++)
{
// find logarithm for the upper half of primes
double logRight = 0;
for (unsigned int pos = 0; pos < half; pos++)
if ((bitmask & (1 << pos)) != 0)
logRight += logPrimes[pos + half];
// store logarithms and their generating bitmasks
if (logRight <= logRoot) // skip a few of the very large products
right.push_back({ logRight, bitmask});
}
// sort container / required for fast binary search (the algorithm behind std::upper_bound)
std::sort(right.begin(), right.end());
// find "best" combination of left and right:
// for each value of "left" look for best match in "right"
// keep the highest sum which doesn't exceed logRoot
double best = 0;
unsigned int leftMask = 0; // optimal bitmask for lower primes
unsigned int rightMask = 0; // optimal bitmask for larger primes
for (unsigned int bitmask = 0; bitmask < (1ULL << half); bitmask++)
{
// find logarithm for the same bitmask of the lower half of primes
double logLeft = 0;
for (unsigned int pos = 0; pos < half; pos++)
if ((bitmask & (1 << pos)) != 0)
logLeft += logPrimes[pos];
// how much should come from the bigger primes ?
LogAndBitmask missing = { logRoot - logLeft, 0 }; // bitmask doesn't matter, set to zero
// find best match
auto iteLogRight = std::upper_bound(right.begin(), right.end(), missing);
// ... which will slightly overshoot, therefore go back one step
iteLogRight--;
auto logRight = iteLogRight->logarithm;
// higher than before ?
if (best < logLeft + logRight)
{
best = logLeft + logRight;
// store bitmasks
leftMask = bitmask;
rightMask = iteLogRight->bitmask;
}
}
// last 16 digits of the product
unsigned long long result = 1;
// multiply all relevant primes (according to leftMask and rightMask)
const auto Modulo = 10000000000000000ULL;
// index of current prime
unsigned int currentPrime = 0;
// the first 21 primes ...
for (; currentPrime < half; currentPrime++)
{
// use that prime ?
if ((leftMask & 1) != 0)
{
result *= primes[currentPrime];
result %= Modulo;
}
// next bit
leftMask >>= 1;
}
// ... and the same for the next 21 primes
for (; currentPrime < primes.size(); currentPrime++)
{
// use that prime ?
if ((rightMask & 1) != 0)
{
result *= primes[currentPrime];
result %= Modulo;
}
// next bit
rightMask >>= 1;
}
// print result
std::cout << result << std::endl;
return 0;
}
This solution contains 16 empty lines, 35 comments and 4 preprocessor commands.
Benchmark
The correct solution to the original Project Euler problem was found in 0.7 seconds on an Intel® Core™ i7-2600K CPU @ 3.40GHz.
Peak memory usage was about 36 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
July 3, 2017 submitted solution
July 3, 2017 added comments
Difficulty
Project Euler ranks this problem at 65% (out of 100%).
Links
projecteuler.net/thread=266 - the best forum on the subject (note: you have to submit the correct solution first)
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 a new 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 265 - Binary Circles | Billionaire - problem 267 >> |