Prime Power-of-Two Graphs: The Hidden Topology of the Primes

We study the Prime Power-of-Two Graph G(N) = (V, E), whose vertices are the odd primes p ≤ N and whose edges join pairs of primes that differ by a power of two. The graph itself was already considered by Malm (1993) and has reappeared in recent discussions; what has been largely missing is a systematic computational investigation of its global structure. Using a memory-efficient segmented sieve and a streaming Union-Find algorithm, we construct and analyse G(N) for N = 108 (with a design capable of reaching N = 109 ). Across this range we observe: ˆ a single giant component containing more than 98% of all vertices, ˆ a rapidly decaying tail of small components (almost all of size 1), ˆ a roughly stable mean degree near 3.76, ˆ a persistence function T(p) that remains large for a substantial fraction of primes, ˆ and a set of isolated primes that frequently admit simple modular covering certificates. These observations supply experimental evidence for several natural conjectures concerning the infinite graph on all odd primes. All statements remain computational observations on finite graphs; none constitutes a mathematical proof