| 1 | # Copyright 2011, 2012, 2013, 2014, 2016, 2019, 2020 Kevin Ryde | ||||||||||
| 2 | |||||||||||
| 3 | # This file is part of Math-NumSeq. | ||||||||||
| 4 | # | ||||||||||
| 5 | # Math-NumSeq is free software; you can redistribute it and/or modify | ||||||||||
| 6 | # it under the terms of the GNU General Public License as published by the | ||||||||||
| 7 | # Free Software Foundation; either version 3, or (at your option) any later | ||||||||||
| 8 | # version. | ||||||||||
| 9 | # | ||||||||||
| 10 | # Math-NumSeq is distributed in the hope that it will be useful, but | ||||||||||
| 11 | # WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY | ||||||||||
| 12 | # or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License | ||||||||||
| 13 | # for more details. | ||||||||||
| 14 | # | ||||||||||
| 15 | # You should have received a copy of the GNU General Public License along | ||||||||||
| 16 | # with Math-NumSeq. If not, see <http://www.gnu.org/licenses/>. | ||||||||||
| 17 | |||||||||||
| 18 | package Math::NumSeq::SqrtContinuedPeriod; | ||||||||||
| 19 | 2 | ▶ | use 5.004; | ||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||
| 20 | 2 | ▶ | use strict; | ||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||
| 21 | |||||||||||
| 22 | 2 | ▶ | use vars '$VERSION', '@ISA'; | ||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||
| 23 | 2 | $VERSION = 75; | |||||||||
| 24 | |||||||||||
| 25 | 2 | ▶ | use Math::NumSeq; | ||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||
| 26 | 2 | ▶ | use Math::NumSeq::Base::IterateIth; | ||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||
| 27 | 2 | @ISA = ('Math::NumSeq::Base::IterateIth', | |||||||||
| 28 | 'Math::NumSeq'); | ||||||||||
| 29 | 2 | *_is_infinite = \&Math::NumSeq::_is_infinite; | |||||||||
| 30 | |||||||||||
| 31 | # uncomment this to run the ### lines | ||||||||||
| 32 | #use Smart::Comments; | ||||||||||
| 33 | |||||||||||
| 34 | |||||||||||
| 35 | # use constant name => Math::NumSeq::__('Sqrt Continued Fraction Period'); | ||||||||||
| 36 | 2 | ▶ | use constant description => Math::NumSeq::__('Period of the continued fraction expansion of sqrt(i), or 0 for perfect squares (where the expansion is finite)'); | ||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||
| 37 | 2 | ▶ | use constant characteristic_count => 1; | ||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||
| 38 | 2 | ▶ | use constant characteristic_smaller => 1; | ||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||
| 39 | 2 | ▶ | use constant characteristic_increasing => 0; | ||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||
| 40 | 2 | ▶ | use constant default_i_start => 1; | ||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||
| 41 | 2 | ▶ | use constant values_min => 0; | ||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||
| 42 | |||||||||||
| 43 | # cf A097853 contfrac sqrt(n) period, or 1 if square | ||||||||||
| 44 | # A054269 contfrac sqrt(prime(i)) period | ||||||||||
| 45 | # | ||||||||||
| 46 | 2 | ▶ | use constant oeis_anum => 'A003285'; # sqrt period, or 0 if square | ||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||
| 47 | |||||||||||
| 48 | 200 | ▶ | sub ith { | ||||||||
|
Subroutine
ith: called CC=5 SCAR=16.3
Pod
documented
| |||||||||||
| 49 | 200 | my ($self, $i) = @_; | |||||||||
| 50 | ### SqrtContinuedPeriod ith(): $i | ||||||||||
| 51 | |||||||||||
| 52 | 200 | ▶ | if (_is_infinite($i)) { | ||||||||
|
Branch: 1 branch
| |||||||||||
| 53 | 0 | return $i; | |||||||||
| 54 | } | ||||||||||
| 55 | 200 | ▶ | if ($i <= 0) { | ||||||||
|
Branch: 1 branch
| |||||||||||
| 56 | 0 | return 0; | |||||||||
| 57 | } | ||||||||||
| 58 | |||||||||||
| 59 | # initial a[1] = floor(sqrt(i)) = $root | ||||||||||
| 60 | # then root + 1/x = sqrt(i) | ||||||||||
| 61 | # 1/x = sqrt(i)-root | ||||||||||
| 62 | # x = 1/(sqrt(i)-root) | ||||||||||
| 63 | # x = (sqrt(i)+root)/(i-root*root) | ||||||||||
| 64 | # so P = root | ||||||||||
| 65 | # Q = i - root*root | ||||||||||
| 66 | # | ||||||||||
| 67 | 200 | my $p = my $root = int(sqrt($i)); | |||||||||
| 68 | 200 | my $q = $i - $root*$root; | |||||||||
| 69 | 200 | ▶ | if ($q <= 0) { | ||||||||
|
Branch: 1 branch
| |||||||||||
| 70 | # perfect square | ||||||||||
| 71 | 13 | return 0; | |||||||||
| 72 | } | ||||||||||
| 73 | |||||||||||
| 74 | 187 | my %seen; | |||||||||
| 75 | 187 | my $count = 0; | |||||||||
| 76 | 187 | for (;;) { | |||||||||
| 77 | 1273 | ▶ | if ($seen{"$p,$q"}++) { | ||||||||
|
Branch: 1 branch
| |||||||||||
| 78 | 187 | return $count; | |||||||||
| 79 | } | ||||||||||
| 80 | 1086 | $count++; | |||||||||
| 81 | |||||||||||
| 82 | 1086 | my $value = int (($root + $p) / $q); | |||||||||
| 83 | 1086 | $p -= $value*$q; | |||||||||
| 84 | 1086 | ($p, $q) = (-$p, | |||||||||
| 85 | ($i - $p*$p) / $q); | ||||||||||
| 86 | |||||||||||
| 87 | ### assert: $p >= 0 | ||||||||||
| 88 | ### assert: $q > 0 | ||||||||||
| 89 | ### assert: $p <= $root | ||||||||||
| 90 | ### assert: $q <= 2*$root+1 | ||||||||||
| 91 | ### assert: (($p*$p - $i) % $q) == 0 | ||||||||||
| 92 | } | ||||||||||
| 93 | } | ||||||||||
| 94 | |||||||||||
| 95 | 2 | 1; | |||||||||
| 96 | __END__ | ||||||||||