15
$\begingroup$

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?

$\endgroup$
5
  • 1
    $\begingroup$ Assuming base 10. $\endgroup$
    – z100
    Oct 16, 2023 at 17:50
  • $\begingroup$ Is it worth crossposting this on MathOverflow? $\endgroup$ Oct 23, 2023 at 10:52
  • $\begingroup$ Has anyone actually been able to conclusively prove that a number is not primeable? With an infinite amount of zeroes available, how can you prove that for any integer, a, and any odd integer, b, there is not a value, k, for which $a10^k+b$ is prime? $\endgroup$
    – MWQOJYNWQA
    Oct 25, 2023 at 18:29
  • $\begingroup$ @MWQOJYNWQA I think the rule is that "existing" 0s can be used in the permutation, but not extra 0s. For example 203 -> 023 = 23 (prime, so 203 is primeable) is allowed, but 49 = 049 -> 409 is not allowed (so 49 is not primeable even though 409 is prime). $\endgroup$ Oct 25, 2023 at 19:08
  • $\begingroup$ @Benjamin Wang Okay, I did not pick up on that. Thank you. $\endgroup$
    – MWQOJYNWQA
    Oct 25, 2023 at 19:09

3 Answers 3

8
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ searched with a brute force algorithm? $\endgroup$ Oct 17, 2023 at 6:23
  • $\begingroup$ 45053, 40559, 5660663, 6056669, 6066661 are prime. $\endgroup$
    – Rosie F
    Oct 17, 2023 at 14:33
  • $\begingroup$ @RosieF None of those are permutations of the non-primeable numbers I have listed. $\endgroup$ Oct 17, 2023 at 15:01
  • $\begingroup$ @DanielMathias The OP clarified in a comment to the question, that leading zeroes are allowed. 45053 is a permutation of 04553, 05453 and 05543. $\endgroup$
    – Rosie F
    Oct 17, 2023 at 15:42
  • 2
    $\begingroup$ @RosieF Leading zeroes are allowed in the permutation, not in the number being permuted. $\endgroup$ Oct 17, 2023 at 16:14
5
+50
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Can we do a sum over $x$ to bound the probability of ever finding such a sequence? $\endgroup$ Oct 19, 2023 at 13:18
  • 1
    $\begingroup$ @BenjaminWang Added $\endgroup$
    – isaacg
    Oct 23, 2023 at 15:12
3
$\begingroup$

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).

$\endgroup$
8
  • 1
    $\begingroup$ 23 is a prime so 203 is primeable, isnt't it? $\endgroup$
    – z100
    Oct 16, 2023 at 17:52
  • $\begingroup$ Nice answer, but your claim seems hard to prove. It will be nice to have a construction, in the spirit of the one for arbitrarily long sequence of consecutive composite numbers $\endgroup$ Oct 16, 2023 at 17:52
  • 1
    $\begingroup$ @z100 Edited to include the first sequence if your interpretation is correct. $\endgroup$ Oct 16, 2023 at 18:07
  • 5
    $\begingroup$ $623\to263$ is primeable. $\endgroup$ Oct 16, 2023 at 23:08
  • 3
    $\begingroup$ I agree that the "in general" claim at the end has not been convincingly argued. $\endgroup$ Oct 17, 2023 at 2:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.