NumSeq/TotientSteps.pm untested

filter: Statementstmt 0.0% 0 / 87 Branchbran 0.0% 0 / 12 Conditioncond 0.0% 0 / 6 MC/DCmcdc 0.0% 0 / 4 Subroutinesub 0.0% 0 / 18 Podpod 0.0% 0 / 4 totaltotal 0.0% 0 / 131 CC 7 SCAR 25.1
CC
7
Cov
0%
ith
42.0
next
6.0
rewind
2.0
CRAP 12.3
1 # Copyright 2011, 2012, 2013, 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 package Math::NumSeq::TotientSteps;
19 use 5.004;
20 use strict;
21  
22 use vars '$VERSION', '@ISA';
23 $VERSION = 75;
24  
25 use Math::NumSeq;
26 use Math::NumSeq::Base::IterateIth;
27 @ISA = ('Math::NumSeq::Base::IterateIth',
28 'Math::NumSeq');
29 *_is_infinite = \&Math::NumSeq::_is_infinite;
30  
31 use Math::NumSeq::Totient;
32 *_totient = \&Math::NumSeq::Totient::_totient;
33  
34 use Math::NumSeq::PrimeFactorCount;;
35 *_prime_factors = \&Math::NumSeq::PrimeFactorCount::_prime_factors;
36  
37 # uncomment this to run the ### lines
38 #use Devel::Comments;
39  
40  
41 # use constant name => Math::NumSeq::__('Totient Steps');
42 use constant description => Math::NumSeq::__('Number of repeated applications of the totient function to reach 1.');
43 use constant characteristic_count => 1;
44 use constant characteristic_smaller => 1;
45 use constant characteristic_increasing => 0;
46 use constant values_min => 0; # at i=1
47 use constant i_start => 1;
48 use constant oeis_anum => 'A003434';
49  
50  
51  
52 sub rewind {
53 my ($self) = @_;
54 $self->{'i'} = $self->i_start;
55 }
56 sub next {
57 my ($self) = @_;
58  
59 my $v = my $i = $self->{'i'}++;
60 my $count = 0;
61 for (;;) {
62 if ($v <= 1) {
63 return ($i, $count);
64 }
65 $v = _totient($v);
66 $count++;
67 }
68 }
69  
70  
71 sub ith {
72 my ($self, $i) = @_;
73 ### TotientSteps ith(): $i
74  
75 if ($i < 0) {
76 return undef;
77 }
78 if (_is_infinite($i)) {
79 return $i;
80 }
81  
82 my ($good, @primes) = _prime_factors($i);
83 return undef unless $good;
84  
85 my %primes;
86 foreach my $p (@primes) {
87 $primes{$p}++;
88 }
89  
90 my %prime_factors;
91 my $count = 0;
92 while (%primes) {
93 ### %primes
94 $count++;
95  
96 my %next;
97 while (my ($p, $e) = each %primes) {
98 if (--$e) {
99 $next{$p} += $e;
100 }
101 my $prime_factors_aref = ($prime_factors{$p} ||= do {
102 my ($good, @primes) = _prime_factors($p-1);
103 return undef unless $good;
104 \@primes
105 });
106 foreach my $f (@$prime_factors_aref) {
107 $next{$f}++;
108 }
109 }
110  
111 %primes = %next;
112 }
113 return $count;
114 }
115  
116 sub pred {
117 my ($self, $value) = @_;
118 return ($value==int($value) && $value >= values_min());
119 }
120  
121 1;
122 __END__