Fifty Shades of J/Chapter 42
Table of Contents ... Glossary ... Previous Chapter ... Next Chapter
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 (*1&|.)f NB. multiply adjacent terms 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 2+/\2*/\f NB. add adj product pairs 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