cp's OEIS Frontend

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.