login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A082767 Number of edges in the prime graph. 2
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 (list; graph; refs; listen; history; text; internal format)
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 INT[n/p], p is 1 or a prime, p < or = n. a(12) = [12/1] + [12/2] + [12/3] + [12/5] + [12/7] + [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

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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified July 29 10:36 EDT 2021. Contains 346344 sequences. (Running on oeis4.)