# Fibonacci word

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>