A Graph Theoretic Formula for the Number of Primes π(n)

2020/03/20 by R. Jacobs, Raphael W. Jacobs, Jacobs, R. +2
Mathematics · #Analytic Number Theory Research #History and Theory of Mathematics #Limits and Structures in Graph Theory #math.CO

paper · pdf · doi:10.48550/arxiv.2003.09475

arxiv created 2020/03/20 · arxiv updated 2020/03/24

Abstract

Let PR[n] be the graph whose vertices are 2,3,…,n with vertex v adjacent to vertex w if and only if gcd(v,w)>1. It is shown that π(n), the the number of primes no more than n, equals the Lovász number of this graph. This result suggests new avenues for graph-theoretic investigations of number-theoretic problems.

Related

• Infinitely-many Primes in ℕ: A Graph Theoretic Approach
• Problems on combinatorial properties of primes
• Estimating the Number of Primes In Unusual Domains
• Finding Cliques of a Graph using Prime Numbers
• The combinatorial algorithm for computing π(x)