A394869 a(n) = floor(n*(sqrt(n - 1) + 2)/2).

0, 1, 3, 5, 7, 10, 12, 15, 18, 21, 25, 28, 31, 35, 39, 43, 46, 51, 55, 59, 63, 67, 72, 76, 81, 86, 91, 95, 100, 105, 110, 115, 121, 126, 131, 137, 142, 148, 153, 159, 164, 170, 176, 182, 188, 194, 200, 206, 212, 218, 225, 231, 237, 244, 250, 257, 263, 270, 276, 283, 290

Offset

0,3

Comments

a(n) is the sharp upper bound of the number of edges in a graph of n vertices that does not contain a cycle of length 4.

References

Miklos Bona, Introduction to Enumerative and Analytic Combinatorics, CRC Press, 2025, pp. 334-336.

Links

Table of n, a(n) for n=0..60.

Mathematica

a[n_]:=Floor[n(Sqrt[n-1]+2)/2]; Array[a, 61, 0]

Prog

(Python)
from math import isqrt
def A394869(n): return n+(isqrt(n**2*(n-1))>>1) # Chai Wah Wu, Apr 06 2026

Crossrefs

Cf. A334563.

Sequence in context: A182136 A335408 A211266 * A378365 A037030 A277719

Adjacent sequences: A394866 A394867 A394868 * A394870 A394871 A394872

Keyword

nonn,easy

Author

Stefano Spezia, Apr 05 2026

Status

approved