| 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 | |||||||||||||||||||||
| 19 | package Math::NumSeq::FibbinaryBitCount; | ||||||||||||||||||||
| 20 | 1 | ▶ | use 5.004; | ||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||
| 21 | 1 | ▶ | use strict; | ||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||
| 22 | |||||||||||||||||||||
| 23 | 1 | ▶ | use vars '$VERSION', '@ISA'; | ||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||
| 24 | 1 | $VERSION = 75; | |||||||||||||||||||
| 25 | |||||||||||||||||||||
| 26 | 1 | ▶ | use Math::NumSeq; | ||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||
| 27 | 1 | ▶ | use Math::NumSeq::Base::IterateIth; | ||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||
| 28 | 1 | @ISA = ('Math::NumSeq::Base::IterateIth', | |||||||||||||||||||
| 29 | 'Math::NumSeq'); | ||||||||||||||||||||
| 30 | 1 | *_is_infinite = \&Math::NumSeq::_is_infinite; | |||||||||||||||||||
| 31 | |||||||||||||||||||||
| 32 | |||||||||||||||||||||
| 33 | # uncomment this to run the ### lines | ||||||||||||||||||||
| 34 | # use Smart::Comments; | ||||||||||||||||||||
| 35 | |||||||||||||||||||||
| 36 | # use constant name => Math::NumSeq::__('Fibbinary Bit Count'); | ||||||||||||||||||||
| 37 | 1 | ▶ | use constant description => Math::NumSeq::__('Bit count of fibbinary numbers (the numbers without adjacent 1 bits).'); | ||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||
| 38 | 1 | ▶ | use constant default_i_start => 0; # same as Fibbinary.pm | ||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||
| 39 | 1 | ▶ | use constant characteristic_increasing => 0; | ||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||
| 40 | 1 | ▶ | use constant characteristic_count => 1; | ||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||
| 41 | 1 | ▶ | use constant characteristic_smaller => 1; | ||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||
| 42 | |||||||||||||||||||||
| 43 | 1 | ▶ | use constant parameter_info_array => | ||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||
| 44 | [ { name => 'digit', | ||||||||||||||||||||
| 45 | display => Math::NumSeq::__('Digit'), | ||||||||||||||||||||
| 46 | share_key => 'digit_1_0_00', | ||||||||||||||||||||
| 47 | type => 'enum', | ||||||||||||||||||||
| 48 | default => '1', | ||||||||||||||||||||
| 49 | choices => ['1','0','00'], | ||||||||||||||||||||
| 50 | description => Math::NumSeq::__('What digit to count.'), | ||||||||||||||||||||
| 51 | }, | ||||||||||||||||||||
| 52 | 1 | ]; | |||||||||||||||||||
| 53 | |||||||||||||||||||||
| 54 | 1 | ▶ | sub values_min { | ||||||||||||||||||
|
Subroutine
values_min: called CC=2 SCAR=7.6
Pod
documented
| |||||||||||||||||||||
| 55 | 1 | my ($self) = @_; | |||||||||||||||||||
| 56 | 1 | ▶ | if ($self->{'digit'} eq 'all') { | ||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||
| 57 | 0 | return $self->ith($self->i_start); | |||||||||||||||||||
| 58 | } else { | ||||||||||||||||||||
| 59 | 1 | return 0; | |||||||||||||||||||
| 60 | } | ||||||||||||||||||||
| 61 | } | ||||||||||||||||||||
| 62 | |||||||||||||||||||||
| 63 | #------------------------------------------------------------------------------ | ||||||||||||||||||||
| 64 | # cf A027941 new highest bit count positions, being Fibonacci(2i+1)-1 | ||||||||||||||||||||
| 65 | # A095111 bit count parity, 1/0 | ||||||||||||||||||||
| 66 | # A020908 bit count of 2^k | ||||||||||||||||||||
| 67 | # | ||||||||||||||||||||
| 68 | # A072649 n occurs Fibonacci(n) times | ||||||||||||||||||||
| 69 | # is fibbinary bit length | ||||||||||||||||||||
| 70 | # A130233 maximum index k for which F(k) <= n, fibbinary length + 1 | ||||||||||||||||||||
| 71 | # A131234 1 then n occurs Fib(n) times | ||||||||||||||||||||
| 72 | # is length(Zeck)+1 | ||||||||||||||||||||
| 73 | # A049839 max in row of Euclidean steps table A049837 | ||||||||||||||||||||
| 74 | # | ||||||||||||||||||||
| 75 | # | ||||||||||||||||||||
| 76 | 1 | my %oeis_anum = (1 => 'A007895', # fibbinary 1-bit count | |||||||||||||||||||
| 77 | 0 => 'A102364', | ||||||||||||||||||||
| 78 | '00' => 'A212278', # count "00" adjacent, possibly overlapping | ||||||||||||||||||||
| 79 | all => 'A072649', | ||||||||||||||||||||
| 80 | # OEIS-Catalogue: A007895 | ||||||||||||||||||||
| 81 | # OEIS-Catalogue: A102364 digit=0 | ||||||||||||||||||||
| 82 | # OEIS-Catalogue: A212278 digit=00 | ||||||||||||||||||||
| 83 | # OEIS-Catalogue: A072649 digit=all i_start=1 | ||||||||||||||||||||
| 84 | ); | ||||||||||||||||||||
| 85 | 1 | ▶ | sub oeis_anum { | ||||||||||||||||||
|
Subroutine
oeis_anum: called CC=1 SCAR=0.0
Pod
documented
| |||||||||||||||||||||
| 86 | 1 | my ($self) = @_; | |||||||||||||||||||
| 87 | 1 | return $oeis_anum{$self->{'digit'}}; | |||||||||||||||||||
| 88 | } | ||||||||||||||||||||
| 89 | |||||||||||||||||||||
| 90 | #------------------------------------------------------------------------------ | ||||||||||||||||||||
| 91 | |||||||||||||||||||||
| 92 | 178 | ▶ | sub ith { | ||||||||||||||||||
|
Subroutine
ith: called CC=10 SCAR=23.5
Pod
documented
| |||||||||||||||||||||
| 93 | 178 | my ($self, $i) = @_; | |||||||||||||||||||
| 94 | ### FibbinaryBitCount ith(): $i | ||||||||||||||||||||
| 95 | |||||||||||||||||||||
| 96 | 178 | ▶ | if (_is_infinite($i)) { | ||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||
| 97 | 0 | return $i; | |||||||||||||||||||
| 98 | } | ||||||||||||||||||||
| 99 | |||||||||||||||||||||
| 100 | # f1+f0 > i | ||||||||||||||||||||
| 101 | # f0 > i-f1 | ||||||||||||||||||||
| 102 | # check i-f1 as the stopping point, so that if i=UV_MAX then won't | ||||||||||||||||||||
| 103 | # overflow a UV trying to get to f1>=i | ||||||||||||||||||||
| 104 | # | ||||||||||||||||||||
| 105 | 178 | my @fibs; | |||||||||||||||||||
| 106 | { | ||||||||||||||||||||
| 107 | 178 | my $f0 = ($i * 0); # inherit bignum 0 | |||||||||||||||||||
| 108 | 178 | my $f1 = $f0 + 1; # inherit bignum 1 | |||||||||||||||||||
| 109 | 178 | ▶ | while ($f0 <= $i-$f1) { | ||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||
| 110 | 742 | ($f1,$f0) = ($f1+$f0,$f1); | |||||||||||||||||||
| 111 | 742 | push @fibs, $f1; | |||||||||||||||||||
| 112 | } | ||||||||||||||||||||
| 113 | } | ||||||||||||||||||||
| 114 | ### @fibs | ||||||||||||||||||||
| 115 | |||||||||||||||||||||
| 116 | 178 | my $digit = $self->{'digit'}; | |||||||||||||||||||
| 117 | 178 | ▶ | if ($digit eq 'all') { | ||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||
| 118 | 0 | return scalar(@fibs); | |||||||||||||||||||
| 119 | } | ||||||||||||||||||||
| 120 | |||||||||||||||||||||
| 121 | 178 | my $ones = 0; | |||||||||||||||||||
| 122 | 178 | my $onezeros = 0; | |||||||||||||||||||
| 123 | 178 | my $sepzeros = 0; | |||||||||||||||||||
| 124 | 178 | ▶ | while (my $f = pop @fibs) { | ||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||
| 125 | ### at: "$f i=$i" | ||||||||||||||||||||
| 126 | 352 | ▶ | if ($i >= $f) { | ||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||
| 127 | 290 | $ones++; | |||||||||||||||||||
| 128 | 290 | $i -= $f; | |||||||||||||||||||
| 129 | ### sub: "$f to i=$i" | ||||||||||||||||||||
| 130 | |||||||||||||||||||||
| 131 | # never consecutive fibs, so pop without comparing to i | ||||||||||||||||||||
| 132 | 290 | ▶ | if (pop @fibs) { | ||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||
| 133 | 228 | $onezeros++; | |||||||||||||||||||
| 134 | } | ||||||||||||||||||||
| 135 | 290 | ▶ | unless ($i) { | ||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||
| 136 | ### stop at i=0 ... | ||||||||||||||||||||
| 137 | 168 | $sepzeros += scalar(@fibs); | |||||||||||||||||||
| 138 | 168 | last; | |||||||||||||||||||
| 139 | } | ||||||||||||||||||||
| 140 | } else { | ||||||||||||||||||||
| 141 | 62 | $sepzeros++; | |||||||||||||||||||
| 142 | } | ||||||||||||||||||||
| 143 | } | ||||||||||||||||||||
| 144 | ### $ones | ||||||||||||||||||||
| 145 | ### $onezeros | ||||||||||||||||||||
| 146 | ### $sepzeros | ||||||||||||||||||||
| 147 | |||||||||||||||||||||
| 148 | 178 | ▶ | if ($digit eq '0') { | ||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||
| 149 | 0 | return $sepzeros + $onezeros; | |||||||||||||||||||
| 150 | } | ||||||||||||||||||||
| 151 | 178 | ▶ | if ($digit eq '00') { | ||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||
| 152 | 0 | return $sepzeros; | |||||||||||||||||||
| 153 | } | ||||||||||||||||||||
| 154 | 178 | return $ones; | |||||||||||||||||||
| 155 | } | ||||||||||||||||||||
| 156 | |||||||||||||||||||||
| 157 | 14 | ▶ | sub pred { | ||||||||||||||||||
|
Subroutine
pred: called CC=2 SCAR=8.1
Pod
documented
| |||||||||||||||||||||
| 158 | 14 | my ($self, $value) = @_; | |||||||||||||||||||
| 159 | 14 | ▶ | 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
| |||||||||||||||||||||
| 160 | } | ||||||||||||||||||||
| 161 | |||||||||||||||||||||
| 162 | 1 | 1; | |||||||||||||||||||
| 163 | __END__ | ||||||||||||||||||||