

A258376


Number of edges connecting the subgraph on {1, ..., n} with the complement in the minimal graph on positive natural numbers where degree(n) equals n.


1



1, 1, 2, 4, 5, 7, 8, 10, 13, 15, 18, 22, 25, 29, 32, 36, 41, 45, 50, 54, 59, 65, 70, 76, 83, 89, 96, 102, 109, 117, 124, 132, 141, 149, 158, 166, 175, 185, 194, 204, 213, 223, 234, 244, 255, 267, 278, 290, 301, 313, 326, 338, 351, 363, 376, 390, 403, 417, 432
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,3


COMMENTS

A graph can be constructed using each of the numbers n as vertices wherein the degree of each vertex is itself, i.e. the number n corresponds to the unique vertex of degree n. The minimal such simple graph is defined here to be when each number is maximally connected to smaller numbers. In that case, provably each number is connected to the next A005206(n) (Hofstadter Gsequence) greater numbers, e.g. 5 is connected to the next three greater numbers 6, 7, and 8, and 5 is also connected to the two smaller numbers 3 and 4. During bottomup construction of the full graph, the order of the finite subgraph upon addition of each vertex n is obviously n, and the size of this subgraph is provably A183137(n). This subgraph has a(n) connections to the rest of the full graph.


LINKS

John Furey, Table of n, a(n) for n = 1..1000


FORMULA

a(n) = Sum_{i=1..n} max(0,A005206(i)n+i).  Alois P. Heinz, Jun 01 2015


EXAMPLE

Following along bottomup construction, the natural number 1 only connects to 2, so a(1) = 1. The subgraph comprising 1 and 2 only connects to 3, so a(2) = 1. 3 also connects to 4 and 5, so a(3) = 2. The three (Hofstadter G) larger connections of 4 and the one remaining larger connection of 3 yield a(4) = 4.


CROSSREFS

Cf. A005206, A183137.
Sequence in context: A067076 A060686 A004214 * A231979 A072013 A326669
Adjacent sequences: A258373 A258374 A258375 * A258377 A258378 A258379


KEYWORD

nonn


AUTHOR

John Furey, May 28 2015


STATUS

approved



