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
Kevin Ryde, Table of n, a(n) for n = 1..1799
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.
EXAMPLE
3.533926398023721796915999756900272...
CROSSREFS
KEYWORD
nonn,cons
AUTHOR
Kevin Ryde, Aug 07 2021
STATUS
approved