The first Fibonacci Number that is zeroless-pandigital at both ends

Here is another Project Euler problem – this time a little-bit more challenging:

The Fibonacci sequence is defined by the recurrence relation:

Fn = Fn1 + Fn2 , where F1 = 1 and F2 = 1.

It turns out that F541  , which contains 113 digits, is the first Fibonacci number for which the last nine digits are 1-9 pandigital (contain all the digits 1 to 9, but not necessarily in order). And F2749  , which contains 575 digits, is the first Fibonacci number for which the first nine digits are 1-9 pandigital.

Given that Fk is the first Fibonacci number for which the first nine digits AND the last nine digits are 1-9 pandigital, find k.”

Does this sound XSLT-ish? No, not at all.

This solution:

<xsl:stylesheet version="2.0"

 xmlns:xsl="http://www.w3.org/1999/XSL/Transform"

 xmlns:xs="http://www.w3.org/2001/XMLSchema"

 xmlns:f="http://fxsl.sf.net/">

 <xsl:import href="../../../f/func-Fibonacci.xsl"/>

 <xsl:output omit-xml-declaration="yes" indent="yes"/>

 

 <xsl:template match="/">

  <xsl:sequence select=

  "f:getFiboBothEndingsPan9(3,2,1)

  "/>

 </xsl:template>

 

 <xsl:function name="f:getFiboBothEndingsPan9" as="xs:integer">

  <xsl:param name="pcurrentInd" as="xs:integer"/>

  <xsl:param name="pPrev1" as="xs:integer"/>

  <xsl:param name="pPrev2" as="xs:integer"/>

 

  <xsl:sequence select=

   "for $current in ($pPrev1 + $pPrev2) mod 1000000000

        return

           if(f:isPandigital19($current)

             and

              f:isPandigital19Head(f:fibo($pcurrentInd))

              )

             then $pcurrentInd

             else

               f:getFiboBothEndingsPan9($pcurrentInd+1, $current, $pPrev1)

   "/>

 </xsl:function>

 

 <xsl:function name="f:isPandigital19" as="xs:boolean">

  <xsl:param name="pN" as="xs:integer"/>

 

  <xsl:sequence select=

  "for $s in xs:string($pN)

    return

          not(translate(‘123456789’, $s, ”))

  "/>

 </xsl:function>

 

 <xsl:function name="f:isPandigital19Head" as="xs:boolean">

   <xsl:param name="pN" as="xs:integer"/>

 

   <xsl:sequence select="f:isPandigital19(f:head9($pN))"/>

 </xsl:function>

 

  <xsl:function name="f:head9" as="xs:integer">

   <xsl:param name="arg1" as="xs:integer"/>

 

   <xsl:sequence select=

    "xs:integer(substring(string($arg1), 1, 9))"/>

  </xsl:function>

</xsl:stylesheet>

has the following properties:

  • Execution time:                 34.6 sec.
  • LOC:                                       54 (~ 40 express the solution)
  • Time to write the code:  ~15 min.
  • Uses library:                       FXSL (the f:fibo() function for generating Fibonacci numbers)

The index of the first Fibonacci number with the required properties is more than 300 thousand and the number itself has more than 68 thousand digits.

Not satisfied with the speed of this solution? Want even faster? Then here’s something you may consider:

