# [seqfan] Re: New(?) sequence

hv at crypt.org hv at crypt.org
Tue Jan 24 03:58:07 CET 2023

```Below are some results for a slight extension of "what is the last residue
class to be filled in" - I include also composites, but search only for
residue classes coprime to n. (I've only checked the first style,
searching primes from 2 upwards; it is trivial to search instead from
n upwards.)

The list below shows n, last residue class, prime used for last residue
class for 2 <= n <= 100.

Here's some simplistic perl code for it:

use Math::Prime::Util qw{ next_prime gcd };
my(\$limit) = @ARGV;
my \$n = 1;
while (\$n < \$limit) {
++\$n;
# list the residue classes to look for
my %a = map +(\$_ => 1), grep gcd(\$_, \$n) == 1, 1 .. \$n - 1;
my \$m = 1;
while (1) {
\$m = next_prime(\$m);
my \$o = \$m % \$n;
next unless delete \$a{\$o};
# done if there are no residue classes left to find
print("\$n \$o \$m\n"), last if !keys %a;
}
}

Hugo

2 1 3
3 1 7
4 1 5
5 4 19
6 1 7
7 1 29
8 1 17
9 1 19
10 9 19
11 10 43
12 1 13
13 12 103
14 1 29
15 1 31
16 9 41
17 1 103
18 1 19
19 1 191
20 1 41
21 4 67
22 21 43
23 22 137
24 1 73
25 24 149
26 25 103
27 1 109
28 27 83
29 27 317
30 1 31
31 1 311
32 1 97
33 16 181
34 1 103
35 16 191
36 35 71
37 32 439
38 1 191
39 38 233
40 9 89
41 10 379
42 25 67
43 33 463
44 25 113
45 1 181
46 45 137
47 27 967
48 1 97
49 25 613
50 49 149
51 44 197
52 25 181
53 24 607
54 1 109
55 1 331
56 9 233
57 34 433
58 27 317
59 1 709
60 49 109
61 24 1061
62 1 311
63 58 373
64 57 313
65 64 389
66 49 181
67 8 1013
68 49 389
69 65 479
70 51 191
71 48 829
72 49 193
73 72 1021
74 69 439
75 68 293
76 69 373
77 15 631
78 77 233
79 55 1319
80 49 449
81 80 647
82 51 379
83 39 1201
84 1 337
85 1 1021
86 33 463
87 82 691
88 45 397
89 69 1493
90 1 181
91 50 1051
92 25 577
93 50 701
94 27 967
95 58 1103
96 25 313
97 44 1499
98 25 613
99 49 643
100 87 487

Allan Wechsler <acwacw at gmail.com> wrote:
:Still haring off on the idea of finding primes of each residue class of the
:prime p.
:
:Pick a prime, say, 13. Starting with 2, file the primes into their
:appropriate residue classes modulo 13.  The best we could hope for is that
:it would only take 13 primes to do this, but that doesn't happen. Instead,
:we don't find a prime equal to 12 modulo 13 until we reach 103, the 27th
:prime, and 12 is the last residue class of 13 to find a prime
:representative. So it took 14 tries more than the minimum to find prime
:representative of each of the residue classes of 13.
:
:For 2, it takes 0 extra tries. For 3, it takes 1 extra try. For 5, it takes
:3 extra tries (that is, the 8th prime fills out the last vacant residue
:class).
:
:Let A(n) = the number of consecutive primes we need to consider until
:finding a representative of all the residue classes of p_n, minus p_n
:(which is the minimum possible). The initial values of A(n) seem to be 0,
:1, 3, 3, 3, 14, ... and this is not in OEIS.
:
:Another idea would be closer to Zak Seidov's process, and look for
:representatives starting not at 2 but at p_n itself. This is where Zak
:noted that the number of extra tries for 7 is 0. The initial values of this
:sequence are 0, 0, 1, 0, 6, 9, 4, ... and this isn't in OEIS either.
:
:For each search regime we could also ask for the last residue class to be
:filled in. If we always start searching at 2, the last classes are 1, 1, 4,
:6, 10, 12, 1, ..., also not archived. Note that these are, so far,
:always +1 or -1, but I doubt that pattern will persist.
:
:If we start searching at p_n, the recalcitrant classes are  1, 1, 4, 1, 5,
:12, 1, 1, ..., not archived.
:
:This data is all from manual scratching, so I would really appreciate it if
:somebody would confirm (and would be THRILLED if somebody could write some
:code -- these are probably one-liners in Mathematica, Maple, or PARI).
:
:
:On Mon, Jan 23, 2023 at 10:57 AM Allan Wechsler <acwacw at gmail.com> wrote:
:
:> It's still kind of intriguing that:
:>
:> the two consecutive primes starting with 2 cover all residues modulo 2;
:>
:> the three consecutive primes starting with 3 cover all residues modulo 3;
:>
:> (5 fails);
:>
:> the seven consecutive primes starting with 7 cover all residues modulo 7;
:>
:> (11 fails) ...
:>
:> Does any other prime number meet this criterion? It seems unlikely.
:>
:>
:> On Mon, Jan 23, 2023 at 2:24 AM <israel at math.ubc.ca> wrote:
:>
:>> On Jan 22 2023, zak seidov via SeqFan wrote:
:>>
:>> > {7,11,13,17,19,23} + n are primes for n =
:>> > {0,90,16050,19410,43770,1091250,1615830,1954350,2822700,2839920}
:>> and it continues 3243330, 3400200, 6005880, 6503580, 7187760, 7641360,
:>> 8061990, 8741130, 10526550, 11086830, 11664540, 14520540, 14812860,
:>> 14834700, 14856750, 16025820, 16094700, 18916470, 19197240, 19634040,
:>> 19800360, 20112210, 20247030, 21321180, 21850170, 22587270, 24786390,
:>> 25009410, 25524120, 27305550, 29153550, 31563930, 31875570, 32836740,
:>> 33575940, 36319170, 36985290, 37055640, 40660710, 41214060, 41763420,
:>> 41927430, 44842860, 45974550, 47204730, 48660240, 49157730, 50685900,
:>> 50943780, 51255630, 53204850, 53266380, 55057890, 56431920, 57812460,
:>> 59877390, 61052340, 62757960, 63655710, 65689560, 67022220, 69296310,
:>> 72610110, 74283600, 74390070, 75085590, 76150500, 79413060, 82984530,
:>> 87423090, 89483820, 94752720, ...
:>>
:>> More generally, you can have a similar sequence for primes
:>> {p(j), p(j+1), ..., p(k)} as long as these don't cover all residues mod
:>> any of p(j) to p(k).
:>>
:>> >29 + n's are not primes :(
:>>
:>> In case you missed it, that's because {7,11,13,17,19,23,29} cover all
:>> residues mod 7, so at least one of {7,11,13,17,19,23,29} + n will be
:>> divisible by 7.
:>>
:>> Cheers,
:>> Robert
:>>
:>> >Zak Seidov
:>> >zakseidov at yahoo.com
:>> >
:>> >--
:>> >Seqfan Mailing list - http://list.seqfan.eu/
:>> >
:>> >
:>>
:>> --
:>> Seqfan Mailing list - http://list.seqfan.eu/
:>>
:>
:
:--
:Seqfan Mailing list - http://list.seqfan.eu/
```