| 1 | # Copyright 2011, 2012, 2013, 2014, 2016, 2017, 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 | |||||||||||||||||||||
| 19 | # Edsgar Dijkstra | ||||||||||||||||||||
| 20 | # http://www.cs.utexas.edu/users/EWD/ewd05xx/EWD570.PDF | ||||||||||||||||||||
| 21 | # http://www.cs.utexas.edu/users/EWD/ewd05xx/EWD578.PDF | ||||||||||||||||||||
| 22 | |||||||||||||||||||||
| 23 | # Some Properties of a Function Studied by De Rham, Carlitz and Dijkstra and | ||||||||||||||||||||
| 24 | # its Relation to the Eisenstein-Stern's Diatomic Sequence | ||||||||||||||||||||
| 25 | # I. Urhiba, Math. Comm. 6 2001 181-198 | ||||||||||||||||||||
| 26 | |||||||||||||||||||||
| 27 | # Lind, Stern summary | ||||||||||||||||||||
| 28 | # "An Extension of Stern'S Diatomic Sequence", Duke Math J 36 | ||||||||||||||||||||
| 29 | # 1969 55-60 | ||||||||||||||||||||
| 30 | |||||||||||||||||||||
| 31 | |||||||||||||||||||||
| 32 | package Math::NumSeq::SternDiatomic; | ||||||||||||||||||||
| 33 | 2 | ▶ | use 5.004; | ||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||
| 34 | 2 | ▶ | use strict; | ||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||
| 35 | |||||||||||||||||||||
| 36 | 2 | ▶ | use vars '$VERSION', '@ISA'; | ||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||
| 37 | 2 | $VERSION = 75; | |||||||||||||||||||
| 38 | 2 | ▶ | use Math::NumSeq; | ||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||
| 39 | 2 | @ISA = ('Math::NumSeq'); | |||||||||||||||||||
| 40 | 2 | *_is_infinite = \&Math::NumSeq::_is_infinite; | |||||||||||||||||||
| 41 | |||||||||||||||||||||
| 42 | 2 | ▶ | use Math::NumSeq::Fibonacci; | ||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||
| 43 | 2 | *_bit_split_hightolow = \&Math::NumSeq::Fibonacci::_bit_split_hightolow; | |||||||||||||||||||
| 44 | |||||||||||||||||||||
| 45 | # uncomment this to run the ### lines | ||||||||||||||||||||
| 46 | #use Smart::Comments; | ||||||||||||||||||||
| 47 | |||||||||||||||||||||
| 48 | # use constant name => Math::NumSeq::__('Stern Diatomic'); | ||||||||||||||||||||
| 49 | 2 | ▶ | use constant description => Math::NumSeq::__('Stern\'s diatomic sequence.'); | ||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||
| 50 | 2 | ▶ | use constant default_i_start => 0; | ||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||
| 51 | 2 | ▶ | use constant values_min => 0; | ||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||
| 52 | 2 | ▶ | use constant characteristic_smaller => 1; | ||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||
| 53 | 2 | ▶ | use constant characteristic_increasing => 0; | ||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||
| 54 | 2 | ▶ | use constant characteristic_integer => 1; | ||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||
| 55 | |||||||||||||||||||||
| 56 | #------------------------------------------------------------------------------ | ||||||||||||||||||||
| 57 | # cf A126606 - starting 0,2 gives 2*diatomic | ||||||||||||||||||||
| 58 | # A049455 - repeat 0..2^k | ||||||||||||||||||||
| 59 | # A049456 - extra 1 at end of each row | ||||||||||||||||||||
| 60 | # A174980 - type ([0,1],1), adding 1 extra at n=2^k | ||||||||||||||||||||
| 61 | # A049455,A049456 stern/farey tree | ||||||||||||||||||||
| 62 | # A070878 stern by rows | ||||||||||||||||||||
| 63 | # A070879 stern by rows | ||||||||||||||||||||
| 64 | # http://oeis.org/stern_brocot.html | ||||||||||||||||||||
| 65 | # | ||||||||||||||||||||
| 66 | # cf Michael Somos iteration in A002487 | ||||||||||||||||||||
| 67 | 2 | ▶ | use constant oeis_anum => 'A002487'; | ||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||
| 68 | |||||||||||||||||||||
| 69 | #------------------------------------------------------------------------------ | ||||||||||||||||||||
| 70 | |||||||||||||||||||||
| 71 | 4 | ▶ | sub rewind { | ||||||||||||||||||
|
Subroutine
rewind: called CC=1 SCAR=0.0
Pod
documented
| |||||||||||||||||||||
| 72 | 4 | my ($self) = @_; | |||||||||||||||||||
| 73 | 4 | $self->{'i'} = $self->i_start; | |||||||||||||||||||
| 74 | 4 | $self->{'p'} = 0; | |||||||||||||||||||
| 75 | 4 | $self->{'q'} = 1; | |||||||||||||||||||
| 76 | } | ||||||||||||||||||||
| 77 | 12 | ▶ | sub seek_to_i { | ||||||||||||||||||
|
Subroutine
seek_to_i: called CC=1 SCAR=0.0
Pod
documented
| |||||||||||||||||||||
| 78 | 12 | my ($self, $i) = @_; | |||||||||||||||||||
| 79 | 12 | $self->{'i'} = $i; | |||||||||||||||||||
| 80 | 12 | ($self->{'p'},$self->{'q'}) = $self->ith_pair($i); | |||||||||||||||||||
| 81 | } | ||||||||||||||||||||
| 82 | |||||||||||||||||||||
| 83 | 203 | ▶ | sub next { | ||||||||||||||||||
|
Subroutine
next: called CC=1 SCAR=0.0
Pod
documented
| |||||||||||||||||||||
| 84 | 203 | my ($self) = @_; | |||||||||||||||||||
| 85 | 203 | my $p = $self->{'p'}; | |||||||||||||||||||
| 86 | 203 | my $q = $self->{'q'}; | |||||||||||||||||||
| 87 | 203 | $self->{'p'} = $q; | |||||||||||||||||||
| 88 | 203 | $self->{'q'} = $p + $q - 2*($p % $q); | |||||||||||||||||||
| 89 | 203 | return ($self->{'i'}++, $p); | |||||||||||||||||||
| 90 | } | ||||||||||||||||||||
| 91 | |||||||||||||||||||||
| 92 | 17 | ▶ | sub ith { | ||||||||||||||||||
|
Subroutine
ith: called CC=1 SCAR=0.0
Pod
documented
| |||||||||||||||||||||
| 93 | 17 | my ($self, $i) = @_; | |||||||||||||||||||
| 94 | 17 | return ($self->ith_pair($i))[0]; | |||||||||||||||||||
| 95 | } | ||||||||||||||||||||
| 96 | |||||||||||||||||||||
| 97 | # Return ($value[i], $value[i+1]). | ||||||||||||||||||||
| 98 | 40 | ▶ | sub ith_pair { | ||||||||||||||||||
|
Subroutine
ith_pair: called CC=6 SCAR=18.0
Pod
documented
| |||||||||||||||||||||
| 99 | 40 | my ($self, $i) = @_; | |||||||||||||||||||
| 100 | ### SternDiatomic _ith_pair(): "$i" | ||||||||||||||||||||
| 101 | |||||||||||||||||||||
| 102 | 40 | ▶ | if ($i < 0) { | ||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||
| 103 | 3 | ▶ | if ($i < -1) { | ||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||
| 104 | 1 | return (undef,undef); | |||||||||||||||||||
| 105 | } else { | ||||||||||||||||||||
| 106 | 2 | return (undef,0); | |||||||||||||||||||
| 107 | } | ||||||||||||||||||||
| 108 | } | ||||||||||||||||||||
| 109 | 37 | ▶ | if (_is_infinite($i)) { # don't loop forever if $value is +/-infinity | ||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||
| 110 | 0 | return ($i,$i); | |||||||||||||||||||
| 111 | } | ||||||||||||||||||||
| 112 | |||||||||||||||||||||
| 113 | 37 | my $p = ($i * 0); # inherit bignum 0 | |||||||||||||||||||
| 114 | 37 | my $q = $p + 1; # inherit bignum 1 | |||||||||||||||||||
| 115 | |||||||||||||||||||||
| 116 | 37 | foreach my $bit (_bit_split_hightolow($i)) { | |||||||||||||||||||
| 117 | 103 | ▶ | if ($bit) { | ||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||
| 118 | 60 | $p += $q; | |||||||||||||||||||
| 119 | } else { | ||||||||||||||||||||
| 120 | 43 | $q += $p; | |||||||||||||||||||
| 121 | } | ||||||||||||||||||||
| 122 | 103 | $i = int($i/2); | |||||||||||||||||||
| 123 | } | ||||||||||||||||||||
| 124 | |||||||||||||||||||||
| 125 | ### result: "$p, $q" | ||||||||||||||||||||
| 126 | 37 | return ($p,$q); | |||||||||||||||||||
| 127 | } | ||||||||||||||||||||
| 128 | |||||||||||||||||||||
| 129 | 12 | ▶ | sub pred { | ||||||||||||||||||
|
Subroutine
pred: called CC=2 SCAR=8.1
Pod
documented
| |||||||||||||||||||||
| 130 | 12 | my ($self, $value) = @_; | |||||||||||||||||||
| 131 | ### SternDiatomic pred(): $value | ||||||||||||||||||||
| 132 | 12 | ▶ | return ($value >= 0 && $value == int($value)); | ||||||||||||||||||
|
Condition33%1/3
$value >= 0 && $value == int $value
MC/DC0%0/2
$value >= 0 && $value == int $value
$value >= 0
$value == int $value
Truth table33%1/3
A && B
A= $value >= 0B= $value == int $value
| |||||||||||||||||||||
| 133 | } | ||||||||||||||||||||
| 134 | |||||||||||||||||||||
| 135 | 2 | 1; | |||||||||||||||||||
| 136 | __END__ | ||||||||||||||||||||