C Knuth's power tree construction
C using the algorithm given in TAOCP vol. 2, p. 692
C Answer to exercise 5 for chapter 4.6.3
C Author: Hugo Pfoertner http://www.pfoertner.org
C Change history:
C Dec 17 2005 Initial version
C
      implicit integer (a-z)
      doubleprecision sum
      parameter ( r=26, p2=2**r )
      dimension linku(0:p2), linkr(0:p2), left(0:r)
100   continue
C Initilaize
      do 10 j = 0, p2
      linku(j) = 0
10    continue
      k = 0
      linkr(0) = 1
      linkr(1) = 0
200   continue
C Change level
      n = linkr(0)
      left(k) = n
      if ( k .eq. r ) goto 999
      m = 0
300   continue
C Prepare for n
      q = 0
      s = n
400   continue
C Already in tree
      if ( linku(n+s) .ne. 0 ) goto 600
500   continue
C Insert below n
      if ( q .eq. 0 ) mprime = n + s
      linkr(n+s) = q
      linku(n+s) = n
      q = n + s
600   continue
C Move up
      s = linku(s)
      if ( s .ne. 0 ) goto 400
700   continue
C Attach group
      if ( q .ne. 0 )then
        linkr(m) = q
        m = mprime
      endif
800   continue
C Move n
      n = linkr(n)
      if ( n .ne. 0 ) goto 300
900   continue
C End of level
      linkr(m) = 0
      k = k + 1
      goto 200
999   continue
C Diagnostic output
C      do 990 i = 0, p2
C      if ( linkr(i) .ne. 0 .or. linku(i) .ne. 0 )
C     & write (*,1000) i, linkr(i), linku(i)
1000  format ( 3 i6 )
C990   continue
C
C Count elements in row and compute row sums
      do 910 i = 1, r
      sum = 0.0D0
      count = 0
      next = left(i)
915   continue
      count = count + 1
      sum = sum + dble(next)
      next = linkr(next)
      if ( next .ne. 0 ) goto 915
C last entry in row reached
      write (*,1001) i+1, left(i), count, sum
1001  format ( i3, 2I8, f17.1 )
910   continue
      end