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%)


with Ada.Text_IO; use Ada.Text_IO;
with Ada.Numerics.Generic_Elementary_Functions;
with Ada.Numerics.Discrete_Random;
procedure Avglen is
   package IIO is new Ada.Text_IO.Integer_IO (Positive); use IIO;
   package LFIO is new Ada.Text_IO.Float_IO (Long_Float); use LFIO;
   subtype FactN is Natural range 0..20;
   TESTS : constant Natural := 1_000_000;
 
   function Factorial (N : FactN) return Long_Float is
      Result : Long_Float := 1.0;
   begin
      for I in 2..N loop Result := Result * Long_Float(I); end loop;
      return Result;
   end Factorial;
 
   function Analytical (N : FactN) return Long_Float is
      Sum : Long_Float := 0.0;
   begin
      for I in 1..N loop
         Sum := Sum + Factorial(N) / Factorial(N - I) / Long_Float(N)**I;
      end loop;
      return Sum;
   end Analytical;
 
   function Experimental (N : FactN) return Long_Float is
      subtype RandInt is Natural range 1..N;
      package Random is new Ada.Numerics.Discrete_Random(RandInt);
      seed : Random.Generator;
      Num : RandInt;
      count : Natural := 0;
      bits : array(RandInt'Range) of Boolean;
   begin
      Random.Reset(seed);
      for run in 1..TESTS loop
         bits := (others  => false);
         for I in RandInt'Range loop
            Num := Random.Random(seed); exit when bits(Num);
            bits(Num) := True; count := count + 1;
         end loop;
      end loop;   
      return Long_Float(count)/Long_Float(TESTS);
   end Experimental;
 
   A, E, err : Long_Float;
begin
   Put_Line(" N  avg    calc   %diff");
   for I in 1..20 loop
      A := Analytical(I);  E := Experimental(I); err := abs(E-A)/A*100.0;
      Put(I, Width=>2); Put(E ,Aft=>4, exp=>0); Put(A, Aft=>4, exp=>0);
      Put(err, Fore=>3, Aft=>3, exp=>0); New_line;
   end loop;
end Avglen;