cp's OEIS Frontend

A275939 Consider the prime race mod q (where q >= 2) between q*k+1 and q*k-1. Terms are numbers k where q*k+1 first takes lead over q*k-1.

%I A275939 #43 Aug 06 2024 11:03:14
%S A275939 3,608981813029,26861,11,608981813017,71,192252423729713,37,11,23
%N A275939 Consider the prime race mod q (where q >= 2) between q*k+1 and q*k-1. Terms are numbers k where q*k+1 first takes lead over q*k-1.
%C A275939 Values are available for all 2 <= q <= 999 except for 12 and 24. If q is odd and > 3 then 2*q will have the same value in the sequence as q.
%C A275939 Additional terms starting with q = 12 are:
%C A275939 unknown, 53, 71, 331, 17, 239, 37, 213827, 1381, 673, 23, 47, unknown, 101, 53, 379, 29, 59, 331
%C A275939 The longest q*k+1 versus q*k-1 races up to q = 999 are for q = 3,6,8,12,24 and 168. When q = 168 the race ends at prime 273084304417.
%C A275939 The mod 12 and 24 races were checked by computer to 1.1 * 10^14 without q*k+1 ever leading.
%C A275939 Kevin Ford (private communication) provides the following information on these races: "My paper with Richard Hudson contains a lot of information about the location of sign changes for pi(x,q,a)-pi(x,q,b).  Corollary 4 has rigorous upper bounds, but these will likely not be useful to you.  The information in Tables 2 and 3 will be more helpful, as these provide the most likely places to look for the first sign change.  In the case of the mod 12 race, it is probably around exp(187.536), or about 2.79 x 10^{81}.  For the mod 24 race, it's about exp(43.453)=7.437... x 10^{18}".
%D A275939 Ford, Kevin; Konyagin, Sergei; Chebyshev's conjecture and the prime number race. IV International Conference "Modern Problems of Number Theory and its Applications": Current Problems, Part II (Russian) (Tula, 2001), 67-91.
%D A275939 Paulo Ribenboim, The Little Book of Big Primes, Springer 1991
%H A275939 Kevin Ford and Richard H. Hudson, <a href="http://www.math.uiuc.edu/~ford/wwwpapers/lehman.pdf">Sign changes in pi q,a(x) - pi q,b(x)</a>, Acta Arithmetica 100 (2001), 297-314.
%H A275939 Kevin Ford and Sergei Konyagin, <a href="https://citeseerx.ist.psu.edu/pdf/e29b80d3ca8a3cec35c30a69f5346e133c371db3">Chebyshev's conjecture and the prime number race</a>
%H A275939 Andrew Granville and Greg Martin, <a href="http://www.dms.umontreal.ca/~andrew/PDF/PrimeRace.pdf">Prime Number Races</a>, Amer. Math. Monthly, 113 (No. 1, 2006), 1-33.
%H A275939 Andy Martin, <a href="/A275939/a275939.txt">Values for 2 to 999 as far as they are known</a>
%e A275939 For the fourth term q is 5. For primes 2,3,5 and 7 the mod 5 values are 2,3,0 and 2 respectively, so there is no change in the race. For the next prime 11, mod 5 gives 1, q*k+1 now leads 1 to 0, and the race is over.
%o A275939 (C)
%o A275939 /*
%o A275939 C language program used to investigate prime number races.
%o A275939 Computes the first lead of qn+1 over qn-1 for q from 2 to 999.
%o A275939 By Andy Martin oldadit@gmail.com 8/12/2016.
%o A275939 Requires Kim Walisch's primesieve library from http://primesieve.org
%o A275939 Iteration based on the primesieve_iterator.c example.
%o A275939 */
%o A275939 #include <primesieve.h>
%o A275939 #include <inttypes.h>
%o A275939 #include <stdio.h>
%o A275939 #define UPDATE_COUNT 10000000000ull
%o A275939 void race(uint64_t q)
%o A275939 {
%o A275939   uint64_t prime  = 0;
%o A275939   uint64_t m1     = 0;
%o A275939   uint64_t m_1    = 0;
%o A275939   uint64_t rem    = 0;
%o A275939   uint64_t update = UPDATE_COUNT;
%o A275939   primesieve_iterator pi;
%o A275939   primesieve_init(&pi);
%o A275939   while (prime = primesieve_next_prime(&pi)) {
%o A275939     if ((rem = prime % q) == 1){
%o A275939       m1 += 1;
%o A275939     } else if (rem == q-1) {
%o A275939       m_1 += 1;
%o A275939     }
%o A275939     if (m1 > m_1){
%o A275939       printf("Race mod %3llu ends at %12llu with %11llu pi(x;%llu,1) and %11llu pi(x;%llu,%llu)\n",
%o A275939              q, prime, m1, q, m_1, q, q-1);
%o A275939       break;
%o A275939     }
%o A275939     /* Enable for update on long races where q = 3,6,8,12,24,168 */
%o A275939     if (prime > update) {
%o A275939       printf("  Race mod %llu ongoing at prime %llu with m1 %llu and m_1 %llu diff: %llu\n",
%o A275939              q, prime, m1, m_1, m_1 - m1);
%o A275939       update += UPDATE_COUNT;
%o A275939     }
%o A275939   }
%o A275939   primesieve_free_iterator(&pi);
%o A275939 }
%o A275939 int main()
%o A275939 {
%o A275939   uint64_t i;
%o A275939   for(i=2; i<1000; i++){ race(i); }
%o A275939   return(0);
%o A275939 }
%Y A275939 Cf. A007350, A007352.
%K A275939 nonn,more
%O A275939 2,1
%A A275939 _Andy Martin_, Aug 12 2016
%E A275939 a(8)-a(11) from _Andy Martin_, Aug 15 2016