File Coverage

blib/lib/Math/NumSeq/DedekindPsiSteps.pm
Criterion Covered Total %
statement 66 67 98.5
branch 9 12 75.0
condition 2 3 66.6
subroutine 14 14 100.0
pod 1 1 100.0
total 92 97 94.8


line stmt bran cond sub pod time code
1             # Copyright 2012, 2013, 2014 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 .
17              
18             package Math::NumSeq::DedekindPsiSteps;
19 1     1   871 use 5.004;
  1         2  
20 1     1   3 use strict;
  1         1  
  1         18  
21              
22 1     1   3 use vars '$VERSION', '@ISA';
  1         1  
  1         49  
23             $VERSION = 72;
24              
25 1     1   4 use Math::NumSeq;
  1         1  
  1         16  
26 1     1   2 use Math::NumSeq::Base::IterateIth;
  1         2  
  1         35  
27             @ISA = ('Math::NumSeq::Base::IterateIth',
28             'Math::NumSeq');
29             *_is_infinite = \&Math::NumSeq::_is_infinite;
30              
31 1     1   3 use Math::NumSeq::PrimeFactorCount;;
  1         1  
  1         29  
32             *_prime_factors = \&Math::NumSeq::PrimeFactorCount::_prime_factors;
33              
34             # uncomment this to run the ### lines
35             #use Smart::Comments;
36              
37              
38             # use constant name => Math::NumSeq::__('Dedekind Psi Steps');
39 1     1   3 use constant description => Math::NumSeq::__('Number of repeated applications of the Dedekind psi function to reach factors 2 and 3 only.');
  1         5  
  1         4  
40 1     1   3 use constant default_i_start => 1;
  1         2  
  1         36  
41 1     1   3 use constant characteristic_count => 1;
  1         1  
  1         30  
42 1     1   3 use constant characteristic_smaller => 1;
  1         2  
  1         32  
43 1     1   3 use constant characteristic_increasing => 0;
  1         1  
  1         33  
44 1     1   3 use constant values_min => 0;
  1         1  
  1         34  
45              
46             # A001615 dedekind psi
47             # A019268 dedekind psi first requiring n steps
48             # A019269 number of steps
49             # A173290 dedekind psi cumulative
50             #
51 1     1   4 use constant oeis_anum => 'A019269';
  1         0  
  1         214  
52              
53             sub ith {
54 108     108 1 110 my ($self, $i) = @_;
55             ### DedekindPsiSteps ith(): $i
56              
57 108 50       139 if (_is_infinite($i)) {
58 0         0 return $i;
59             }
60 108 100       142 if ($i < 0) {
61 3         5 return undef;
62             }
63              
64 105         139 my ($good, @primes) = _prime_factors($i);
65 105 50       128 return undef unless $good;
66              
67 105         69 my %primes;
68 105         107 foreach my $p (@primes) {
69 176         219 $primes{$p}++;
70             }
71 105         66 my $count = 0;
72              
73 105         72 my %prime_factors;
74 105         61 for (;;) {
75 143         112 delete $primes{'2'};
76 143         81 delete $primes{'3'};
77 143 100       183 last unless %primes;
78              
79             ### %primes
80 38         29 $count++;
81 38         22 my %next_primes;
82 38         73 while (my ($p, $e) = each %primes) {
83 38 100       51 if (--$e) {
84 1         1 $next_primes{$p} += $e;
85             }
86 38   66     61 my $prime_factors_aref = ($prime_factors{$p} ||= do {
87 37         71 my ($good, @primes) = _prime_factors($p+1);
88 37 50       51 return undef unless $good;
89             \@primes
90 37         69 });
91 38         36 foreach my $f (@$prime_factors_aref) {
92 88         148 $next_primes{$f}++;
93             }
94             }
95 38         67 %primes = %next_primes;
96             }
97 105         240 return $count;
98             }
99              
100             # sub _psi_ex23 {
101             # my ($n) = @_;
102             # ### _psi(): $n
103             #
104             # my $prev = 0;
105             # my $ret = 1;
106             # foreach my $p (prime_factors($n)) {
107             # next if $p == 2 || $p == 3;
108             # if ($p == $prev) {
109             # $ret *= $p;
110             # } else {
111             # $ret *= $p+1;
112             # $prev = $p;
113             # }
114             # }
115             # return $ret;
116             #
117             # # my %primes;
118             # # @primes{prime_factors($n)} = (); # hash slice
119             # # delete $primes{2,3}; # hash slice
120             # # foreach my $p (keys %primes) {
121             # # $n /= $p;
122             # # $n *= $p+1;
123             # # }
124             # return $n;
125             # }
126              
127             # sub _is_2x3y {
128             # my ($n) = @_;
129             # until ($n % 2) {
130             # $n = int($n/2);
131             # }
132             # until ($n % 3) {
133             # $n = int($n/3);
134             # }
135             # return ($n == 1);
136             # }
137              
138             1;
139             __END__