A321005 - OEIS

%I #57 Feb 28 2020 01:43:47

%S 0,0,1,1,0,1,1,2,1,0,1,2,2,2,2,2,2,3,4,3,2,3,1,2,2,4,2,3,3,4,5,1,3,4,

%T 2,3,4,4,5,1,4,3,6,4,6,4,5,6,4,4,5,4,5,4,8,7,3,5,5,7,7,6,4,10,9,9,8,6,

%U 4,9,9,7,8,6,8,9,9,5,9,6,9,9,6,4,10

%N Let p = prime(n); a(n) = number of pairs of primes (i,j) with i < j < p such that i*j == 1 (mod p).

%C _David James Sycamore_ and Karl Love computed this sequence in early October 2018 and studied its asymptotic growth.

%C See link for conjectured asymptotic behavior of this sequence, showing (red line) first asymptotic term and residual bounds (blue lines). It appears that a(n) ~ Li(p)^2/(2*p), based upon the assumption that the probabilities that the first and second numbers in a pair are primes are independent. The residuals (with minor exceptions for some small p) seem to be bounded by (2/Pi^2)*sqrt(p). These observations were contributed by Karl Love (via Mapleprimes). - _David James Sycamore_, Nov 05 2018

%C If i < j < p in the definition is replaced by i <= j < p, then the only change is that a(2) becomes 1. For if i^2 == 1 (mod p) then p divides i^2-1 = (i-1)*(i+1), which implies p=i+1, so p must be 3 and i must be 2. - _N. J. A. Sloane_, Nov 06 2018

%H Chai Wah Wu, <a href="/A321005/b321005.txt">Table of n, a(n) for n = 1..10000</a>

%H Karl Love, <a href="/A321005/a321005.txt">Maple programs for A321005</a>

%H David James Sycamore, <a href="/A321005/a321005_1.jpg">Asymptotic Behaviour of A321005</a>

%F An alternative heuristic argument leads the conjecture that a(n) ~ (n-4)/(2*log(n)) ~ Pi(n)/2. (Essentially the same as Karl Love's conjecture in the Comments section, but simpler to calculate.) - _N. J. A. Sloane_, Nov 06 2018

%p with(numtheory);

%p f:=proc(n) local m,i,j,c; global pi;

%p if n < 4 then return(0); fi;

%p c:=0; m:=NumberTheory[pi](n); if isprime(n) then m:=m-1; fi;

%p for i from 1 to m-1 do p:=ithprime(i);

%p for j from i+1 to m do

%p if ithprime(j)*p mod n = 1 then c:=c+1; fi; od: od: c; end;

%p [seq(f(ithprime(n)),n=1..120)];

%t a[n_] := Module[{p=Prime[n]}, c=0; Do[Do[If[Mod[Prime[i]*Prime[j],p]==1, c++],{i,1,j-1}], {j,1,n-1} ]; c]; Array[a, 100] (* _Amiram Eldar_, Jan 11 2019 *)

%o (Python)

%o from sympy import nextprime

%o A321005_list, plist = [], [2]

%o for n in range(10000):

%o     c, p = 0, plist[-1]

%o     for j in range(n):

%o         pj = plist[j]

%o         for i in range(j):

%o             if (plist[i]*pj) % p == 1:

%o                 c += 1

%o     A321005_list.append(c)

%o     plist.append(nextprime(p)) # _Chai Wah Wu_, Nov 02 2018

%o (PARI) a(n) = my(vp = primes(n)); sum(i=1, n-2, sum(j=i+1, n-1, (vp[i]*vp[j] % vp[n]) == 1)); \\ _Michel Marcus_, Jan 11 2019

%Y A subsequence of A321004.

%Y The record values produce A321006.

%Y A320276 is an inverse.

%K nonn

%O 1,8

%A _N. J. A. Sloane_, Nov 02 2018, following a suggestion from _David James Sycamore_