[xsl] Primes in consecutive digits in Fibonacci numbers (Re: [xsl] A small programming challenge)

Subject: [xsl] Primes in consecutive digits in Fibonacci numbers (Re: [xsl] A small programming challenge)
From: Dimitre Novatchev <dnovatchev@xxxxxxxxx>
Date: Sun, 22 Jan 2006 12:23:37 +1100
Many months ago I submitted to the xsl list a small programming challenge:

      http://www.biglist.com/lists/xsl-list/archives/200506/msg00848.html

Let me first appologize for the delay in summarizing the solution(s)
-- it's part of me being busy/lazy, part due to unexpected unwelcome
events.

This puzzle was inspired by the less difficult but now famous Google puzzle
    {first 10-digit prime found in consecutive digits of e}.com


   http://www.npr.org/programs/morning/features/2004/sep/googlead/billboard.h
tml

and
   Dan Brown's "The Da Vinci code".


The purpose was to once again show that such problems can be solved
both efficiently and elegantly in XSLT.


As originally stated, the problem was to
       " Find the first 10-digit prime in consecutive digits of F-3000"

The problem consists of two separate sub-problems:

    1. Calculate F-3000

    2. Find the first 10-digit substring that represents a prime number

My initial solution of the first subproblem was to simply use the
wellknown recursive definition of a Fibonacci number:

    F(N+1) = F(N) + F(N-1)

combined with the saxon:memo-function="yes" attribute, which produces
F(N) with O(N) (linear) time complexity.

F-3000 was chosen not by chance -- one cannot calculate F-3000 in
Saxon 8.x using the above formula, because of stack overflow (even big
arithmetic faces the hardware limits of a computer).

However, it was possible to calculate F-3000 with the above method
using Saxon.NET.


Then, in the ensueing thread I wrote:

  "Andrew,
Yes, I have a solution and I know of a better solution, which will run
even faster and will not use any extensions."


At the same time I received a solution from David Carlisle, which used
exactly this faster algorithm.

This exploits a general idea of calculating any function F(N) (not
only the one that produces Fibonacci numbers),  if

  F(2N) and F(2N+1) can be expressed by F(N).

Then, recursively, one calculates F(N), F(N/2), F(N/4),..., F(0) or F(1)

The above sequence has Log2(N) elements and if the calculations from N
to 2N are not very complicated, one may generally expect a time
complexity close to O(log2(N)).

For example, if

     F(M) =  x^M,

then we have:

   F(2M) = F(M)*F(M)

   F(2M+1) = x*F(2M)


and therefore, one can calculate a^N in O(log2(N)) -- much faster than
in linear time.

The corresponding formulas for Fib(N), which both David and I used
(but I derived these formulas without reading them in a textbook) can
be found at:

    http://www.mcs.surrey.ac.uk/Personal/R.Knott/Fibonacci/fibFormula.html#fi
binits


    F(2N)      = F(N) * F(N)  + f(N-1) * F(N-1)

    F(2N+1) = (2F(N-1) + F(N)) * F(N)

Then the algorithm is easy to write, it is fast and efficient and
produces F-3000 in Saxon 8.x without a problem.

The second subproblem is the classic one of determining if a given
number is a prime one.

David is using the little Fermat's theorem to eliminate all numbers
that are not primes.

The little Fermat's theorem states that:

if p is prime, then

               a^(p-1) mod p = 1                                    (1)

So, we can safely conclude that a number N is not prime if

   not(a^(N-1) mod N = 1)

However, from

   a^(N-1) mod N = 1

it still does not follow that N is a prime. For example:

    2^341 - 2 is divisible by 341,

    but 341 is composite: 341 = 31 x 11


What David didn't complete in his solution was that he didn't perform
any additional checks in the case when formula (1) above did hold
(when the sequence of ten consecutive digits was a Fermat's
pseudo-prime).

In this case luckily the first ten consecutive digit
Fermat'spseudo-prime in F-3000 is also the first ten consecutive digit
prome in F-3000.


I conclude this long post by listing below the two solutions: David
Carlisle's and mine.

I want to express my gratitude to David Carlisle for his love of
challenging problems, which has promoted the quality of this mailing
list. I also thank Tommie for her understanding and permitting me to
post this, despite some initial doubts that such posts truly fall into
the subjectmatter of the xsl list.


David Carlisle's solution:

Current Thread