[seqfan] Permutations classes in primes
David Corneth
davidacorneth at gmail.com
Fri May 31 15:28:54 CEST 2024
Hi all,
So I was browsing oeis.org/history to see what's going on and came
across A065844 called
"Let u be any string of n digits from {0,1,2}; 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)."
which is part of a family of sequences varying possible digits.
Though finding more terms for those 'brute force sequences' usually
are out of reach for me I gave this one a go by looking at permutation
classes. A permutation class is a specific frequency of digits in a
number. So 10112 and 21110 are in the same permutation class as they
have the same number of 0's, 1's and 2's (1, 3, 1) respectively.
I gave this idea a go but I could use your help for an optimization by either.
- give a "strong" upper bound of primes in a permutation class. Like,
say, at most 1 in 5 of these numbers is prime. Or, say, at most
1325189140 of these numbers are prime. Maybe by showing some of them
must be divisible by at least one of 5, 7, 11, 13, ... (2 and 3 are
taken care of)
- show that it is sufficient to only check a permutation class that
has the most permutations
I started a search for A065844(25) and got a lower bound being 1325189141.
I go through the permutations classes for base 3 similar to A179239
and check the number of primes in that class.
In some cases that's pretty quick. If the sum of base-3 digits is even
then none of them is prime.
If that sum of digit is odd then I check the number of primes it could
give at most (and this can be improved I think) by seeing how many
permutations have a 1 or a 2 at the start AND a 1 or a 2 at the end
(so doesn't start and doesn't end in 0). I'll show an example for
permutation class 10112.
If there is a permutation starting and ending at 1 then between those
digits there is {0, 1, 2} for which there are 6 permutations.
If there is a permutation starting and ending with 1 and 2 then
between them there is {0, 1, 1} and so that is 3 permutations. We
could have (start, end) in {(1, 2), (2, 1)} so that's 2 options for
that and we multiply by 2 to get 6 permutations.
We cannot have 2 at the start and at the end as in 10112 there is just one 2.
So a total of 6+6 = 12 primes at most for 10112.
I think it's important to check numbers starting and ending in 1 or 2
rather than just number of permutations. For example for a(25) there
are more permutations for (eight 0's, nine 1's and eight 2's) than
there are for (seven 0's, nine 1's and nine 2's) but an equal amount
both start and end in 1 or 2.
Using this maximum number of primes we can somewhat restrict the
search. I'll show this by a computation of A065844(21) below. The
permutation classes shown have an odd sum of digits. They are sorted
decreasing by number of primes *found* in their permutation class. I
say *found* because in some cases I didn't search for primes because
even if all of those numbers where primes it would never be more than
the maximum number of primes in a class found so far. So here is the
table:
index | permutation class |
#primes found |max #number of primes| ratio max number of primes over
#primes found (where at least 1 prime is found)
1 | [1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2] |
161857 924924
5.7144516455883897514472651785217815726
-------------------------------------------------------------------------------------------------------
if we would know that
2 | [1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2] |
138732 792792
5.7145575642245480494766888677450047574 - if this class gives the
record then more than 1 in 792792/161857 = 4.89810.... of the numbers
are prime.
3 | [1, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2] |
138589 792792
5.7204540042860544487657750615128184777 - if this class gives the
record then more than 1 in 792792/161857 = 4.89810.... of the numbers
are prime.
4 | [1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 2] |
132806 756756
5.6982064063370630844991943135099317802 - if this class gives the
record then more than 1 in 756756/161857 = 4.67546.... of the numbers
are prime.
5 | [1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2] |
116909 660660
5.6510619370621594573557211164238852441
6 | [1, 0, 0, 0, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2] |
109846 624624
5.6863609052673743240536751452032845984
7 | [1, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2] |
81182 468468
5.7705895395531029045847601685102608953
8 | [1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2] |
76169 432432
5.6772702805603329438485473092728012709
9 | [1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 2, 2, 2] |
63995 360360
5.6310649269474177670130478943667474021
10 | [1, 0, 0, 0, 0, 0, 0, 1, 1, 2, 2, 2, 2, 2, 2, 2] |
62594 360360
5.7571013196152985909192574368150301946
11 | [1, 0, 0, 0, 0, 0, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2] |
57069 330330
5.7882563212952741418283130946748672660
12 | [1, 0, 0, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2] |
54696 312312
5.7099605089951733216322948661693725318
13 | [1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 2, 2, 2, 2, 2, 2] |
50751 288288
5.6804397942897676893066146479872317787
14 | [1, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2] |
45561 260260
5.7123416957485568797875375869713131845
15 | [1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2] |
38499 220220
5.7201485752876698096054442972544741422
16 | [1, 0, 0, 0, 0, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2] |
38123 220220
5.7765653280172074600634787398683209611
17 | [1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2] |
32369 182182
5.6282863233340541876486762025394667738
18 | [1, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2] |
31533 182182
5.7775029334348143215044556496368883392
19 | [1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2] |
29491 168168
5.7023498694516971279373368146214099217 - finding 168168-161857+1 =
6312 nonprimes in this class is enough to show that this class doesn't
give the record
20 | [1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 2, 2, 2, 2, 2] |
29301 168168
5.7393263028565577966622299580219105150 - finding 168168-161857+1 =
6312 nonprimes in this class is enough to show that this class doesn't
give the record
-------------------------------------------------------------------------------------------------------
all these classes don't have to be checked if we make our initial
guess of 161857 as maximum (found by checking class with most
permutations)
21 | [1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 2, 2] |
21834 123552
5.6586974443528441879637262984336356142
22 | [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 2, 2, 2, 2] |
12284 70070
5.7041680234451318788668186258547704331
23 | [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2] |
7539 42042
5.5766016713091922005571030640668523677
24 | [1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 2] |
4354 24024
5.5176848874598070739549839228295819936
25 | [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 2, 2, 2] |
3557 20020
5.6283384874894574079280292381220129322
26 | [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 2, 2, 2, 2, 2] |
2410 14014
5.8149377593360995850622406639004149378
27 | [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2] |
1121 6006
5.3577163247100802854594112399643175736
28 | [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 2, 2, 2, 2] |
1073 6006
5.5973904939422180801491146318732525629
29 | [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 2, 2] |
634 3640
5.7413249211356466876971608832807570978
30 | [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 2, 2, 2] |
335 1820
5.4328358208955223880597014925373134328
31 | [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 2] |
59 364
6.1694915254237288135593220338983050848
32 | [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1] |
58 364
6.2758620689655172413793103448275862069
33 | [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 2, 2] |
56 364
6.5000000000000000000000000000000000000
34 | [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 2] |
8 42
5.2500000000000000000000000000000000000
35 | [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1] |
5 14
2.8000000000000000000000000000000000000
36 | [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2] |
1 2
2.0000000000000000000000000000000000000
-------------------------------------------------------------------------------------------------------
below this line no primes where searched as the maximum number of
primes is always less then optimum found so far (161857 or maybe
another record).
37 | [1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2] |
0 16
38 | [1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2] |
0 560
39 | [1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2] |
0 4368
40 | [1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2] |
0 11440
41 | [1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2] |
0 11440
42 | [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2] |
0 4368
43 | [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2] |
0 560
44 | [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2] |
0 16
45 | [1, 0, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2] |
0 210
46 | [1, 0, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2] |
0 6370
47 | [1, 0, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2] |
0 42042
48 | [1, 0, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2] |
0 90090
49 | [1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2] |
0 70070
50 | [1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2] |
0 19110
51 | [1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2] |
0 1470
52 | [1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] |
0 14
53 | [1, 0, 0, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2] |
0 1274
54 | [1, 0, 0, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2] |
0 33124
55 | [1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2] |
0 33124
56 | [1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2] |
0 1274
57 | [1, 0, 0, 0, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2] |
0 4732
58 | [1, 0, 0, 0, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2] |
0 104104
59 | [1, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2] |
0 28392
60 | [1, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] |
0 364
61 | [1, 0, 0, 0, 0, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2] |
0 12012
62 | [1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2] |
0 12012
63 | [1, 0, 0, 0, 0, 0, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2] |
0 22022
64 | [1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2] |
0 110110
65 | [1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] |
0 2002
66 | [1, 0, 0, 0, 0, 0, 0, 2, 2, 2, 2, 2, 2, 2, 2, 2] |
0 30030
67 | [1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 2] |
0 30030
68 | [1, 0, 0, 0, 0, 0, 0, 0, 2, 2, 2, 2, 2, 2, 2, 2] |
0 30888
69 | [1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1] |
0 3432
70 | [1, 0, 0, 0, 0, 0, 0, 0, 0, 2, 2, 2, 2, 2, 2, 2] |
0 24024
71 | [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1] |
0 2002
72 | [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] |
0 0
Any ideas or thoughts?
Best,
David
More information about the SeqFan
mailing list