login
A346915
Decimal expansion of the limit as N->oo of the mean number of mems per forest taken by Knuth's algorithm O when generating the rooted forests of N vertices.
3
3, 5, 3, 3, 9, 2, 6, 3, 9, 8, 0, 2, 3, 7, 2, 1, 7, 9, 6, 9, 1, 5, 9, 9, 9, 7, 5, 6, 9, 0, 0, 2, 7, 2, 7, 8, 4, 5, 1, 0, 8, 6, 7, 6, 0, 3, 2, 5, 7, 3, 7, 7, 2, 9, 1, 8, 0, 6, 7, 3, 4, 5, 8, 9, 4, 6, 0, 3, 4, 1, 2, 0, 6, 2, 1, 8, 6, 9, 2, 4, 9, 4, 1, 9, 7, 5, 0, 7, 7, 2, 5, 1, 2, 6, 3, 1, 2, 7, 2, 8, 7, 3, 0, 5, 5
OFFSET
1,1
COMMENTS
Knuth volume 4A section 7.2.1.6 algorithm O adapts the rooted tree iteration algorithm of Beyer and Hedetniemi (A346913) to become a forests iteration in vertex parent array form (A346914).
Knuth's exercise 88 is to count mems (memory reads + memory writes) in algorithm O. Per Knuth's answer, the present constant is 2 + 3/(d-1) where d=A051491 is the growth power of rooted trees (and forests).
Also equals 3*S+2 where S=A346916 is the (limit) mean number of singletons in a rooted forest. The mems are S reads to find the end-most vertex k which is not a singleton, then S+1 reads and S+1 writes to change k and the singletons to subtree copies. Finding k examines S+1 array entries, but the algorithm holds the final p[N] in a register as well as in memory so no mem to examine it.
LINKS
Donald E. Knuth, The Art of Computer Programming, Volume 4A, Combinatorial Algorithms, Part 1, section 7.2.1.6, exercise 88. Also in Pre-Fascicle 4A, Draft of Section 7.2.1.6, Generating All Trees algorithm O page 22, exercise 88 page 40, and answer page 66.
FORMULA
Equals 2 + 3/(A051491 - 1). [Knuth]
Equals 3*A346916 + 2.
EXAMPLE
3.533926398023721796915999756900272...
CROSSREFS
Cf. A051491 (rooted tree growth), A346916 (mean singletons per forest).
Cf. A346913 (levels iteration), A346914 (vpar iteration).
Sequence in context: A097519 A133773 A327555 * A077934 A077950 A077973
KEYWORD
nonn,cons
AUTHOR
Kevin Ryde, Aug 07 2021
STATUS
approved