A080036 a(n) = n + round(sqrt(2*n)) + 1.

1, 3, 5, 6, 8, 9, 10, 12, 13, 14, 15, 17, 18, 19, 20, 21, 23, 24, 25, 26, 27, 28, 30, 31, 32, 33, 34, 35, 36, 38, 39, 40, 41, 42, 43, 44, 45, 47, 48, 49, 50, 51, 52, 53, 54, 55, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 80, 81, 82, 83, 84, 85, 86

Offset

0,2

Comments

a(0)=1, a(1)=3; for n>1, a(n)=a(n-1)+1 if n is already in the sequence, a(n)=a(n-1)+2 otherwise.

Sequence (without first term) is the complement of A000124 (central polygonal numbers). - Jaroslav Krizek, Jun 16 2009

a(n) is the Ramsey core number rc(2,n). The Ramsey core number rc(s,t) is the smallest n such that for all edge 2-colorings of K_n, either the factor induced by the first color contains an s-core or the second factor contains a t-core. (A k-core is a subgraph with minimum degree at least k.) - Allan Bickle, Mar 29 2023

References

R. Klein and J. Schönheim, Decomposition of K_{n} into degenerate graphs, In Combinatorics and Graph Theory Hefei 6-27, April 1992. World Scientific. Singapore, New Jersey, London, Hong Kong, 141-1

Links

G. C. Greubel, Table of n, a(n) for n = 0..1000

Allan Bickle, The k-Cores of a Graph, Ph.D. Dissertation, Western Michigan University, 2010.

Allan Bickle, Structural results on maximal k-degenerate graphs, Discuss. Math. Graph Theory 32 4 (2012), 659-676.

Allan Bickle, A Survey of Maximal k-degenerate Graphs and k-Trees, Theory and Applications of Graphs 0 1 (2024) Article 5.

B. Cloitre, N. J. A. Sloane and M. J. Vandermast, Numerical analogues of Aronson's sequence, J. Integer Seqs., Vol. 6 (2003), #03.2.2.

B. Cloitre, N. J. A. Sloane and M. J. Vandermast, Numerical analogues of Aronson's sequence, arXiv:math/0305308 [math.NT], 2003.

Sascha Stoll, On Subgraphs With Minimum Degree Restrictions, Master’s Thesis, Karlsruhe Institute of Technology, 2019.

Formula

a(n) = A003057(n+1) + n. - Jaroslav Krizek, Jun 16 2009

a(n) = ceiling(n + 1/2 + sqrt(2*(n-1)+9/4)). - Allan Bickle, Mar 29 2023

Example

For order 5, one of the two factors has at least 5 edges, and so contains a cycle.   For order 4, K_4  decomposes into two paths.  Thus rc(2,2)=5.

Mathematica

Table[(n + Round[Sqrt[2 n]] + 1), {n, 0, 80}] (* Vincenzo Librandi, Jan 20 2015 *)

Prog

(PARI) A080036(n)=n+round(sqrt(2*n))+1 \\ M. F. Hasler, Jan 13 2015
(Magma) [n + Round(Sqrt(2*n)) + 1: n in [0..80]]; // Vincenzo Librandi, Jan 20 2015
(Python)
from math import isqrt
def A080036(n): return (k:=isqrt(m:=n<<1))+int((m<<2)>(k<<2)*(k+1)+1)+n+1 # Chai Wah Wu, Jul 26 2022

Crossrefs

Equals A014132 + 1. Cf. A080037.

Different from A105206.

Cf. A361261 (array of rc(s,t)), A361684 (rc(n,n)).

Sequence in context: A175966 A121882 A105206 * A242535 A165290 A307206

Adjacent sequences: A080033 A080034 A080035 * A080037 A080038 A080039

Keyword

nonn

Author

N. J. A. Sloane, Mar 14 2003

Status

approved