J-ottings 33: How to Tell a Fib in lots of Different Ways
Vector 19:1, page 41
Transcribed from the printed issue; not yet reviewed. Read it in the PDF of the issue, page 41
Michel Dumontier’s article in Vector vol. 18 on the "beastly number" 666 came as quite a Revelation to me, but I suppose that was always the way it was intended to be! The Fibonacci series and its squares are a bit like it in that once you start looking for them, they turn up all over the place! The Fibonacci series is well known for its application in models of natural phenomena like the arrangement of sunflower seed-heads, and the population growth of rabbit colonies. Readers no doubt know well how this series is extended by concatenating the sum of the last two items, which is an imperfect way of saying in English what a fully accurate description in J says a few lines below
Assigning the first fourteen terms to a variable f is sufficient to observe the evolving patterns. Because this defines only a finite part of the series there will be end effects in the series derived from it. These could be eliminated by topping and tailing, but as this usually serves only to obscure what is important, please just ignore these.
f=.(,+/@(_2&{.))^:12(0 1)
0 1 1 2 3 5 8 13 21 34 55 89 144 233
f^2 NB. Fibonacci squares
0 1 1 4 9 25 64 169 441 1156 3025 7921 20736 54289
Incrementing the cumulative sums and differences still leaves us in Fibonacci-land :
>:+/\f NB. same as 2|.f
1 2 3 5 8 13 21 34 55 89 144 233 377 610
>:-/\f NB. _2|.f, has alternating signs
1 0 1 _1 2 _3 5 _8 13 _21 34 _55 89 _144 0,
Multiplying terms of f which are neighbours but one :
gives a series which differs by 1 in alternating directions from f^2.
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 :
and the Fibonacci trade mark is still present in the following :
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
You can even generate the Fibonacci series using long division :
Then try %998999 and do the long division (it isn’t hard!) – you’ll soon see how it works.
The products of pairs of consecutive items in the Fibonacci series generate the series :
which is the same as :
Cumulating sums of adjacent product pairs of ppf brings us back to f :
Subtract successive products in pairs to get the odds, which are also the squares of f :
The cumulative series of ppf is :
odd and even subsets of whose items turn up in:
ev^2 NB. squares of even values
0 1 9 64 441 3025 20736
1 0 sel(*2&|.)f NB. prods of pairs one apart in f
0 3 24 168 1155 7920 0
What happens when three or more successive items in f are cumulated ? :
-: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 NB. 2|.Lucas numbers
(The Lucas series is what the Fibonnaci series becomes if you start with 1 3:
)
Now replace + with - :
|>:-/\f NB. _1|f
1 0 1 1 2 3 5 8 13 21 34 55 89 144
|2-/\f NB. also _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
2 1 3 4 7 11 18 29 47 76 123
Selecting and cumulating every third term leads to :
which should be compared with
Fibonacci numbers have an intimate relationship with binomial coefficients as diagonal addition (+//.) on the Pascal triangle demonstrates :
If Pythagoras happens to be your t(r)ipple, try
p=.1}.2*ppf NB. 2 f(n+1).f(n+2)
q=.f*3|.f NB. f(n).f(n+3)
r=.1}.2+/\f^2 NB. (f(n+1))^2 +(f(n+2))^2
p,q,:r NB. Every col. is a Pythgn. triple
2 4 12 30 80 208 546 1428 3740 9790 25632 67104 0 0
0 3 5 16 39 105 272 715 1869 4896 12815 0 144 233
2 5 13 34 89 233 610 1597 4181 10946 28657 75025 0 0
Fibonacci numbers have a closed form which uses the solution of the quadratic equation \(1 + x - x^2 = 0\) :
An expression known as Binet’s formula gives the nth. Fibonacci number as \(\dfrac{1}{\sqrt{5}}(\phi^n - \varphi^n)\) where \(\phi\) and \(\varphi\) are the items of gs, and so the Fibonacci numbers are given formulaically as :
or equivalently, since the larger root (gm=.-:>:%:5) in gs rapidly dominates :
rnd=.<.@(0.5&+) NB. round to nearest integer
rnd (gm^i.15)%%:5
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377
A closed form also allows the generation of large Fibonacci numbers :
for which Roger Hui demonstrated another method (although not a closed form), viz.
The selection verb can also be used to demonstrate various divisibility properties of f, for example that even Fibonacci numbers have indices divisible by 3, all the others are odd :
This can be extended by generalizing the selection verb to provide complementary selections, e.g. to provide masks for integers in i.4 which are/are not divisible by 4 :
In the next three cases, post-edited comments show the properties of the numbers in the various pairs of boxes :
(dpsel 4)sel&.><f
+----------+-------------------------+
|0 3 21 144|1 1 2 5 8 13 34 55 89 233|NB.div/not div by 3
+----------+-------------------------+
(dpsel 5)sel&.><f
+------+------------------------------+
|0 5 55|1 1 2 3 8 13 21 34 89 144 233|NB.div/not div by 5
+------+------------------------------+
(dpsel 6)sel&.><f
+-------+----------------------------+
|0 8 144|1 1 2 3 5 13 21 34 55 89 233|NB.div/not div by 8
+-------+----------------------------+
All Fibonacci numbers which are divisible by 17 are even which is corroborated by :
Continued fractions starting with 1, 1+1/1 are the result of cumulating the verb +% :
and converge rapidly to the golden mean. Applying rational arithmetic using x: gives :
Multiplying by f keeps us marching on the Fibonacci spot (well, more or less!) :
This also gives a convenient way to obtain some rather large Fibonacci numbers. The denominator has been edited out of the following display in order to show the 250th. Fibonacci number :
No wonder there are a lot of rabbits about!