# Fifty Shades of J/Chapter 42

Fifty ways to tell a fib

### Principal Topics

^: (power conjunction), β (rank conjunction  (prefix / infix) /. (oblique) ~ (passive / reflex) Fibonacci numbers, Lucas numbers, binomial coefficients, Pascal triangle, Binet formula, continued fractions.

The Fibonacci series is a bit like fly-paper or goose-grass, once it begins sticking to you, it is terribly hard to get rid of it. I will start by defining the first 14 terms which should be enough to observe the patterns which evolve. (Note : because I am treating only a finite part of the series there will be end effects which could be resolved by topping and tailing, but this usually serves only to obscure what is important, so please just ignore end effects.)

```   f=.(,+/@(_2&{.))^:12(0 1)
0 1 1 2 3 5 8 13 21 34 55 89 144 233```

Incrementing the cumulative sums and differences still leaves us in Fibonacci-land :

```   >:+/\f            NB. 2|.f
1 2 3 5 8 13 21 34 55 89 144 233 377 610
>:-/\f            NB. alternating differences(6)
1 0 1 _1 2 _3 5 _8 13 _21 34 _55 89 _144```

Here is a selector verb which takes a binary pattern as left argument and extends it as a mask for the right argument. Its first use is to select odd and even items in f :

```   sel=.(\$~#)#]
]od=.0 1 sel f             NB. odd items in f
1 2 5 13 34 89 233
]ev=.1 0 sel f             NB. even items in f
0 1 3 8 21 55 144```

Cumulating either odds or evens leads to the other :

```   +/\od                      NB. 1|.ev    (4)
1 3 8 21 55 144 377
>:+/\ev                    NB. 1|.od    (5)
1 2 5 13 34 89 233```

and the Fibonacci trade mark is still there if we do the following :

```   +/\*:f                     NB. scan the squares of f (9)
0 1 2 6 15 40 104 273 714 1870 4895 12816 33552 87841
0 1 2 6 15 40 104 273 714 1870 4895 12816 33552 0
2+/\f                      NB. result is 2|.f
1 2 3 5 8 13 21 34 55 89 144 233 377
2-~/\f
1 0 1 1 2 3 5 8 13 21 34 55 89
_2+/\f                     NB. same as }.ev
1 3 8 21 55 144 377
2*/\f                      NB. products in pairs
0 1 2 6 15 40 104 273 714 1870 4895 12816 33552
+/\2*/\f                   NB. cum sums of prods in pairs
0 1 3 9 24 64 168 441 1155 3025 7920 20736 54288```

The product pairs of consecutive items in the Fibonacci series generate another derived series with some interest in its own right :

```   2*/\ f
0 1 2 6 15 40 104 273 714 1870 4895 12816 33552```

Its cumulative series is :

```   ]cpp=.+/\2*/\f             NB. cum product pairs
0 1 3 9 24 64 168 441 1155 3025 7920 20736 54288```

Compare :

```   0 1 sel cpp                NB. odd items in ccp
1 9 64 441 3025 20736
ev^2
0 1 9 64 441 3025 20736
1 0 sel cpp                NB. even items in cpp
0 3 24 168 1155 7920 54288
1 0 sel(*2&|.)f            NB. prods of pairs but one
0 3 24 168 1155 7920 0
1 3 8 21 55 144 377 987 2584 6765 17711 46368
(2*/\f)+1|.2*/\f           NB. 1|.ev   (as above)
1 3 8 21 55 144 377 987 2584 6765 17711 46368 33552```

At this point switch to a lesson in J style :

```   ((+ 1&|.)@(2&(*/\)))f      NB. better style for above
1 3 8 21 55 144 377 987 2584 6765 17711 46368 33552
pp=.2&(*/\)                NB. third version
((+1&|.)@pp)f
1 3 8 21 55 144 377 987 2584 6765 17711 46368 33552```

Add products in pairs and you get the evens

```   1 |.ev
1 3 8 21 55 144 0```

Subtract successive products in pairs and you get the odds which are also the squares of f :

```   2-~/\2*/\f                 NB. cf.0 1 sel+/\2*/\f
1 1 4 9 25 64 169 441 1156 3025 7921 20736```

What about successive sums of three or more ? :

```   -:3+/\f               NB. 2|.f
1 2 3 5 8 13 21 34 55 89 144 233
4+/\f
4 7 11 18 29 47 76 123 199 322 521```

These numbers which arise from applying the Fibonacci rule starting with 1 3 are known as the Lucas numbers, and are generated directly by

```   ]l=.(,+/@(_2&{.))^:12(1 3)  NB. Lucas numbers
1 3 4 7 11 18 29 47 76 123 199 322 521 843
|>:-/\f                     NB. _1|.f
1 0 1 1 2 3 5 8 13 21 34 55 89 144
|2-/\f                      NB. _1|.f
1 0 1 1 2 3 5 8 13 21 34 55 89
-:3-/\f                     NB. f
0 1 1 2 3 5 8 13 21 34 55 89
|4-/\f                      NB. _1|.Lucas nos.
2 1 3 4 7 11 18 29 47 76 123
}.*:f                       NB. f squared
1 1 4 9 25 64 169 441 1156 3025 7921 20736 54289
(*2&|.)f                    NB. f * 2|.f
0 2 3 10 24 65 168 442 1155 3026 7920 20737 0 233```
```   v1=.1&|.@:*:                NB. shift squares
v1 f
1 1 4 9 25 64 169 441 1156 3025 7921 20736 54289 0
v2=.*2&|.                   NB. prods next but one (hook)
v2 f
0 2 3 10 24 65 168 442 1155 3026 7920 20737 0 233
(v1-v2)f                    NB. differences
1 _1 1 _1 1 _1 1 _1 1 _1 1 _1 54289 _233

+//.!/~i.10 NB. oblique sums of Pascal tri.
1 1 2 3 5 8 13 21 34 55 88 133 176 189 155 92 37 9 1

+/\0 0 1 sel f              NB. cum sum of 3rd 6th, 9th β¦
1 6 27 116
-:<:0 1 0 sel f             NB. half of u sub(3n+2) β1
0 1 6 27 116```

### Relationship with binomial coefficients

```   +//.(!/~)i.10
1 1 2 3 5 8 13 21 34 55 88 133 176 189 155 92 37 9 1```

As an aside the following gives the first four Pascal triangles as a rank 3 array :

```   a=.(!/~)\i.4
+/"2 a NB. add cols of successive Pascal tria.
1 0 0 0
1 2 0 0
1 2 4 0
1 2 4 8
]gs=.(1&{::@p.)1 1 _1    NB. Binetββs formula
1.61803 _0.618034
*/gs
_1
]c=.0 1%.1,:gs            NB. solve for closed form
0.447214 _0.447214
+/"1 c *"1(<gs)^&> i.12
1.11022e_16 1 1 2 3 5 8 13 21 34 55 89```

or equivalently, because the larger root rapidly dominates :

```   rnd=.<.@(0.5&+)
rnd(({.gs)^i.15)%%:5
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377```

It also allows the generation of indefinitely large Fibonacci numbers :

```   (9!:11)16
c +/ .*gs^78
8944394323791464```

### Divisibility properties :

Demonstration that even Fibonacci numbers have indices divisible by 3, all the others are odd :

```   1 0 0 sel f
0 2 8 34 144
0 1 1 sel f
1 1 3 5 13 21 55 89 233```

This can be extended by generalising the selection verb to provide complementary selections :

```   dpsel=.(0&=;0&~:)@:i.
dpsel 4
βββββββββ¬ββββββββ
β1 0 0 0β0 1 1 1β
βββββββββ΄ββββββββ
(dpsel 4)sel&.><f
ββββββββββββ¬ββββββββββββββββββββββββββ
β0 3 21 144β1 1 2 5 8 13 34 55 89 233β
ββββββββββββ΄ββββββββββββββββββββββββββ
(dpsel 5)sel&.><f
ββββββββ¬ββββββββββββββββββββββββββββββ
β0 5 55β1 1 2 3 8 13 21 34 89 144 233β
ββββββββ΄ββββββββββββββββββββββββββββββ
(dpsel 6)sel&.><f
βββββββββ¬βββββββββββββββββββββββββββββ
β0 8 144β1 1 2 3 5 13 21 34 55 89 233β
βββββββββ΄βββββββββββββββββββββββββββββ
F=.(,+/@(_2&{.))^:60(0 1)
17((=&0@:|)#])F
0 34 2584 196418 14930352 1134903170 86267571272```

### Continued fractions

Continued fractions are defined by

```   cf=.1&+@%
cf^:(i.11)1
1 2 1.5 1.666666666666667 1.6 1.625 1.615384615384615 1.619047619047619 1.617647058823529 1.618181818181818 1.617977528089888
```

The relationship to the Fibonacci numbers should be clear from

```   (}.f)*cf^:(i.13)1
1 2 3 5 8 13 21 34 55 89 144 233 377```

### Code Summary

```f=: (,+/@(_2&{.))^:12(0 1)    NB. first 12 Fib numbers
l=:(,+/@(_2&{.))^:12(1 3)     NB. Lucas numbers
F=.(,+/@(_2&{.))^:60(0 1)
od=: 0 1 sel f                NB. odd items in f
ev=: 1 0 sel f                NB. even items in f
sel=: (\$~#)#]
cpp=: +/\2*/\f                NB. cum product pairs
pp=: 2&(*/\)                  NB. product pairs
gs=: (1&{::@p.)1 1 _1         NB. Binetββs formula
rnd=: <.@(0.5&+)              NB. round to integer
dpsel=: (0&=;0&~:)@:i.        NB. complementary selections
cf=: 1&+@%                    NB. continued fractions
```