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,2

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.

Links

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

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

Example

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.

Mathematica

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

Prog

(PARI) a=1; c=2; while (c<50, print1(a", "); a=a+1+omega(c); c++)
(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

Crossrefs

Partial sums of A083399.

Sequence in context: A248106 A033036 A198082 * A047932 A139130 A219087

Adjacent sequences: A082764 A082765 A082766 * A082768 A082769 A082770

Keyword

nonn

Author

Jon Perry, May 24 2003

Extensions

Corrected by T. D. Noe, Oct 25 2006

Status

approved