Fibonacci word
You are encouraged to solve this task according to the task description, using any language you may know.
The Fibonacci Word may be created in a manner analogous to the Fibonacci Sequence as described here:
- Define F_Word1 as 1;
- Define F_Word2 as 0;
- Form F_Word3 as F_Word2 concatenated with F_Word1 i.e "01"
- Form F_Wordn as F_Wordn-1 concatenated with F_wordn-2
For this task we shall do this for n = 37. You may display the first few but not the larger values of n, doing so will get me into trouble with them what be (again!).
Instead create a table for F_Words 1 to 37 which shows:
- The number of characters in the word
- The word's Entropy.
Icon and Unicon
The following solution works in both Icon and Unicon. The first eight Fibonacci words are shown, while the Fibonacci word length and Entropy are shown for all 37.
<lang unicon>procedure main(A)
n := integer(A[1]) | 37
write(right("N",4)," ",right("length",15)," ",left("Entrophy",15)," ",
" Fibword")
every w := fword(i := 1 to n) do {
writes(right(i,4)," ",right(*w,15)," ",left(H(w),15))
if i <= 8 then write(": ",w) else write()
}
end
procedure fword(n)
static fcache
initial fcache := table()
/fcache[n] := case n of {
1: "1"
2: "0"
default: fword(n-1)||fword(n-2)
}
return fcache[n]
end
procedure H(s)
P := table(0.0) every P[!s] +:= 1.0/*s every (h := 0.0) -:= P[c := key(P)] * log(P[c],2) return h
end</lang>
Sample run:
->fw N length Entrophy Fibword 1 1 0.0 : 1 2 1 0.0 : 0 3 2 1.0 : 01 4 3 0.9182958340544: 010 5 5 0.9709505944546: 01001 6 8 0.9544340029249: 01001010 7 13 0.9612366047228: 0100101001001 8 21 0.9587118829771: 010010100100101001010 9 34 0.9596868937742 10 55 0.9593160320543 11 89 0.9594579158386 12 144 0.9594037542210 13 233 0.9594244469559 14 377 0.9594165437404 15 610 0.9594195626031 16 987 0.9594184095152 17 1597 0.9594188499578 18 2584 0.9594186817240 19 4181 0.9594187459836 20 6765 0.9594187214387 21 10946 0.9594187308140 22 17711 0.9594187272330 23 28657 0.9594187286009 24 46368 0.9594187280783 25 75025 0.9594187282781 26 121393 0.9594187282015 27 196418 0.9594187282313 28 317811 0.9594187282195 29 514229 0.9594187282251 30 832040 0.9594187282196 31 1346269 0.9594187282169 32 2178309 0.9594187282191 33 3524578 0.9594187282130 34 5702887 0.9594187282322 35 9227465 0.9594187281818 36 14930352 0.9594187282743 37 24157817 0.9594187282928 ->
PARI/GP
<lang parigp>ent(a,b)=[a,b]=[a,b]/(a+b);(a*log(if(a,a,1))+b*log(if(b,b,1)))/log(1/2) allocatemem(75<<20) \\ Allocate 75 MB stack space F=vector(37);F[1]="1";F[2]="0";for(n=3,37,F[n]=Str(F[n-1],F[n-2])) for(n=1,37,print(n" "fibonacci(n)" "ent(fibonacci(n-1),fibonacci(n-2))))</lang>
For those output fascists:
1 1 0.E-9 2 1 0.E-9 3 2 1.00000000 4 3 0.918295834 5 5 0.970950594 6 8 0.954434003 7 13 0.961236604 8 21 0.958711883 9 34 0.959686894 10 55 0.959316032 11 89 0.959457916 12 144 0.959403754 13 233 0.959424447 14 377 0.959416544 15 610 0.959419563 16 987 0.959418409 17 1597 0.959418850 18 2584 0.959418682 19 4181 0.959418746 20 6765 0.959418721 21 10946 0.959418731 22 17711 0.959418727 23 28657 0.959418728 24 46368 0.959418728 25 75025 0.959418728 26 121393 0.959418728 27 196418 0.959418728 28 317811 0.959418728 29 514229 0.959418728 30 832040 0.959418728 31 1346269 0.959418728 32 2178309 0.959418728 33 3524578 0.959418728 34 5702887 0.959418728 35 9227465 0.959418728 36 14930352 0.959418728 37 24157817 0.959418728
Perl 6
Does not work yet with rakudo for rakudo does not recognize * R~ * as priming. It's possible to write -> $a, $b { $b ~ $a } instead but it's kind of verbose.
<lang Perl 6>my @fib-word := 1, 0, * R~ * ... *;
sub entropy {
-log(2) R/
[+] map -> \p { p * log p },
$^string.comb.bag.values »/» $string.chars
} for 1 .. 37 -> $n {
printf "%5d\t%10d\t%.8e\t%s\n", $n, .chars, .&entropy, $n > 10 ?? !! $_ given @fib-word[$n];
}</lang>