<< 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.

# 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.

# Interactive test

You can submit your own input to my program and it will be instantly processed at my server:

This is equivalent to`echo 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)*

# Benchmark

The correct solution to the original Project Euler problem was found in 0.7 seconds on a 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=c++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

green problems solve the original Project Euler problem and have a perfect score of 100% at Hackerrank, too.

yellow problems score less than 100% at Hackerrank (but still solve the original problem).

gray problems are already solved but I haven't published my solution yet.

blue problems are solved and there wasn't a Hackerrank version of it at the time I solved it or I didn't care about it because it differed too much.

red problems are solved but exceed the time limit of one minute or the memory limit of 256 MByte.

*Please click on a problem's number to open my solution to that problem:*

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 |

I scored 13,183 points (out of 15300 possible points, top rank was 17 out of ≈60000 in August 2017) at Hackerrank's Project Euler+.

Look at my progress and performance pages to get more details.

My username at Project Euler is

**stephanbrumme**while it's stbrumme at Hackerrank.

# 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 >> |