A080036 - OEIS

%I #45 Feb 18 2024 02:09:06

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

%T 33,34,35,36,38,39,40,41,42,43,44,45,47,48,49,50,51,52,53,54,55,57,58,

%U 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

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

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

%C Sequence (without first term) is the complement of A000124 (central polygonal numbers). - _Jaroslav Krizek_, Jun 16 2009

%C 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

%D 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

%H G. C. Greubel, <a href="/A080036/b080036.txt">Table of n, a(n) for n = 0..1000</a>

%H Allan Bickle, <a href="https://allanbickle.files.wordpress.com/2016/05/dissertation4.pdf">The k-Cores of a Graph</a>, Ph.D. Dissertation, Western Michigan University, 2010.

%H Allan Bickle, <a href="https://www.dmgt.uz.zgora.pl/publish/pdf.php?doi=1637">Structural results on maximal k-degenerate graphs</a>, Discuss. Math. Graph Theory 32 4 (2012), 659-676.

%H Allan Bickle, <a href="https://doi.org/10.20429/tag.2024.000105">A Survey of Maximal k-degenerate Graphs and k-Trees</a>, Theory and Applications of Graphs 0 1 (2024) Article 5.

%H B. Cloitre, N. J. A. Sloane and M. J. Vandermast, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL6/Cloitre/cloitre2.html">Numerical analogues of Aronson's sequence</a>, J. Integer Seqs., Vol. 6 (2003), #03.2.2.

%H B. Cloitre, N. J. A. Sloane and M. J. Vandermast, <a href="https://arxiv.org/abs/math/0305308">Numerical analogues of Aronson's sequence</a>, arXiv:math/0305308 [math.NT], 2003.

%H Sascha Stoll, <a href="https://limejuicestudio.com/pdf/Final_Master_thesis.pdf">On Subgraphs With Minimum Degree Restrictions</a>, Master’s Thesis, Karlsruhe Institute of Technology, 2019.

%F a(n) = A003057(n+1) + n. - _Jaroslav Krizek_, Jun 16 2009

%F a(n) = ceiling(n + 1/2 + sqrt(2*(n-1)+9/4)). - _Allan Bickle_, Mar 29 2023

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

%t Table[(n + Round[Sqrt[2 n]] + 1), {n, 0, 80}] (* _Vincenzo Librandi_, Jan 20 2015 *)

%o (PARI) A080036(n)=n+round(sqrt(2*n))+1 \\ _M. F. Hasler_, Jan 13 2015

%o (Magma) [n + Round(Sqrt(2*n)) + 1: n in [0..80]]; // _Vincenzo Librandi_, Jan 20 2015

%o (Python)

%o from math import isqrt

%o 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

%Y Equals A014132 + 1. Cf. A080037.

%Y Different from A105206.

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

%K nonn

%O 0,2

%A _N. J. A. Sloane_, Mar 14 2003