Unprimeable Versus Weakly Prime Numbers

Let's clarify the distinction between these two types of numbers:

Unprimeable numbers are composite numbers that remain composite regardless of which single digit is changed to another. These numbers are essentially "immune" to becoming prime through a single-digit modification in base 10, with 200 being the smallest example. 

Key Facts about Unprimeable Numbers:

• Definition: A composite number is unprimeable if changing one digit to any other digit (0-9) never produces a prime number. 

• Smallest Examples: The sequence begins 200, 204, 206, 208, 320, 322, 324, 325, 326, 328, .... 

• Example Case (200): Modifying the first, second, or third digit of 200 always results in a composite number (e.g., changing 200 to 100, 300, 210, 201, etc.). 

• Differentiation: They are sometimes confused with "weakly primes", which are actual prime numbers that cannot be turned into a different prime by changing a single digit.

The reason that I sought the clarification is that the number associated with my diurnal age today, 28151, has a property that allows it membership of OEIS A186995:

  A186995: smallest weak prime in base \(n\).

The initial members of this sequence, up to base 16, are:

127, 2, 373, 83, 28151, 223, 6211, 2789, 294001, 3347, 20837899, 4751, 6588721, 484439, 862789

28151 corresponds to base 6 where it has the representation 334155. This large value surprised me and so I asked Gemini:

OEIS A186995 lists the smallest weak prime in base n and it begins with 127, 2, 373, 83, 28151, 223, 6211, 2789, 294001, 3347, 20837899, 4751, 6588721, 484439, 862789 etc. starting with n=2. When we get to n=6, the base 6 equivalent of 28151 is 334155 but I find it hard to believe that in the first 28150 base 6 numbers there are none that are weakly prime. Can you explain how this is so in the case of base 6.

This was the response: 

The reason the smallest weakly prime number in base 6 jumps so drastically to 28151 (which is 334155 in base 6) lies in the prime factorization of the base itself. Because 6 is the product of the two smallest prime numbers, 2 and 3, it creates a mathematical "divisibility shield" that makes it statistically extremely difficult for a base 6 number to qualify as weakly prime.

Here is the step-by-step mechanics of how this works:

The Mechanics of Digit Substitution

In base 6, a number N is constructed from its digits as:

N = d_k 6^k + d_k-1 6^k-1 + … + d₁ 6¹ + d₀ 6⁰

For a number to be weakly prime, it must first be prime. If N is prime (and greater than 3), it cannot be divisible by 2 or 3. This means it must be an odd number, and it cannot be a multiple of 3.

When you modify a digit d_i to a new value c (where c is between 0 and 5), the difference between the new number and the original prime N is exactly (c − d_i) 6ⁱ.

The Divisibility Shield

For any digit position i ≥ 1, the place value 6ⁱ is always a multiple of 6. Therefore, the difference (c − d_i) 6ⁱ is always an even number and always a multiple of 3.

When you add or subtract a multiple of 2 and 3 to a prime number N, the resulting number maintains the exact same divisibility properties as N modulo 2 and modulo 3. Consequently, any substitution made to the 6¹, 6², 6³ … positions will never produce a number divisible by 2 or 3.

The Statistical Improbability

To satisfy the weakly prime condition, every possible digit substitution must result in a composite number.

In the general integer population, about 66.7% of all numbers are composite simply by being even or a multiple of 3. However, because of the divisibility shield, none of the modified numbers from the higher digit positions can take this "easy" path to being composite. They are forced into the remaining 33.3% of the number line—numbers coprime to 6—where the density of primes is three times higher.

For 334155 in base 6, there are 5 higher digit positions (i ≥ 1), and changing them to the other 5 valid digits yields 25 different modified numbers. All 25 of these must simultaneously be composite, but their prime factors must be drawn exclusively from larger primes (5, 7, 11, 13, etc.). Finding a cluster where 25 specific numbers coprime to 6 all happen to hit composite numbers requires venturing much further up the number line, which is why the sequence jumps so violently to 28151.

You can observe this exact same behavior in OEIS A186995 whenever the base has multiple distinct prime factors. For base 10 (factors 2 and 5), the smallest weakly prime is 294001. For base 12 (factors 2 and 3), it rockets to 20837899. Conversely, in a prime base like base 5 (where the answer is just 83), changing a higher digit easily flips the number from odd to even, quickly satisfying the composite requirement.

