[no subject]

My entry: stylesheet and result below.

timings on a PIII 730 (I really should get a new machine, my laptop is
4 times faster but isn't here:-)

David



Saxon 8.4 from Saxonica
Java version 1.5.0_02
Stylesheet compilation time: 1552 milliseconds
Calling template x


:

f3000:
6643904603669600722802178478660283842441635124527832594055797655426212141
61219257396449810982999820391132226802809465132446349331994409434926019045342
723
74918853031699467847355132063510109961938297318162258568733693978437352789755
548
94868417261317338143401291756224504216051010258971732359906627702037564387865
175
30547101123748849140252686120104032647025145598956675902135010566909783124959
436
46982555831428970135422715178460286571078062467510705656982282054284666032181
383
88962758197532813714918090044122191248563751216948117287242136678145773266185
214
78357661859018967313354840178403197559969056510791709859144173304364898001

1st (fermat base 2 pseudo-)prime:
72280217
:

Execution time: 501 milliseconds
Calling template x


:

f3000:
6643904603669600722802178478660283842441635124527832594055797655426212141
61219257396449810982999820391132226802809465132446349331994409434926019045342
723
74918853031699467847355132063510109961938297318162258568733693978437352789755
548
94868417261317338143401291756224504216051010258971732359906627702037564387865
175
30547101123748849140252686120104032647025145598956675902135010566909783124959
436
46982555831428970135422715178460286571078062467510705656982282054284666032181
383
88962758197532813714918090044122191248563751216948117287242136678145773266185
214
78357661859018967313354840178403197559969056510791709859144173304364898001

1st (fermat base 2 pseudo-)prime:
72280217
:

Execution time: 180 milliseconds
Calling template x


:

f3000:
6643904603669600722802178478660283842441635124527832594055797655426212141
61219257396449810982999820391132226802809465132446349331994409434926019045342
723
74918853031699467847355132063510109961938297318162258568733693978437352789755
548
94868417261317338143401291756224504216051010258971732359906627702037564387865
175
30547101123748849140252686120104032647025145598956675902135010566909783124959
436
46982555831428970135422715178460286571078062467510705656982282054284666032181
383
88962758197532813714918090044122191248563751216948117287242136678145773266185
214
78357661859018967313354840178403197559969056510791709859144173304364898001

1st (fermat base 2 pseudo-)prime:
72280217
:

Execution time: 180 milliseconds








<xsl:stylesheet xmlns:xsl="http://www.w3.org/1999/XSL/Transform";
        version="2.0"
 xmlns:xs="http://www.w3.org/2001/XMLSchema";
 xmlns:x="data:,x">
  <xsl:output method="text"/>
  <xsl:function name="x:power_mod" as="xs:integer">
    <xsl:param name="b" as="xs:integer"/>
    <xsl:param name="e" as="xs:integer"/>
    <xsl:param name="n" as="xs:integer"/>
    <xsl:choose>
      <xsl:when test="$e=0">
        <xsl:sequence select="1"/>
      </xsl:when>
      <xsl:when test="$e=1">
        <xsl:sequence select="$b"/>
      </xsl:when>
      <xsl:when test="$e&gt;1 and ($e mod 2 = 1)">
        <xsl:variable name="e2" select="x:power_mod($b,$e idiv 2,$n)"/>
        <xsl:sequence select="($e2 * $e2 * $b) mod $n"/>
      </xsl:when>
      <xsl:when test="$e&gt;1">
        <xsl:variable name="e2" select="x:power_mod($b,$e idiv 2,$n)"/>
        <xsl:sequence select="($e2 * $e2) mod $n"/>
      </xsl:when>
    </xsl:choose>
  </xsl:function>
  <xsl:function name="x:fib" as="xs:integer">
    <xsl:param name="n" as="xs:integer"/>
    <xsl:choose>
      <xsl:when test="$n=0">
        <xsl:sequence select="1"/>
      </xsl:when>
      <xsl:when test="$n =1">
        <xsl:sequence select="1"/>
      </xsl:when>
      <xsl:when test="$n mod 2 = 0">
        <xsl:variable name="n2" select="$n idiv 2"/>
        <xsl:variable name="fn" select="x:fib($n2)"/>
        <xsl:variable name="fn-1" select="x:fib($n2 -1)"/>
        <xsl:sequence select="$fn * $fn + $fn-1 * $fn-1"/>
      </xsl:when>
      <xsl:when test="$n mod 2 = 1">
        <xsl:variable name="n2" select="($n - 1) idiv 2"/>
        <xsl:variable name="fn" select="x:fib($n2)"/>
        <xsl:variable name="fn-1" select="x:fib($n2 -1)"/>
        <xsl:sequence select="(2 * $fn-1 + $fn) * $fn"/>
      </xsl:when>
    </xsl:choose>
  </xsl:function>
  <xsl:template  name="x">

:
    <xsl:variable name="x"  select="string(x:fib(3000))"/>
f3000:
    <xsl:value-of select="$x"/>

1st (fermat base 2 pseudo-)prime:
    <xsl:value-of select="(for $i in 1 to (string-length($x)-9)
                         return
xs:integer(substring($x,$i,10)))[x:power_mod(2,. - 1, .)=1][1]"
            separator="&#10;"/>
:

  </xsl:template>
</xsl:stylesheet>

-----------------------------------------------------------------------------
------------------

Dimitre Novatchev's solution:

<xsl:stylesheet version="2.0"
 xmlns:xsl="http://www.w3.org/1999/XSL/Transform";
 xmlns:xs="http://www.w3.org/2001/XMLSchema";
 xmlns:saxon="http://saxon.sf.net/";
 xmlns:f="http://fxsl.sf.net/";
 exclude-result-prefixes="xs saxon f"
 >
  <xsl:import href="../f/func-Fibonacci.xsl"/>
  <xsl:import href="../f/func-Primes.xsl"/>

 <xsl:output method="text"/>