<xsl:stylesheet version="2.0"

 xmlns:xsl="http://www.w3.org/1999/XSL/Transform"

 xmlns:xs="http://www.w3.org/2001/XMLSchema"

 xmlns:f="http://fxsl.sf.net/">

 <xsl:output omit-xml-declaration="yes" indent="yes"/>

 

 <xsl:template match="/">

  <xsl:sequence select=

  "f:getFiboBothEndingsPan9(3,2,1,2,1)

  "/>

 </xsl:template>

 

 <xsl:function name="f:getFiboBothEndingsPan9" as="xs:integer">

  <xsl:param name="pcurrentInd" as="xs:integer"/>

  <xsl:param name="pPrevTail1" as="xs:integer"/>

  <xsl:param name="pPrevTail2" as="xs:integer"/>

  <xsl:param name="pPrevHead1" as="xs:integer"/>

  <xsl:param name="pPrevHead2" as="xs:integer"/>

 

  <xsl:sequence select=

   "for $currentTail in ($pPrevTail1 + $pPrevTail2) mod 1000000000,

        $newHead1 in $pPrevHead1 + $pPrevHead2,

        $newHead2 in $pPrevHead1,

        $currentHead1 in if($newHead1 ge 10000000000000000)

                           then $newHead1 idiv 10

                           else $newHead1,

        $currentHead2 in if($newHead1 ge 10000000000000000)

                            then $newHead2 idiv 10

                            else $newHead2

        return

           if($currentHead1 ge 100000000

             and

              f:isPandigital19($currentTail)

             and

              f:isPandigital19

                    (xs:integer(substring(string($currentHead1),1,9))))

             then $pcurrentInd

             else

               f:getFiboBothEndingsPan9($pcurrentInd+1,

                                        $currentTail, $pPrevTail1,

                                        $currentHead1, $currentHead2

                                        )

   "/>

 </xsl:function>

 

 <xsl:function name="f:isPandigital19" as="xs:boolean">

  <xsl:param name="pN" as="xs:integer"/>

 

  <xsl:sequence select=

  "for $s in xs:string($pN)

    return

          not(translate(‘123456789’, $s, ”))

  "/>

 </xsl:function>

</xsl:stylesheet>

We have added a a couple of lines of code and look what we have now:

  • Execution time:                     0.555 sec.
  • LOC:                                        55 (~ 43 express the solution)
  • Time to write the code:  ~10 min.

As witnessed in the Project Euler thread for this problem (one must have provided the correct answer in order to access this thread), many solutions took longer: from 3.3 seconds, to 30-40 minutes, to couple of hours.

One Python programmer even waited for the end of his brute-force solution … 12 days

Advertisements
This entry was posted in Project Euler. Bookmark the permalink.

8 Responses to The first Fibonacci Number that is zeroless-pandigital at both ends

  1. Khach says:

    Dmitri, could you please explain either of these solutions?

    • Khach, What is it that you don’t understand in the first solution? It must be self-explanatory.

      • Khach says:

        Dmitri,
        About the first solution. What the general algorithm of the calculation implemented in the stylesheet and namely what does the second xsl:sequence element? In fact I am not experienced in computational usage of XSLT but would like to gain some experience. Also there is an imported stylesheet ../../../f/func-Fibonacci.xsl. Where is it, or maybe it is the same stylesheet itself?
        About the second solution. This seems more elegant but, again, I do not grasp the algorithm.

  2. func-Fibonacci.xsl is part of FXSL. In the post there is already a link to its source — on the smae line that says: “Uses library:: FXSL (the f:fibo() function for generating Fibonacci numbers)” . One can download the latest version of FXSL from its sourceforge CVS.

    As for “the second xsl:sequence”, I guess you mean this:

    This produces true() exactly when the string representation of $pN contains all digits from 1 to 9 (in any order.

    The XPath translate($s1, $s2, $s3) function replaces any character in S1 that is also found in $s2 with its (of $s2) same-position character in $s3. When $s3 is the empty string, then the result is the string $s1 in which all occurences of characters in $s2 are deleted.

    In this concrete case, if $s doesn’t contain all digits from 1 to 9, then some digit in the first argument of translate() “123456789” will remain undeleted in the result. Because a non-empty string is automatically converted to the boolean true(), in this case not(translate(’123456789′, $s, ”)) returns false().

    The f:isPandigital19() function is used to check if a number contains all digits 123456789 or not. When passed (as in all cases in this code) a 9-digit number, if it returns true() then this number is zeroless-pandigital.

    • To continue my answer, we first verify that the number is zeroless-pandigital at the end, only then we verify if it is zeroless-pandigital at the head. If both the end and head are zeroless-pandigital — this is our result. If not, then we need to do the same check on the next Fibonacci number.

      • Khach says:

        Thank you for your explanation. I have to think over it some amount of time.
        Is the algorithm of the second stylesheet the same?

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s