A082767 Number of edges in the prime graph.

1, 3, 5, 7, 9, 12, 14, 16, 18, 21, 23, 26, 28, 31, 34, 36, 38, 41, 43, 46, 49, 52, 54, 57, 59, 62, 64, 67, 69, 73, 75, 77, 80, 83, 86, 89, 91, 94, 97, 100, 102, 106, 108, 111, 114, 117, 119, 122, 124, 127, 130, 133, 135, 138, 141, 144, 147, 150, 152, 156, 158, 161, 164, 166, 169, 173

Offset: 1

Author

Jon Perry, May 24 2003

Keywords

• nonn

Comments

The prime graph is defined to be the graph formed by writing the integers 0 to n in a straight line as vertices and then connecting i and j (i > j) iff i-j=1 or i=j+p, where p is a prime factor of i. It can be visualized as the Sieve of Eratosthenes, with each integer connected to its neighbors and the striking out process as a wave forming the remaining edges.

Examples

			a(1) = 1.
a(2) = a(1) + 1 + omega(2) = 1 + 1 + 1 = 3.
a(6) = a(5) + 1 + omega(6) = 9 + 1 + 2 = 12.
		

Links

• Vincenzo Librandi, Table of n, a(n) for n = 1..2000

Crossrefs

Partial sums of A083399.

Programs

Magma

I:=[1]; [n le 1 select I[n] else Self(n-1)+1+#PrimeDivisors(n): n in [1..70]]; // Vincenzo Librandi, Jun 10 2017

Mathematica

Accumulate[PrimeNu[Range[120]] + 1] (* Vincenzo Librandi, Jun 10 2017 *)

PARI

a=1; c=2; while (c<50,print1(a","); a=a+1+omega(c); c++)

Formula

a(n) = a(n-1) + 1 + omega(n) if n > 1, with a(1) = 1, where omega(n) is the number of distinct prime factors of n.

a(n) = Sum_{p is 1 or a prime, p <= n} floor(n/p); e.g., a(12) = floor(12/1) + floor(12/2) + floor(12/30) + floor(12/5) + floor(12/7) + floor(12/11) = 12 + 6 + 4 + 2 + 1 + 1 = 26. - Amarnath Murthy, Jul 06 2005

Extensions

Corrected by T. D. Noe, Oct 25 2006