<!--
    Solves the following problem:

    Find the first 10-digit prime in consecutive digits of F-3000

    Where F-N is the Nth Fibonacci number.

    Here are the elements of the sequence of Fibonacci numbers from 0 to 11:

    Element:    1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144
    Index:      0, 1, 2, 3, 4, 5,  6,  7,  8,  9, 10,  11

   Invoke on any xml file or with an initial template named "initial".

   Expected result: 0072280217

-->

  <xsl:variable name="vFib" select="xs:string(f:fibo(3000))"/>

  <xsl:template name="initial" match="/">
   The first prime from a sequence of
   ten consecutive digits in Fibonacci's number F3000:
<xsl:text/>
   <xsl:value-of select="$vFib"/>
   Is: <xsl:text/>
   <xsl:value-of select=
   "(
     for $n in 1 to string-length($vFib)-9
                  return(substring($vFib, $n, 10))
     )
     [f:isPrime(xs:integer(.))][1]
   "/>
  </xsl:template>

</xsl:stylesheet>

file:  ../f/func-Fibonacci.xsl
====================
<xsl:stylesheet version="2.0"
 xmlns:xsl="http://www.w3.org/1999/XSL/Transform";
 xmlns:xs="http://www.w3.org/2001/XMLSchema";
 xmlns:saxon="http://saxon.sf.net/";
 xmlns:f="http://fxsl.sf.net/";
 exclude-result-prefixes="f xs saxon"
 >

 <xsl:function name="f:fiboLimitedSeq" as="xs:integer*">
   <xsl:param name="pLimit" as="xs:double"/>
   <xsl:param name="pN"  as="xs:integer"/>

   <xsl:variable name="vVal" select="f:fibo($pN)"/>

   <xsl:if test="$vVal le $pLimit" >
     <xsl:sequence select=
     "$vVal, f:fiboLimitedSeq($pLimit, $pN+1)"
     />
   </xsl:if>
 </xsl:function>

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

   <xsl:sequence select=
    "if ($pN gt 10)
        then
          if($pN mod 2 = 0)
            then
               for $i in $pN idiv 2,
                    $fi in f:fibo($i),
	$fi-1 in f:fibo($i -1)
	    return $fi*$fi + $fi-1*$fi-1
            else
               for $i in ($pN -1) idiv 2,
	$fi in f:fibo($i),
	$fi-1 in f:fibo($i -1)
	   return (2*$fi-1 + $fi) * $fi
    else
       (1,1,2,3,5,8,13,21,34,55,89)[$pN +1]
    "/>
 </xsl:function>
 </xsl:stylesheet>

file ../f/func-Primes.xsl
=================
<xsl:stylesheet version="2.0"
 xmlns:xsl="http://www.w3.org/1999/XSL/Transform";
 xmlns:xs="http://www.w3.org/2001/XMLSchema";
 xmlns:saxon="http://saxon.sf.net/";
 xmlns:gexslt="http://www.gobosoft.com/eiffel/gobo/gexslt/extension";
 xmlns:f="http://fxsl.sf.net/";
 exclude-result-prefixes="xs saxon f"
 >
  <xsl:import href="func-sqrt.xsl"/>

 <xsl:output method="text"/>

  <xsl:function name="f:isPrime" as="xs:boolean" saxon:memo-function="yes"
                       gexslt:memo-function="yes">
    <xsl:param name="pNum" />

    <xsl:variable name="vstrNum" select="string($pNum)" as="xs:string"/>
    <xsl:variable name="vLastDigit"
                  select="substring($vstrNum, string-length($vstrNum))"/>

    <xsl:value-of select=
           "if(not(translate($vLastDigit, '024568', '')) )
               then false()
               else
                 if(f:pow2mod($pNum - 1, $pNum) ne 1)
                   then false()
                   else
	empty(
	              (3, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41,
		  (43 to xs:integer(round(f:sqrt($pNum, 0.1E0)))) )
                                                       [f:divisor(., $pNum)]
	            )
            "/>
  </xsl:function>

<!--
    f:pow2mod(K, N) = 2^K mod N
-->
  <xsl:function name="f:pow2mod" as="xs:integer">
    <xsl:param name="pE" as="xs:integer"/>
    <xsl:param name="pN" as="xs:integer"/>

    <xsl:sequence select=
     "if($pE eq 1)
       then 2
       else
         for $half in f:pow2mod($pE idiv 2, $pN)
           return
              $half * $half * (1 + ($pE mod 2)) mod $pN
     "/>
  </xsl:function>
</xsl:stylesheet>



Timings on my 2-year old P-IV 3GHZ 2GB PC run with Saxon 8.6.1:

Execution time: 235 ms

Result:


   The first prime from a sequence of
   ten consecutive digits in Fibonacci's number F3000:
66439046036696007228021784786602838424416351245278325940557976554262121416121
92573964498109829998203911322268028094651324463493319944094349260190453427237
49188530316994678473551320635101099619382973181622585687336939784373527897555
48948684172613173381434012917562245042160510102589717323599066277020375643878
65175305471011237488491402526861201040326470251455989566759021350105669097831
24959436469825558314289701354227151784602865710780624675107056569822820542846
66032181383889627581975328137149180900441221912485637512169481172872421366781
45773266185214783576618590189673133548401784031975599690565107917098591441733
04364898001

   Is: 0072280217




--
Cheers,
Dimitre Novatchev
---------------------------------------
To avoid situations in which you might make mistakes may be the
biggest mistake of all.

Current Thread