cp's OEIS Frontend

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

%I A363694 #19 Aug 06 2023 01:52:48
%S A363694 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,
%T A363694 27,30,31,33,34,37,37,41,41,42,43,46,46,50,51,54,55,58,58,63,64,68,68,
%U A363694 71,71,76,77,80,80,83,83,89,90,92,93,98,98,104,104,106,107,112,112,118,119
%N A363694 Number of edges in the prime (Gruenberg-Kegel) graph of the symmetric group, S_n, on n elements.
%C A363694 For integer n, this is the number of distinct pairs of primes p,q such that p+q <= n.
%C A363694 It appears that n = 30,31 are the only cases of a(n) = n.
%H A363694 J. S. Williams, <a href="https://doi.org/10.1016/0021-8693(81)90218-0">Prime graph components of finite groups</a>, Journal of Algebra, 69(1981), 487-513.
%e A363694 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.
%o A363694 (Python) # Inefficient but works
%o A363694 import sympy
%o A363694 m = 100
%o A363694 dict1 = {}
%o A363694 for n in range(1,m):
%o A363694     edges = 0
%o A363694     for i in sympy.primerange(n):
%o A363694         for j in sympy.primerange(n):
%o A363694             if i != j and i + j <= n:
%o A363694                 edges += 1
%o A363694     dict1[n] = int(edges/2)
%o A363694 print(dict1.values())
%o A363694 (Python)
%o A363694 from sympy import primepi, nextprime
%o A363694 def A363694(n):
%o A363694     c, m, p = 0, 1, 2
%o A363694     while p<<1 < n:
%o A363694         c += primepi(n-p)-m
%o A363694         p = nextprime(p)
%o A363694         m += 1
%o A363694     return c # _Chai Wah Wu_, Aug 05 2023
%K A363694 nonn
%O A363694 1,7
%A A363694 _Lixin Zheng_, Jun 15 2023