Upd: the first 8 primes are not enough, because $$$341550071728321 = 10670053 \times 32010157$$$ (for hacker).

===

Hi everyone,

Generally speaking, using the sequence (2, 325, 9375, 28178, 450775, 9780504, 1795265022) as bases in the Miller-Rabin primality test is sufficient to check prime numbers below $$$2^{64}$$$.

However, this sequence is quite hard to remember. Some sources suggest using the first 12 prime numbers as bases, while others claim that the first 8 primes are enough. Unfortunately, these claims lack clear references.

I'm curious about the minimum number of $$$n$$$ if we use the first $$$n$$$ prime numbers as bases for testing primality below $$$2^{64}$$$.

Does anyone know a definitive answer or a reliable source for this?

Thank you!

English is not my native language; please excuse typing errors.

unordered_map<uint64_t, uint64_t> ump;
uint64_t solve(uint64_t n) {
  if (ump.count(n))
    return ump[n];
  uint64_t p = cube(n - 1);
  uint64_t c = p * p * p;
  uint64_t res = solve(c) + solve(n - c) + (n - c);
  ump[n] = res;
  return res;
}

I'm curious about the time complexity of this recursive function.

Here, the function cube is used to calculate the cube root (not the cube). You can assume that it's $$$O(1)$$$ or $$$O(\log n)$$$.

I believe it is $$$\Omega(\sqrt[3]{n})$$$, but I'd like to know a more precise result and analysis.

You can consider that I've preprocessed $$$[0,m]\cap\mathbb{Z}$$$ as a base case for the recursion (which doesn't seem to offer significant optimization).

Can anyone help me?

English is not my native language; please excuse typing errors.

In last night's contest, I didn't come up with the correct solution to problem C. I used many large integers, instead of the least common multiple. But it really worked!

264483249

Can anyone hack it?

English is not my native language; please excuse typing errors.