Primeable numbers

Question

Say a positive integer is primeable if it is prime or some permutation of all its digits (leading 0s allowed in permutations) is a prime. Thus the first few primeable numbers are 2, 3, 5, 7, 11, 13, 14, 16, 17, 19, 20, 23, 29, 30, 31, 32, 34, 35, 37, etc.

One cannot find arbitrarily long sequences of consecutive integers all of which are primeable because in any sequence of consecutive integers, however permuted the digits of each of them is, every third will be a multiple of three.

Can one find arbitrarily long sequences of consecutive numbers none of which is primeable?

What is the earliest such sequence with 10 or more terms?

Answer 1

Allowing for zeros to be discarded to form primes with fewer digits, the first sequence containing ten or more consecutive non-primeable numbers is:

$4550,4551,4552,4553,4554,4555,4556,4557,4558,4559,4560$ with 11 numbers.

Related sequences:

$5450,5451,5452,\cdots,5458,5459,5460$ with 11 numbers,
and $5540,5541,5542,\cdots,5554,5555,5556$ with 17 numbers.

Searching all numbers with six or fewer digits, we find another family:

$566660,566661,566662,\cdots,566668,566669,566670$ (11 numbers) $656660,656661,656662,\cdots,656668,656669,656670$ (11 numbers)
$665660,665661,665662,\cdots,665668,665669,665670$ (11 numbers)
$666560,666561,666562,\cdots,666568,666569,666570$ (11 numbers)
$666650,666651,666652,\cdots,666664,666665,666666$ (17 numbers)

Apart from those, there are only four other independent groups of 10 or 11 numbers.

As for arbitrarily long sequences, I think not. Longer sequences will necessarily contain numbers with multiple digits from the set $\{1,3,7,9\}$, providing many more permutations that could be prime.

Update:

I have now checked the primeability of all numbers with nine or fewer digits (i.e. less than one billion). Here is a list of all sequences of ten or more consecutive non-primeable numbers in this range.

 4550 through 4560 (11 numbers)
 5450 through 5460 (11 numbers)
 5540 through 5556 (17 numbers)
 44439 through 44448 (10 numbers)
 55550 through 55560 (11 numbers)
 66660 through 66669 (10 numbers)
 222219 through 222229 (11 numbers)
 566660 through 566670 (11 numbers)
 656660 through 656670 (11 numbers)
 665660 through 665670 (11 numbers)
 666560 through 666570 (11 numbers)
 666650 through 666666 (17 numbers)
 2222220 through 2222229 (10 numbers)
 4444440 through 4444452 (13 numbers)
 5555550 through 5555560 (11 numbers)
 6666660 through 6666669 (10 numbers)
 8888880 through 8888889 (10 numbers)
 44444438 through 44444452 (15 numbers)
 444444444 through 444444456 (13 numbers)
 555555548 through 555555562 (15 numbers)
 888888842 through 888888856 (15 numbers)

While this isn't a proof, it provides a strong argument against arbitrarily long sequences.

Answer 2

Let's try to understand the probability of very large unprimeable numbers. To do so, let's start by looking at how many permutations a number has. If a number has only a single unique digit, it has only one permutation. If it has one digit that isn't the majority digit, it has about $x$ unique permutations, where $x$ is the number of digits. 2 non-majority digits, about $x^2$ unique permutations, and so forth.

Now, let's consider divisibility by different numbers. The main divisibility criteria we need to consider are divisibility by 2, 3, and 5. If the majority digit is 0, 2, 4, 5, 6, or 8, then only permutations ending with the non-majority digit can be prime. If the original number is divisible by three, then all permutations will be divisible by three.

Let's suppose there are $m$ non-majority digits, all of which are 1, 3, 7, or 9, and the number is not divisible by 3. There will be about $x^{m-1}$ unique permutations that are eligible to be prime (end with 1, 3, 7, 9), assuming that the majority digit is 0, 2, 4, 5, 6, or 8.

By the prime number theorem, we expect each of these numbers to be prime with probability about $1/x$. Therefore, the chance that none of them are prime is about

$$(1-1/x)^{x^{m-1}} \approx e^{-x^{m-2}}$$

Note that if $m \ge 4$, this probability is much less than $1/10^x$. But there are only $10^x$ numbers with $x$ digits, so it's unlikely that there are any $x$ digit numbers with $m$ non-majority digits that are unprimeable.

But note that any sequence of $7113-3999=3114$ consecutive numbers must contain at least one number with 4 non-majority digits in the set $\{1, 3, 7, 9\}$ which is not a multiple of 3. The longest sequence of numbers that doesn't have 4 digits in that set is $4000$ through $7110$, and expanding the range to $3999$ to $7113$ avoids the multiples of 3.

That number is overwhelmingly likely to be primeable.

So it's unlikely that there exists a sequence of 3114 unprimeable numbers.

---

Using the estimate of at most a $e^{-x^2}$ probability of any $x$-digit nonprimeable number with 4 non-majority digits in $\{1, 3, 7, 9\}$ that is not divisible by 3, and using @DanielMathias's search of all numbers with at most 9 digits, we can establish the following heuristic bound on the probability of a length 3114 nonprimeable sequence:

$$ \text{Probability} \le \sum_{x=10}^\infty e^{-x^2} 10^x \le 4 \cdot 10^{-34} $$

Calculation

So there is probably no such sequence.

Answer 3

The first such sequence with 10 or more terms is

$200, 201, 202, 203, 204, 205, 206, 207, 208, 209, 210$

because

every "decade" before this (every sequence of 10 numbers of the form $mn0$ to $mn9$) contains at least one prime, and none of these eleven numbers can be primeable because primes can't end with $0$ or $2$.

If we assume that leading zeros are allowed, so that e.g. $203$ is primeable because $23$ (or $023$) is prime, then a similar argument to the above gives the answer as

$620, 621, 622, 623, 624, 625, 626, 627, 628, 629, 630$.

---

In general,

we can find arbitrarily long sequences of non-primeable numbers,

because all we need is

to find strings of non-primes such that all of their non-final digits (i.e. no digits except possibly the last one, or last two, or last three, ...) are $0,2,4,5,6,8$ - there's no way to make these prime because all primes must end with $1,3,7,9$. We can find such arbitrarily long strings of non-primes, because of well known properties of the primes (i.e. they get arbitrarily sparse as we go up).