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 |
---|
|
<- Previous | Index | Next -> |
---|---|---|
Re: [xsl] Unable to get text() of n, Geert Josten | Thread | [xsl] Calculate average value recur, Weiran Zhang |
Re: [xsl] Unable to get text() of n, Andrew Franz | Date | [xsl] Calculate average value recur, Weiran Zhang |
Month |