Let f be a uniformly-randomly chosen mapping from the numbers 1..N to the numbers 1..N (note: not necessarily a permutation of 1..N; the mapping could produce a number in more than one way or not at all). At some point, the sequence 1, f(1), f(f(1))... will contain a repetition, a number that occurring for the second time in the sequence.



Task

Write a program or a script that estimates, for each N, the average length until the first such repetition.

Also calculate this expected length using an analytical formula, and optionally compare the simulated result with the theoretical one.



This problem comes from the end of Donald Knuth's Christmas tree lecture 2011.

Example of expected output:

 N    average    analytical    (error)
===  =========  ============  =========
  1     1.0000        1.0000  (  0.00%)
  2     1.4992        1.5000  (  0.05%)
  3     1.8784        1.8889  (  0.56%)
  4     2.2316        2.2188  (  0.58%)
  5     2.4982        2.5104  (  0.49%)
  6     2.7897        2.7747  (  0.54%)
  7     3.0153        3.0181  (  0.09%)
  8     3.2429        3.2450  (  0.07%)
  9     3.4536        3.4583  (  0.14%)
 10     3.6649        3.6602  (  0.13%)
 11     3.8091        3.8524  (  1.12%)
 12     3.9986        4.0361  (  0.93%)
 13     4.2074        4.2123  (  0.12%)
 14     4.3711        4.3820  (  0.25%)
 15     4.5275        4.5458  (  0.40%)
 16     4.6755        4.7043  (  0.61%)
 17     4.8877        4.8579  (  0.61%)
 18     4.9951        5.0071  (  0.24%)
 19     5.1312        5.1522  (  0.41%)
 20     5.2699        5.2936  (  0.45%)


 
function Get-AnalyticalLoopAverage ( [int]$N )
    {
    #  Expected loop average = sum from i = 1 to N of N! / (N-i)! / N^(N-i+1)
    #  Equivalently, Expected loop average = sum from i = 1 to N of F(i)
    #    where F(N) = 1, and F(i) = F(i+1)*i/N
 
    $LoopAverage = $Fi = 1
 
    If ( $N -eq 1 ) { return $LoopAverage }
 
    ForEach ( $i in ($N-1)..1 )
        {
        $Fi *= $i / $N
        $LoopAverage  += $Fi
        }
    return $LoopAverage
    }
 
function Get-ExperimentalLoopAverage ( [int]$N, [int]$Tests = 100000 )
    {
    If ( $N -eq 1 ) { return 1 }
 
    #  Using 0 through N-1 instead of 1 through N for speed and simplicity
    $NMO = $N - 1
 
    #  Create array to hold mapping function
    $F = New-Object int[] ( $N )
 
    $Count = 0
    $Random = New-Object System.Random
 
    ForEach ( $Test in 1..$Tests )
        {
        #  Map each number to a random number
        ForEach ( $i in 0..$NMO )
            {
            $F[$i] = $Random.Next( $N )
            }
 
        #  For each number...
        ForEach ( $i in 0..$NMO )
            {
            #  Add the number to the list
            $List = @()
            $Count++
            $List += $X = $i
 
            #  If loop does not yet exist in list...
            While ( $F[$X] -notin $List )
                {
                #  Go to the next mapped number and add it to the list
                $Count++
                $List += $X = $F[$X]
                }
            }
        }
    $LoopAvereage = $Count / $N / $Tests
    return $LoopAvereage
    }
 