A343980 Decimal expansion of the expected length of the first cycle in an evolving graph with n vertices rescaled by n^(-1/6).

2, 0, 3, 3, 6, 9, 2, 0, 1, 4, 0, 6, 3, 8, 9, 8, 9, 9, 9, 1, 6, 5, 4, 7, 7, 2, 3, 8, 6, 2, 0, 1, 0, 6, 3, 9, 6, 2, 6, 6, 1, 8, 1, 2, 5, 2, 3, 1, 5, 3, 3, 7, 0, 2, 2, 4, 3, 0, 2, 6, 1

Offset

1,1

Comments

The first cycle in an evolving graph with n vertices has size K n^(1/6) + O(n^(3/22)) on the average with K given by a double integral (see the formula below).

In "The first cycles in an evolving graph" by Philippe Flajolet, Boris Pittel and Donald E. Knuth, the constant K is estimated as 2.0337 using a tedious computation at the end of the paper: one part of the integral is estimated numerically, and the complement is represented as divergent series for which an optimal truncation rule is used. Their techniques can be used to obtain more digits of this constant using interval arithmetic.

Links

Table of n, a(n) for n=1..61.

S. Dovgal, Supplementary material for Section 1 of the paper "The birth of the strong components".

P. Flajolet, D. E. Knuth, and B. Pittel, The first cycles in an evolving graph, Discrete Mathematics, 75(1-3):167-215, 1989.

Formula

K = 1/(sqrt(8*Pi)*i) Integral_{m=-oo..oo} Integral_{s=1-i*oo..1+i*oo} e^((m+2s) * (m-s)^2/6)/s ds dm.

Example

2.033692014063898999165477238620106396266181252315337022430261...

Prog

(Python) See Dovgal link

Crossrefs

Sequence in context: A247508 A112239 A298814 * A021835 A112476 A370724

Adjacent sequences: A343977 A343978 A343979 * A343981 A343982 A343983

Keyword

nonn,cons,more

Author

Sergey Dovgal, May 06 2021

Status

approved