A376550 Smallest primes that generate a record number of deranged primes (see Comments).

2, 13, 197, 1097, 10259, 10273, 10369, 10723, 10739, 10937, 13729, 31729, 38791, 101267, 101273, 102139, 102359, 102367, 102397, 105379, 107839, 108793, 109387, 109537, 109873, 130579, 150379, 709831, 1002739, 1002973, 1003879, 1005937, 1008379, 1012369, 1012379

Offset: 1

Author

Ivan N. Ianakiev, Nov 27 2024

Keywords

• nonn
• base

Comments

A derangement is a permutation of the elements of a set in which no element appears in its original position. In the present case, elements and set stand for digits and number.

When counting deranged primes, leading zeros are allowed.

The respective number of deranged primes is: 0,1,2,5,6,8,9,10,12,14,15,17,18,...

From David A. Corneth, Nov 28 2024: (Start)

a(105) > 185000000. Likely a(105)..a(110) are 324908761, 364150279, 403157269, 504921367, 539021467, 724908361 and a(111) onwards > 10^9. If there is any term between 10^8 and 10^9 that is not listed in the b-file and not listed in the candidates I gave then any such term t meets A328447(t) > 103567778 and t > 18500000. (End)

The likely terms a(105)..a(110) above are indeed terms. - Michael S. Branicky, Nov 30 2024

Examples

			The smallest prime generating one deranged prime is 13, where the deranged prime is 31. The smallest prime generating two deranged primes is 197, where the deranged primes are 719 and 971. So, 13 and 197 are terms. Although 10753 is the smallest prime that generates 7 deranged primes it is not a term, since the smaller prime 10273 generates a record of 8 deranged primes.
		

Links

• Michael S. Branicky, Table of n, a(n) for n = 1..138
• David A. Corneth, PARI program
• Wikipedia, Derangement

Crossrefs

Cf. A000040, A000166, A328447.

Programs

Mathematica

(* How to find a(4) among the 4-digit candidates, where z=9 is the number of derangements of a 4-element set *)
Derangements[list_]:=Module[{n=Length[list],perms,isDerangement},
perms=Permutations[list];isDerangement[perm_]:=And@@Table[perm[[i]]!=list[[i]],{i,n}]; Select[perms,isDerangement]];
numberOfPrimeDerangements[n_]:=Length[Select[FromDigits/@Derangements[IntegerDigits[n]],PrimeQ]];
listOf4digitCandidates=Table[{z,Select[Prime/@Range[169,1229],numberOfPrimeDerangements[#]==z&,1]},{z,3,9}]

PARI

\\ See Corneth link

Python

from itertools import islice
from sympy import isprime, nextprime
from sympy.utilities.iterables import multiset_derangements as md
def f(n): return len(set(tuple(d) for d in md(list(str(n))) if isprime(int("".join(d)))))
def agen(): # generator of terms
    record, p = -1, 2
    while True:
        v = f(p)
        if v > record:
            yield p
            record = v
        p = nextprime(p)
print(list(islice(agen(), 26))) # Michael S. Branicky, Nov 27 2024

Extensions

a(14) and beyond from Michael S. Branicky, Nov 27 2024

2 prepended by David A. Corneth, Nov 27 2024