1

Following the spirit of this question, I developed a program to check how many numbers made of permutations without repetition of the first consecutive positive integers were prime numbers. Let us call $S(n)$ the set of numbers made of all the permutations of the first $n$ positive integers. For instance, $S(3)=\{123,132,213,231,312,321\}$.

For similar reasons to the ones exposed in this partial answer I gave to the question cited, $S(n)$ contains no prime number for $n\neq 3k+1$, as the sum of digits of any permutation in some set $S(3k)$ is divisible by $3$ (and by divisibility criteria it follows that such permutation is divisible by $3$ too), and this in turn implies divisibility by $3$ of any permutation in some set $S(3k-1)$.

Therefore, I have focused only on the sets $S(3k+1)$. Let us call $P(n)$ the subset made of permutations of $S(n)$ that are prime numbers. I found that $$|P(4)|=4$$ $$|P(7)|=534$$ $$|P(10)|=2808500$$

I have not been able to calculate the cardinality of more sets $P(3k+1)$, as my computer runs out of memory for bigger sets (it has to check $(3k+1)!$ numbers!). However, I have come up to the following

Conjecture

Let $D(3k+1)$ count the number of digits of any permutation of some set $P(3k+1)$. Then,

$$\lim_{k\to \infty}\frac{(D(3k+1)-1)!}{|P(3k+1)|}=1$$

It is a "bold" conjecture, as I only have three data to support it: $$\frac{(D(4)-1)!}{|P(4)|}=1.5$$ $$\frac{(D(7)-1)!}{|P(7)|}=1.34$$ $$\frac{(D(10)-1)!}{|P(10)|}=1.292$$

It would be great (i) to have more data that helps to strengthen (or discard) the conjecture, (ii) to have an insight on the reasonability (or not) of it, and (iii) of course, if there is some literature on the subject, more than glad to hear of it!

Thanks in advance!

Juan Moreno
  • 1,110
  • At OEIS A295206 you have another term, and it seems your third one is wrong. – Fabius Wiesner Nov 13 '21 at 12:52
  • How do you define the numbers for $n>9$ ? – Peter Nov 13 '21 at 13:11
  • @Peter for $n=10$, some examples of permutations included in $S(10)$ would be $12345678910$, $11230456789$, $01231456789$,... do you think numbers are not well defined for $n>9$? How can I improve it? – Juan Moreno Nov 13 '21 at 13:24
  • 1
    can you please explain the definition of D(3k+1) – Asher2211 Nov 13 '21 at 13:28
  • So you just use all the digits in the numbers from $1$ to $n$ and count all the permutations that are prime ? – Peter Nov 13 '21 at 13:29
  • @BillyJoe thanks for sharing the sequence A295206 (I did not knew about it). I think the difference is that I have included $0$ as a digit in the permutations. – Juan Moreno Nov 13 '21 at 13:30
  • @Peter exactly, I use all the digits in the numbers from $1$ to $n$ and count all the permutations that are prime. – Juan Moreno Nov 13 '21 at 13:31
  • Apparently, you also allow leading zeros. – Peter Nov 13 '21 at 13:33
  • @Asher2211 $D(3k+1)$ counts the digits of the permutations included in some set $P(3k+1)$; for instance, $D(10)=11$, as the sequence of the first $10$ positive integers is $12345678910$, which has $11$ digits – Juan Moreno Nov 13 '21 at 13:33
  • @Peter correct, I allow leading zeros – Juan Moreno Nov 13 '21 at 20:02
  • FYI, one has $$D(3k+1)-1= 3k+(3k+2)\lfloor\log_{10}(3k+1)\rfloor-\frac{10}{9}\bigg(10^{\lfloor\log_{10}(3k+1)\rfloor}-1\bigg)$$ – mathlove Dec 01 '21 at 11:56
  • As k goes larger, there're a great number of duplicated digits so that the total candidate numbers are far less than D(3k+1)!. It is likely the limit will go to 0 instead of 1. – Zhaohui Du Dec 07 '21 at 04:45
  • Have you explored what happens in bases other than 10? This seems like a natural way to test or generalize the conjecture. Furthermore nothing in your formula really depends on the base, so it would seem a bit unnatural if it only worked in base 10.

    Also you should check whether your conjecture is consistent with Prime Number Theorem or the Cramer random model [https://en.wikipedia.org/wiki/Cram%C3%A9r%27s_conjecture#:~:text=Terence%20Tao.%5B5%5D-,Heuristic%20justification,-%5Bedit%5D]. If it's not, then that would be reason for skepticism.

     – user34722 Dec 07 '21 at 17:44

0 Answers0