login
A363694
Number of edges in the prime (Gruenberg-Kegel) graph of the symmetric group, S_n, on n elements.
1
0, 0, 0, 0, 1, 1, 2, 3, 4, 5, 5, 6, 7, 8, 9, 11, 11, 13, 14, 16, 17, 19, 19, 22, 23, 25, 25, 27, 27, 30, 31, 33, 34, 37, 37, 41, 41, 42, 43, 46, 46, 50, 51, 54, 55, 58, 58, 63, 64, 68, 68, 71, 71, 76, 77, 80, 80, 83, 83, 89, 90, 92, 93, 98, 98, 104, 104, 106, 107, 112, 112, 118, 119
OFFSET
1,7
COMMENTS
For integer n, this is the number of distinct pairs of primes p,q such that p+q <= n.
It appears that n = 30,31 are the only cases of a(n) = n.
LINKS
J. S. Williams, Prime graph components of finite groups, Journal of Algebra, 69(1981), 487-513.
EXAMPLE
For n = 5, the primes dividing the order of S_5 are 2,3,5. There is an element of order 6 in S_5, so there is an edge between 2 and 3, and there are no other edges. So a(5) = 1.
PROG
(Python) # Inefficient but works
import sympy
m = 100
dict1 = {}
for n in range(1, m):
edges = 0
for i in sympy.primerange(n):
for j in sympy.primerange(n):
if i != j and i + j <= n:
edges += 1
dict1[n] = int(edges/2)
print(dict1.values())
(Python)
from sympy import primepi, nextprime
def A363694(n):
c, m, p = 0, 1, 2
while p<<1 < n:
c += primepi(n-p)-m
p = nextprime(p)
m += 1
return c # Chai Wah Wu, Aug 05 2023
CROSSREFS
Sequence in context: A108141 A291811 A291812 * A330292 A017866 A086886
KEYWORD
nonn
AUTHOR
Lixin Zheng, Jun 15 2023
STATUS
approved