A graph theoretic formula for the number of primes (n)

MaRDI QIDQ5148772zbMATH OpenFDO

Authors

Publication date 5 February 2021

Full work available at URL https://arxiv.org/abs/2003.09475, http://math.colgate.edu/~integers/u84/u84.pdf

zbMATH Keywords

Lovász number of graphLovász's theta functionnumber of primes

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Other combinatorial number theory (11B75)

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

Recommendations

• Analytic number theory for graph theory
• scientific article; zbMATH DE number 3340379
• scientific article; zbMATH DE number 3330856
• scientific article; zbMATH DE number 1439467

Cites work

• scientific article; zbMATH DE number 861421 (Why is no real title available?)
• On conjectures of Graffiti
• The sandwich theorem

Cited in

(5)

• The convex hull of the prime number graph
• scientific article; zbMATH DE number 1208028 (Why is no real title available?)
• scientific article; zbMATH DE number 3330856 (Why is no real title available?)
• scientific article; zbMATH DE number 2210065 (Why is no real title available?)
• Analytic number theory for graph theory

Describes a project that uses

Uses Software

• GRAFFITI

This page was built for publication: A graph theoretic formula for the number of primes \(\pi(n)\)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5148772)