Fibonacci word

constant @fib-word = 1, 0, { $^b ~ $^a } ... *;
 
sub entropy {
    -log(2) R/
        [+] map -> \p { p * log p },
            $^string.comb.Bag.values »/» $string.chars
}
for @fib-word[^37] {
    printf "%5d\t%10d\t%.8e\t%s\n",
    (state $n)++, .chars, .&entropy, $n > 10 ?? '' !! $_;
}

That works, but is terribly slow due to all the string processing and bag creation, just to count 0's and 1's. By contrast, the following prints the table up to 100 almost instantly by tracking the values to calculate entropy in parallel with the actual strings. This works in Raku because lazy lists are calculated on demand, so if we don't actually ask for the larger string forms, we don't calculate them. Which would be relatively difficult for a string containing 573147844013817084101 characters, unless you happen to have a computer with a zettabyte or so of memory sitting in your garage.

constant @fib-word = '1', '0', { $^b ~ $^a } ... *;
constant @fib-ones = 1, 0, * + * ... *;
constant @fib-chrs = 1, 1, * + * ... *;
 
multi entropy(0) { 0 }
multi entropy(1) { 0 }
multi entropy($n) {
    my $chars = @fib-chrs[$n];
    my $ones  = @fib-ones[$n];
    my $zeros = $chars - $ones;
    -log(2) R/
        [+] map -> \p { p * log p },
            $ones / $chars, $zeros / $chars
}

for 0..100 -> $n {
    printf "%5d\t%21d\t%.15e\t%s\n",
	    $n, @fib-chrs[$n], entropy($n), $n > 9 ?? '' !! @fib-word[$n];
}

Output:

    0                       1   0.000000000000000e+00   1
    1                       1   0.000000000000000e+00   0
    2                       2   1.000000000000000e+00   01
    3                       3   9.182958340544895e-01   010
    4                       5   9.709505944546688e-01   01001
    5                       8   9.544340029249650e-01   01001010
    6                      13   9.612366047228759e-01   0100101001001
    7                      21   9.587118829771317e-01   010010100100101001010
    8                      34   9.596868937742167e-01   0100101001001010010100100101001001
    9                      55   9.593160320543776e-01   0100101001001010010100100101001001010010100100101001010
   10                      89   9.594579158386695e-01   
   11                     144   9.594037542210229e-01   
   12                     233   9.594244469559866e-01   
   13                     377   9.594165437404406e-01   
   14                     610   9.594195626031441e-01   
   15                     987   9.594184095152244e-01   
   16                    1597   9.594188499578099e-01   
   17                    2584   9.594186817240321e-01   
   18                    4181   9.594187459836640e-01   
   19                    6765   9.594187214386754e-01   
   20                   10946   9.594187308140276e-01   
   21                   17711   9.594187272329618e-01   
   22                   28657   9.594187286008074e-01   
   23                   46368   9.594187280783370e-01   
   24                   75025   9.594187282779029e-01   
   25                  121393   9.594187282016755e-01   
   26                  196418   9.594187282307919e-01   
   27                  317811   9.594187282196701e-01   
   28                  514229   9.594187282239183e-01   
   29                  832040   9.594187282222958e-01   
   30                 1346269   9.594187282229156e-01   
   31                 2178309   9.594187282226789e-01   
   32                 3524578   9.594187282227692e-01   
   33                 5702887   9.594187282227345e-01   
   34                 9227465   9.594187282227477e-01   
   35                14930352   9.594187282227427e-01   
   36                24157817   9.594187282227447e-01   
   37                39088169   9.594187282227441e-01   
   38                63245986   9.594187282227441e-01   
   39               102334155   9.594187282227441e-01   
   40               165580141   9.594187282227441e-01   
   41               267914296   9.594187282227441e-01   
   42               433494437   9.594187282227441e-01   
   43               701408733   9.594187282227441e-01   
   44              1134903170   9.594187282227441e-01   
   45              1836311903   9.594187282227441e-01   
   46              2971215073   9.594187282227441e-01   
   47              4807526976   9.594187282227441e-01   
   48              7778742049   9.594187282227441e-01   
   49             12586269025   9.594187282227441e-01   
   50             20365011074   9.594187282227441e-01   
   51             32951280099   9.594187282227441e-01   
   52             53316291173   9.594187282227441e-01   
   53             86267571272   9.594187282227441e-01   
   54            139583862445   9.594187282227441e-01   
   55            225851433717   9.594187282227441e-01   
   56            365435296162   9.594187282227441e-01   
   57            591286729879   9.594187282227441e-01   
   58            956722026041   9.594187282227441e-01   
   59           1548008755920   9.594187282227441e-01   
   60           2504730781961   9.594187282227441e-01   
   61           4052739537881   9.594187282227441e-01   
   62           6557470319842   9.594187282227441e-01   
   63          10610209857723   9.594187282227441e-01   
   64          17167680177565   9.594187282227441e-01   
   65          27777890035288   9.594187282227441e-01   
   66          44945570212853   9.594187282227441e-01   
   67          72723460248141   9.594187282227441e-01   
   68         117669030460994   9.594187282227441e-01   
   69         190392490709135   9.594187282227441e-01   
   70         308061521170129   9.594187282227441e-01   
   71         498454011879264   9.594187282227441e-01   
   72         806515533049393   9.594187282227441e-01   
   73        1304969544928657   9.594187282227441e-01   
   74        2111485077978050   9.594187282227441e-01   
   75        3416454622906707   9.594187282227441e-01   
   76        5527939700884757   9.594187282227441e-01   
   77        8944394323791464   9.594187282227441e-01   
   78       14472334024676221   9.594187282227441e-01   
   79       23416728348467685   9.594187282227441e-01   
   80       37889062373143906   9.594187282227441e-01   
   81       61305790721611591   9.594187282227441e-01   
   82       99194853094755497   9.594187282227441e-01   
   83      160500643816367088   9.594187282227441e-01   
   84      259695496911122585   9.594187282227441e-01   
   85      420196140727489673   9.594187282227441e-01   
   86      679891637638612258   9.594187282227441e-01   
   87     1100087778366101931   9.594187282227441e-01   
   88     1779979416004714189   9.594187282227441e-01   
   89     2880067194370816120   9.594187282227441e-01   
   90     4660046610375530309   9.594187282227441e-01   
   91     7540113804746346429   9.594187282227441e-01   
   92    12200160415121876738   9.594187282227441e-01   
   93    19740274219868223167   9.594187282227441e-01   
   94    31940434634990099905   9.594187282227441e-01   
   95    51680708854858323072   9.594187282227441e-01   
   96    83621143489848422977   9.594187282227441e-01   
   97   135301852344706746049   9.594187282227441e-01   
   98   218922995834555169026   9.594187282227441e-01   
   99   354224848179261915075   9.594187282227441e-01   
  100   573147844013817084101   9.594187282227441e-01

Last updated