cp's OEIS Frontend

A065851 Let u be any string of n digits from {0,...,9}; let f(u) = number of distinct primes, not beginning with 0, formed by permuting the digits of u; then a(n) = max_u f(u).

%I A065851 #49 Jul 09 2024 08:55:32
%S A065851 1,2,4,11,39,148,731,4333,26519,152526,1251724,7627713,49545041,
%T A065851 342729012
%N A065851 Let u be any string of n digits from {0,...,9}; let f(u) = number of distinct primes, not beginning with 0, formed by permuting the digits of u; then a(n) = max_u f(u).
%C A065851 From _David A. Corneth_, Jan 25 2022: (Start)
%C A065851 a(12) >= 7627713. a(13) >= 49545041.
%C A065851 There are A006879(12) = 33489857205 primes with 12 digits. There are 2.4*10^11 numbers with 12 digits that are coprime to 30 (i.e. end in 1, 3, 7, 9 and have a digital sum not divisible by 3).
%C A065851 On average one in 2.4*10^11/33489857205 ~= 7.166 of these numbers with 12 digits is prime.
%C A065851 Let maxqprimes(d) be the number of permutations of digits of d without leading 0 and ending in 1, 3, 7 or 9.
%C A065851 Let qprimes(d) be the number of permutations of digits of d (without leading 0 and ending in 1, 3, 7 or 9) that are prime.
%C A065851 a(12) = 7627713 if for some number with 12 digits we have maxprimes(d)/qprimes(d) < 5 (found via a brute force check). This is much less than the expected 7.166.
%C A065851 (At least) 101233456789 with 12 digits has maxqprimes(101233456789) = 54432000. This d = 101233456789 has a shared record for largest value for maxqprimes(d), along with d in {101234567789, 101234567899, 102334567789, 102345677899}. This gives maxqprimes(101233456789)/qprimes(101233456789) ~= 7.136, close to the expected 7.166.
%C A065851 The values d that have maxqprimes(d) >= 5*7627713 all have maxqprimes(d)/qprimes(d) >= 7.13.
%C A065851 For a(12) there are 2.4*10^11 checks needed if we do not use the found bound of 7627713. If we do we can bring down the search space by a factor of about 4 (without any heuristic). If we increase to 7*7627713 we only have about 9*10^8 needed checks left to do. (End)
%H A065851 Kevin Ryde, <a href="/A065851/a065851.c.txt">C Code</a>
%e A065851 a(2) = 2 because 13 and 31 are primes.
%e A065851 a(3) = 4 because {149, 419, 491, 941} or {179, 197, 719, 971} or {379, 397, 739, 937} are primes. - _R. J. Mathar_, Apr 23 2016
%t A065851 c[x_] := Module[{},
%t A065851    Length[Select[Permutations[x],
%t A065851      First[#] != 0 && PrimeQ[FromDigits[#, 10]] &]]];
%t A065851 A065851[n_] := Module[{i},
%t A065851    Return[Max[Map[c, DeleteDuplicatesBy[Tuples[Range[0, 9], n],
%t A065851        Table[Count[#, i], {i, 0, 9}] &]]]]];
%t A065851 Table[A065851[n], {n, 1, 6}] (* _Robert Price_, Mar 30 2019 *)
%o A065851 (Python)
%o A065851 from sympy import isprime
%o A065851 from itertools import combinations_with_replacement
%o A065851 from sympy.utilities.iterables import multiset_permutations
%o A065851 def a(n): return max(sum(1 for p in multiset_permutations(u) if p[0] != "0" and isprime(int("".join(p)))) for u in combinations_with_replacement("0123456789", n) if sum(int(ui) for ui in u)%3)
%o A065851 print([a(n) for n in range(1, 7)]) # _Michael S. Branicky_, Jan 24 2022
%o A065851 (Python)
%o A065851 from collections import Counter
%o A065851 from gmpy2 import next_prime, digits
%o A065851 def A065851(n, base=10):  # change base for A065843-A065850
%o A065851     c, p = Counter(), next_prime(base**(n-1))
%o A065851     while p < base**n:
%o A065851         c["".join(sorted(digits(p, base)))] += 1
%o A065851         p = next_prime(p)
%o A065851     m = min(c.most_common(1))
%o A065851     return m[1]
%o A065851 print([A065851(n) for n in range(1, 8)]) # _Michael S. Branicky_, May 28 2024
%o A065851 (C) /* See links. */
%Y A065851 Cf. A006879, A373179 (digits attaining).
%Y A065851 Cf. A065843, A065844, A065845, A065846, A065847, A065848, A065849, A065850, A065852, A065853.
%K A065851 nonn,base,more
%O A065851 1,2
%A A065851 _Sascha Kurz_, Nov 24 2001
%E A065851 1 more term from _Sean A. Irvine_, Sep 06 2009
%E A065851 Definition corrected by _David A. Corneth_, Apr 23 2016
%E A065851 a(11) from _David A. Corneth_, Jan 25 2022
%E A065851 a(12)-a(14) from _Kevin Ryde_, Jul 09 2024