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!)
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

%I

%S 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,

%T 89,96,102,109,117,124,132,141,149,158,166,175,185,194,204,213,223,

%U 234,244,255,267,278,290,301,313,326,338,351,363,376,390,403,417,432

%N 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.

%C 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 G-sequence) 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 bottom-up 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.

%H John Furey, <a href="/A258376/b258376.txt">Table of n, a(n) for n = 1..1000</a>

%F a(n) = Sum_{i=1..n} max(0,A005206(i)-n+i). - _Alois P. Heinz_, Jun 01 2015

%e Following along bottom-up 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.

%Y Cf. A005206, A183137.

%K nonn

%O 1,3

%A _John Furey_, May 28 2015

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 June 23 13:01 EDT 2021. Contains 345401 sequences. (Running on oeis4.)