Primality, Mobius and harmonic sums

Questions 1 to 5 of 8

1. 1. An AI tool wrote an is_prime(n) that uses only base 2, and it says the test is exact for every 64-bit number. Which input shows the claim is wrong?

   Test 561: it is a Carmichael number, so base 2 must pass itTest 1000000007: it is prime, so the test must reject itTest 2047: it equals 23 × 89, yet it passes the base-2 strong testTest 9: base 2 is not coprime to 9, so the test must give the wrong answer
2. 2. Which statements about the Miller-Rabin code in this lesson are true? Select all that apply.

   Pick every answer that is true.

   A base that is a multiple of n must be skipped, because it gives no informationA plain 64-bit product a * b % m is safe for n near 10^18Base 2 alone is exact for every 64-bit numberThe seven fixed bases give the same answer on every run
3. 3. The program calls pollard_brent directly on the prime 1000000007, and it never returns. Which fix matches the lesson?

   Call is_prime(n) first, and call pollard_brent only when n is compositeRaise the iteration limit so that the search has more stepsUse 32-bit integers, which make the gcd step fasterReplace the seven fixed bases with random bases
4. 4. For n = 10^6, how many inner-loop steps does the nested loop over multiples take in total? Here d runs from 1 to n and m runs from d to n in steps of d. Give the exact count.

   Type a number.

5. 5. Put the steps for counting coprime pairs in a rectangle with the Mobius function in the order the lesson uses them.

   Use the arrows to put the steps in order.

   1. 1.Build prefix sums of mu↑↓
   2. 2.Add (prefix difference) × floor(A / d) × floor(B / d) for each block↑↓
   3. 3.Combine four prefix counts with inclusion-exclusion↑↓
   4. 4.Sieve mu(1..N) once with the linear sieve↑↓
   5. 5.Split d into blocks where floor(A / d) and floor(B / d) stay the same↑↓