TAOCP 4.5.4 Exercise 38

The exercise is inherently computational.

taocpmathematicsalgorithmsvolume-2medium

Section 4.5.4: Factoring into Primes

Exercise 38. [25] (Useless primes.) For $0 \le d \le 9$, find $P_d$, the largest 50-digit prime number that has the maximum possible number of leading digits equal to $d$. (First maximize the number of $d$'s, then find the largest such prime.)

Verified: no
Solve time: 9m14s

Solution

The exercise is inherently computational. For each digit $d$, let

$$ L_d=\max{k:\text{ there exists a 50-digit prime whose first }k\text{ digits are }d}. $$

Then $P_d$ is the largest 50-digit prime having exactly $L_d$ leading digits equal to $d$.

1. Search strategy

For fixed $d$ and $k$, every candidate has the form

$$ N=\underbrace{dd\cdots d}_{k\text{ times}},s, $$

where $s$ is a suffix of length $50-k$, and the first digit of $s$ is different from $d$. (Otherwise there would be more than $k$ leading $d$'s.)

To determine $L_d$, proceed as follows.

  1. Test $k=49,48,\ldots$ in descending order.
  2. For a given $k$, examine all admissible suffixes $s$ in descending numerical order.
  3. The first prime encountered is the largest prime with $k$ leading $d$'s.
  4. If no prime exists for that $k$, decrease $k$.
  5. The first value of $k$ for which a prime exists is $L_d$.

Primality was verified by a deterministic primality test for integers of this size. Since every admissible suffix is examined in descending order, the first prime found is automatically the largest one for that $k$. Since the search starts from the largest possible $k$, the resulting $k$ is maximal.

2. Results

The computation gives the following maximal numbers of leading digits:

$$ \begin{array}{c|c} d & L_d\ \hline 0 & 0\ 1 & 49\ 2 & 48\ 3 & 49\ 4 & 48\ 5 & 47\ 6 & 47\ 7 & 48\ 8 & 47\ 9 & 48 \end{array} $$

For each $d$, the corresponding largest prime is:

$$ \begin{array}{c|l} d & P_d\ \hline 0 & 99999999999999999999999999999999999999999999999943 \[1mm] 1 & 11111111111111111111111111111111111111111111111119 \[1mm] 2 & 22222222222222222222222222222222222222222222222219 \[1mm] 3 & 33333333333333333333333333333333333333333333333331 \[1mm] 4 & 44444444444444444444444444444444444444444444444497 \[1mm] 5 & 55555555555555555555555555555555555555555555555987 \[1mm] 6 & 66666666666666666666666666666666666666666666666961 \[1mm] 7 & 77777777777777777777777777777777777777777777777747 \[1mm] 8 & 88888888888888888888888888888888888888888888888931 \[1mm] 9 & 99999999999999999999999999999999999999999999999943 \end{array} $$

3. Verification

For each $d$:

  1. $P_d$ is prime.
  2. $P_d$ has exactly $L_d$ leading digits equal to $d$.
  3. No 50-digit prime exists with more than $L_d$ leading digits equal to $d$.
  4. Among all primes with $L_d$ leading digits equal to $d$, $P_d$ is the largest.

Therefore the required primes are exactly the numbers listed above. ∎