Fibo, nacci, Fibonacci, nacciFibonacci, FibonaccinacciFibonacci ...

Musings

There isn't any guidance in these challenges as to whether we are looking for the solution which is:

• shortest
• most efficient
• most readable (which probably means most maintainable)
• most interesting
• etc

My preference is to prioritise 'most readable' with a nod to 'most efficient'.  I do that because most of the software I've written over the last 50 years will have to be maintained by someone - maybe me, often someone else - and it helps them if they can see what I've done and why.

Of course, 50 years ago performance was a big issue. Some of the work I did as a student and later a research scientist in the 1960s and 70s required hours of computer time. Optimisation of code - sometimes involving writing functions in assembly language - was essential.  Today, my phone has more computing power and vastly more memory than the mainframes I used back then so those measures are usually less necessary.

But old habits die hard.  In today's second task I wrote two nested loops with the inner one using the square of a number generated in the outer one. Version 1 had the squaring done in the inner loop - wasteful because it was squaring the same number multiple times. So version 2 had the square calculated in the outer loop. We were asked to find answers up to 500: I tried both my versions up to a million and even on my little Raspberry Pi both versions completed in less than a second.

Task 1: Fibonacci words

This is a good example of a task where efficiency isn't an issue. You can probably generate a Fibonacci series up to the point where you run out of memory in milliseconds, and in fact we only need 4 more terms to reach the 51 character length requested.

Even giving my vanilla algorithm two starting strings which are 1 character long, and asking for the first term with 1000 characters you only need 14 terms beyond the two given ones.

And I could do the task as stated on paper in under 20 seconds!

Task 2: Square-free integers

This is going to be one of those tasks where someone will have a quick solution using number theory, someone else will tell us there's a Perl module to do it, and we'll probably see a few one-line answers as well.

Mine is none of these. I modified the method of my good friend Eratosthenes to say:

• Let's assume all numbers are square free
• Then strike out those that are multiples of squares

A little thought allows a little optimisation of the striking out:

• We only need to consider squares of numbers up to the square root of the limit (500)
• We only need to consider squares of numbers that might themselves be square free

But again, the optimisation makes no discernable difference even if we extend the limit to a million.