コラッツ・角谷の問題 in XSLT DouKaku?

コラッツ・角谷の問題

任意の数nを与えたときに
・nが偶数ならば2で割る　(n=n/2)
・nが奇数ならば3倍して1を足す （n = 3*n+1)
を繰り返すと、いづれは1になる。というものがあります。

数値計算の上ではかなりの数まで成り立つことが知られています。
（すべての数について成り立つかは不明）
参考リンク先参照

ある任意の数nがコラッツ・角谷の問題で1になるまでのステップ数をf(n)とします。
1～2^20までの数でf(n)を求めて、f(n)が最大になるときのnとf(n)を表示してください。

たとえばn=9だと次のような数列をたどって、19ステップで1になります。
9->28->14->7->22->11->34->17->52->26->13->40->20->10->5->16->8->4->2->1
つまりf(9)=19です。

また、最大を求めた際の実行時間と環境を書いてください。

see: コラッツの問題の成り立つ範囲

post comment

Posted feedbacks - XSLT

OS: WindowsVista(Home Premium 32bit)
CPU: AMD Turion64X2 (1.6GHz)
メモリ: 1.5GB で、

XSLTプロセッサ環境が、
Saxon 9.0.0.6J from Saxonica
Java version 1.6.0_06

出力：
n=837799, f(n)=524

かかった時間は、
Stylesheet compilation time: 586 milliseconds
Execution time: 391187 milliseconds
だそうです。

<xsl:stylesheet version="2.0"
  xmlns:xsl="http://www.w3.org/1999/XSL/Transform"
  xmlns:xs="http://www.w3.org/2001/XMLSchema"
  xmlns:fn="http://www.w3.org/2005/xpath-functions"
  xmlns:my="uri:ja.doukaku.org:my-functions"
  exclude-result-prefixes="my"
  >

  <xsl:output method="text" />

  <xsl:template match="/" >
    <xsl:variable name="collatzresult" as="xs:integer*">
      <xsl:for-each select="1 to 1048576">
        <xsl:value-of select="my:collatz(.,0)" />
      </xsl:for-each>
    </xsl:variable>

    <xsl:variable name="max" as="xs:integer" select="fn:max($collatzresult)" />

    <xsl:text>n=</xsl:text>
    <xsl:for-each select="$collatzresult">
      <xsl:if test="$max=.">
        <xsl:value-of select="fn:position()" />
        <xsl:text>, </xsl:text>
      </xsl:if>
    </xsl:for-each>
    <xsl:text>f(n)=</xsl:text>
    <xsl:value-of select="$max" />
    <xsl:text>&#xA;</xsl:text>
  </xsl:template>

  <xsl:function name="my:collatz" as="xs:integer">
    <xsl:param name="n" as="xs:integer" />
    <xsl:param name="cnt" as="xs:integer" />

    <xsl:choose>
      <xsl:when test="$n=1">
        <xsl:value-of select="$cnt" />
      </xsl:when>
      <xsl:when test="($n mod 2)=0" >
        <xsl:value-of select="my:collatz($n idiv 2,$cnt+1)" />
      </xsl:when>
      <xsl:otherwise>
        <xsl:value-of select="my:collatz($n*3+1,$cnt+1)" />
      </xsl:otherwise>
    </xsl:choose>
  </xsl:function>

</xsl:stylesheet>

DouKaku?

コラッツ・角谷の問題

Posted feedbacks - XSLT

Index

Feed

Other

Link

Pathtraq