A363694 Number of edges in the prime (Gruenberg-Kegel) graph of the symmetric group, S_n, on n elements.

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

Author

Lixin Zheng, Jun 15 2023

Keywords

• nonn

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.

Examples

			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.
		

Links

• J. S. Williams, Prime graph components of finite groups, Journal of Algebra, 69(1981), 487-513.

Programs

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