NumSeq/FibonacciRepresentations.pm

filter: Statementstmt 98.7% 76 / 77 Branchbran 94.4% 17 / 18 Conditioncond 33.3% 1 / 3 MC/DCmcdc 0.0% 0 / 2 Subroutinesub 100% 16 / 16 Podpod 100% 3 / 3 totaltotal 94.9% 113 / 119 CC 11 SCAR 15.2
CC
11
Cov
96%
ith_pair
10.0
pred
2.3
BEGIN
1.0
CRAP 4.6
« NumSeq/Abundant.pm ↑ Summary NumSeq/AlgebraicContinued.pm »
1 # Copyright 2014, 2016, 2019, 2020, 2021 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 # https://eudml.org/doc/92679
20 # J. Berstel, An Exercise on Fibonacci Representations, RAIRO/
21 # Informatique Theorique, Vol. 35, No 6, 2001, pp. 491-498, in
22 # the issue dedicated to Aldo De Luca on the occasion of his
23 # 60-th anniversary.
24  
25 # Paul K. Stockmeyer, "A Smooth Tight Upper Bound for the Fibonacci
26 # Representation Function R(N)", Fibonacci Quarterly, Volume 46/47, Number
27 # 2, May 2009.
28 # Free access only post 2003
29 # http://www.fq.math.ca/46_47-2.html
30 # http://www.fq.math.ca/Papers/46_47-2/Stockmeyer.pdf
31  
32 # Klarner 1966
33 # Product (1+x^fib(i)) gives coefficients R(N)
34 # R(F[n]) = floor((n+2)/2) n > 1
35 # R(F[n]-1) = floor((n+1)/2) n > 0
36 # R(F[n]-2) = n-2 n > 2
37 # R(F[n]-3) = n-3 n > 4
38  
39 # http://www.math.tugraz.at/~edson/Publications/Representations%20in%20Fibonacci%20Base.pdf
40  
41  
42 package Math::NumSeq::FibonacciRepresentations;
43 2 ▶use 5.004;
Subroutine BEGIN: called CC=1 SCAR=0.0
44 2 ▶use strict;
Subroutine BEGIN: called CC=1 SCAR=0.0
45  
46 2 ▶use vars '$VERSION', '@ISA';
Subroutine BEGIN: called CC=1 SCAR=0.0
47 2 $VERSION = 75;
48  
49 2 ▶use Math::NumSeq;
Subroutine BEGIN: called CC=1 SCAR=0.0
50 2 ▶use Math::NumSeq::Base::IterateIth;
Subroutine BEGIN: called CC=1 SCAR=0.0
51 2 @ISA = ('Math::NumSeq::Base::IterateIth', 'Math::NumSeq');
52 2 *_is_infinite = \&Math::NumSeq::_is_infinite;
53  
54 # uncomment this to run the ### lines
55 # use Smart::Comments;
56  
57 # use constant name => Math::NumSeq::__('Fibonacci Representations');
58 2 ▶use constant description => Math::NumSeq::__('Fibonacci representations sequence, the number of ways i can be formed as a sum of distinct Fibonacci numbers.');
Subroutine BEGIN: called CC=1 SCAR=0.0
59 2 ▶use constant default_i_start => 0;
Subroutine BEGIN: called CC=1 SCAR=0.0
60 2 ▶use constant characteristic_count => 1;
Subroutine BEGIN: called CC=1 SCAR=0.0
61 2 ▶use constant characteristic_smaller => 1;
Subroutine BEGIN: called CC=1 SCAR=0.0
62 2 ▶use constant characteristic_integer => 1;
Subroutine BEGIN: called CC=1 SCAR=0.0
63 2 ▶use constant characteristic_increasing => 0;
Subroutine BEGIN: called CC=1 SCAR=0.0
64 2 ▶use constant values_min => 1;
Subroutine BEGIN: called CC=1 SCAR=0.0
65  
66 #------------------------------------------------------------------------------
67 #
68 2 ▶use constant oeis_anum => 'A000119';
Subroutine BEGIN: called CC=1 SCAR=0.0
69  
70 #------------------------------------------------------------------------------
71  
72 1126 ▶sub ith {
Subroutine ith: called CC=1 SCAR=0.0
Pod documented
73 1126 my ($self, $i) = @_;
74 1126 return ($self->ith_pair($i))[0];
75 }
76  
77 1145 ▶sub ith_pair {
Subroutine ith_pair: called CC=10 SCAR=23.0
Pod documented
78 1145 my ($self, $i) = @_;
79 ### ith_pair(): $i
80  
81 1145 ▶ if ($i < 0) {
Branch: 1 branch
BranchTrueFalseTotal
if ($i < 0) 3 1142 1145
82 3 return (undef,undef);
83 }
84 1142 ▶ if (_is_infinite($i)) {
Branch: 1 branch
BranchTrueFalseTotal
if (_is_infinite($i)) 0 1142 1142
85 0 return ($i,$i); # +inf or nan
86 }
87  
88 # seeking f2 >= i+1
89 # but stop at f1 >= i so not go past UV_MAX if i=UV_MAX
90 #
91 1142 my @fibs; # all Fibonacci numbers <= $i
92 {
93 # find biggest fibonacci f1 <= i
94 # if f1+f0 > i then stop loop
95 # f1+f0 might overflow UV_MAX so do the loop
96 # condition as stop when f1 > i-f0, continue while f1 <= i-f0
97 #
98 1142 my $f0 = ($i*0) + 1; # $f0=1, inherit bignum from $i
99 1142 my $f1 = $f0 + 1; # $f1=2, inherit bignum from $i
100 1142 ▶ while ($f0 <= $i-$f1) {
Branch: 1 branch
BranchTrueFalseTotal
if ($f0 <= $i - $f1) 9520 1142 10662
101 9520 push @fibs, $f0;
102 9520 ($f1,$f0) = ($f1+$f0,$f1);
103 }
104 ### @fibs
105 ### $f0
106 ### $f1
107  
108 # here have f1 <= i < f0+f1
109 # subtract i+1 - f1
110 1142 $i -= $f1;
111 1142 $i += 1;
112 ### i+1 - f1: $i
113  
114 # If i+1-f1 >= f0 then high fib is not the f1 just subtracted but
115 # instead f2=f1+f0. Subtract also f0 so i+1 - (f1+f0). Now skip f1
116 # since the Zeck form has no consecutive fibs. Push f0 onto @fibs to be
117 # the next fib tested in the loop.
118 #
119 # Actually i+1-(f1+f0) = 0 here, since f1 <= i and f0+f1 <= i+1 means
120 # i+1==f0+f1 exactly. Could return r += $#fibs/2 which is the effect of
121 # every second 0-bit step, but i+1=fibonacci will be fairly rare.
122 #
123 # If i+1-f1 < f0 then high fib is f1 just subtracted. Now skip f0 since
124 # the Zeck form has no consecutive fibs.
125 #
126 1142 ▶ if ($i >= $f0) {
Branch: 1 branch
BranchTrueFalseTotal
if ($i >= $f0) 57 1085 1142
127 57 return (1, int(scalar(@fibs)/2) + 2);
128  
129 # $i -= $f0;
130 # ### subtract f0, so i+1 sub f2=f1+f0: $i
131 # push @fibs, $f0;
132 }
133 }
134  
135 1085 my $r = 1; # R(0) = 1
136 1085 my $rplus1 = 1; # R(1) = 1
137 1085 my $odd_zeros = 1; # high zeck "10..." initial zero
138  
139 1085 ▶ while (my $f = pop @fibs) {
Branch: 1 branch
BranchTrueFalseTotal
if (my $f = pop @fibs) 7045 651 7696
140 ### at: "f=$f i=$i r=$r rplus1=$rplus1 odd_zeros=$odd_zeros"
141  
142 7045 ▶ if ($i < $f) {
Branch: 1 branch
BranchTrueFalseTotal
if ($i < $f) { } 4286 2759 7045
143 ### 0-bit ...
144  
145 4286 ▶ if ($odd_zeros) {
Branch: 1 branch
BranchTrueFalseTotal
if ($odd_zeros) 2776 1510 4286
146 ### odd zeros on i+1, add to rplus1 ...
147 2776 $rplus1 += $r;
148 }
149 4286 $odd_zeros ^= 1;
150  
151 } else {
152 2759 $i -= $f;
153 ### 1-bit sub: "$f to i=$i"
154  
155 2759 ▶ if ($odd_zeros) {
Branch: 1 branch
BranchTrueFalseTotal
if ($odd_zeros) { } 1723 1036 2759
156 ### odd zeros on i+1, add to r ...
157 1723 $r += $rplus1;
158 } else {
159 ### even zeros on i+1, r same as rplus1 ...
160 1036 $r = $rplus1;
161 }
162  
163 ### never consecutive fibs, so pop without comparing to i ...
164 2759 ▶ pop @fibs || last;
Branch: 1 branch
BranchTrueFalseTotal
pop @fibs or last 2325 434 2759
165 2325 $odd_zeros = 1; # one trailing 0-bit is odd
166 }
167 }
168  
169 ### final: "r=$r rplus1=$rplus1"
170 1085 return ($r, $rplus1);
171 }
172  
173 20 ▶sub pred {
Subroutine pred: called CC=2 SCAR=8.1
Pod documented
174 20 my ($self, $value) = @_;
175 ### FibonacciRepresentations pred(): $value
176 20 ▶ return ($value >= 1 && $value == int($value));
Condition33%1/3
$value >= 1 && $value == int $value
!ll&&!rl&&r
0020
MC/DC0%0/2
$value >= 1 && $value == int $value
$value >= 1 $value == int $value
Truth table33%1/3
A && B
A= $value >= 1B= $value == int $value
ABresult
0X0
100
111
177 }
178  
179 2 1;
180 __END__
« NumSeq/Abundant.pm ↑ Summary NumSeq/AlgebraicContinued.pm »