cp's OEIS Frontend

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.

%I A346915 #11 Sep 02 2021 05:43:03
%S A346915 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,
%T A346915 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,
%U A346915 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
%N 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.
%C A346915 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).
%C A346915 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).
%C A346915 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.
%H A346915 Kevin Ryde, <a href="/A346915/b346915.txt">Table of n, a(n) for n = 1..1799</a>
%H A346915 Donald E. Knuth, <a href="http://www-cs-faculty.stanford.edu/~knuth/taocp.html">The Art of Computer Programming</a>, Volume 4A, Combinatorial Algorithms, Part 1, section 7.2.1.6, exercise 88.  Also in <a href="http://www-cs-faculty.stanford.edu/~knuth/fasc4a.ps.gz">Pre-Fascicle 4A, Draft of Section 7.2.1.6, Generating All Trees</a> algorithm O page 22, exercise 88 page 40, and answer page 66.
%F A346915 Equals 2 + 3/(A051491 - 1). [Knuth]
%F A346915 Equals 3*A346916 + 2.
%e A346915 3.533926398023721796915999756900272...
%Y A346915 Cf. A051491 (rooted tree growth), A346916 (mean singletons per forest).
%Y A346915 Cf. A346913 (levels iteration), A346914 (vpar iteration).
%K A346915 nonn,cons
%O A346915 1,1
%A A346915 _Kevin Ryde_, Aug 07 2021