Unprimeable Composites and Digitally Delicate Primes

I consult Numbers Aplenty on a daily basis and one of the categories always mentioned is that unprimeable numbers. It's one that I have always ignored but a recent mathematical article kindled my interest:

Mathematicians Discovered a New Kind of Prime Number

In new research, mathematicians have revealed a new category of “digitally delicate” prime numbers. These infinitely long primes turn back to composites faster than Cinderella at midnight with a change of any individual digit.

Digitally delicate primes have infinite digits, and changing any digit to any other value bears a composite number outcome instead. To use a more bite-size example, consider 101, which is a prime. Change the digits to 201, 102, or 111, and you have values that are divisible by 3 and therefore compound numbers.

This idea is decades old, so what’s new? Now, mathematicians from the University of South Carolina have established an even more specific niche of the digitally delicate primes: widely digitally delicate primes. These are primes with added, infinite “leading zeros,” which don’t change the original prime, but make a difference as you change the 0s into other digits to test for delicacy.

So instead of 101, consider 000101. That value is prime, and the zeros are just there for show, basically. But if you change the zeros, like 000101 to 100101, now you have a composite number that’s divisible by 3. The mathematicians believe there are infinite widely digitally delicate primes, but so far, they can’t come up with a single real example. They’ve tested all the primes up to 1,000,000,000 by adding leading zeros and doing the math. 

I won't go into the topic of widely digitally delicate primes in this post but will look at digitally delicate primes that form OEIS A050249:

A050249

Weakly prime numbers (changing any one decimal digit always produces a composite number). Also called digitally delicate primes.

The first few of these sorts of primes are:

294001, 505447, 584141, 604171, 971767, 1062599, 1282529, 1524181, 2017963, 2474431, 2690201, 3085553, 3326489, 4393139, 5152507, 5564453, 5575259, 6173731, 6191371, 6236179, 6463267, 6712591, 7204777, 7469789, 7469797

Clearly these sorts of primes are quite rare. Terence Tao however, has proved that this sequence is infinite. For values 6, 7, 8, 9, 10 of \(k\), the number of terms \(< 10^k \) in this sequence is 5, 35, 334, 3167, 32323. It should be noted that the digits include 0 and so the first number in the sequence, 294001, can become 094001 or simply 94001 which of course is composite.

200 is the first unprimeable number

Unprimeable numbers turn out to be far more numerous and are defined as follows:

A composite number \(n\) is called unprimeable if it cannot be turned into a prime by changing a single digit. 

For example, 144 is not unprimeable, because changing the last digit into a nine we obtain 149, a prime. The number 200 is instead unprimeable (the smallest one), since none of the numbers 201, 203, 207, 205, and 209 are prime and all the other numbers which can be obtained from 200 (say, 300, or 270, or 208) are even, so they are not prime. 

It is easy to prove that unprimeable numbers are infinite, since, for example, all the numbers of the form  \(510+k\cdot 2310\) are unprimeable. Source.

These numbers form OEIS A118118:

A118118

Composite numbers that always remain composite when a single decimal digit of the number is changed.

 The initial members of the sequence are:

200, 204, 206, 208, 320, 322, 324, 325, 326, 328, 510, 512, 514, 515, 516, 518, 530, 532, 534, 535, 536, 538, 620, 622, 624, 625, 626, 628, 840, 842, 844, 845, 846, 848, 890, 892, 894, 895, 896, 898, 1070, 1072, 1074, 1075, 1076, 1078

Notice that 202 is not in the sequence because it can be changed to 002 = 2 which is prime. Otherwise, within a suitable decad, all numbers ending in 0, 2, 4, 5, 6 or 8 will be in the sequence e.g. 320, 322, 324, 325, 326 and 328. Thus the numbers comes in batches within decads that often have wide gaps between them:

• 200, 204, 206, 208
• 320, 322, 324, 325, 326, 328
• 510, 512, 514, 515, 516, 518
• 530, 532, 534, 535, 536, 538
• 620, 622, 624, 625, 626, 628
• 840, 842, 844, 845, 846, 848
• 890, 892, 894, 895, 896, 898
• 1070, 1072, 1074, 1075, 1076, 1078

So this post brings together two different but related categories of numbers: 

• the digitally delicate prime that always changes into a composite number with the alteration of the single digit AND 
• the unprimeable composite that can never change into a prime by the alteration of a single digit