| 1 | # Copyright2011, 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 | package Math::NumSeq::Primorials; | ||||||||||||||||||||||||||||
| 19 | 1 | ▶ | use 5.004; | ||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||
| 20 | 1 | ▶ | use strict; | ||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||
| 21 | 1 | ▶ | use Math::Prime::XS; | ||||||||||||||||||||||||||
|
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 | 1 | ▶ | use Math::NumSeq; | ||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||
| 26 | 1 | @ISA = ('Math::NumSeq'); | |||||||||||||||||||||||||||
| 27 | 1 | *_is_infinite = \&Math::NumSeq::_is_infinite; | |||||||||||||||||||||||||||
| 28 | |||||||||||||||||||||||||||||
| 29 | # use constant name => Math::NumSeq::__('Primorials'); | ||||||||||||||||||||||||||||
| 30 | 1 | ▶ | use constant description => Math::NumSeq::__('The primorials 1, 2, 6, 30, 210, etc, 2*3*5*7*...Prime(n).'); | ||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||
| 31 | 1 | ▶ | use constant i_start => 0; | ||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||
| 32 | 1 | ▶ | use constant characteristic_increasing => 1; | ||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||
| 33 | 1 | ▶ | use constant characteristic_integer => 1; | ||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||
| 34 | 1 | ▶ | use constant values_min => 1; | ||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||
| 35 | |||||||||||||||||||||||||||||
| 36 | # cf A034386 product of primes p <= i, so repeating 1, 2, 6, 6, 30, 30, | ||||||||||||||||||||||||||||
| 37 | # A143293 partial sums of primorials | ||||||||||||||||||||||||||||
| 38 | # | ||||||||||||||||||||||||||||
| 39 | 1 | ▶ | use constant oeis_anum => 'A002110'; # starting at 1 | ||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||
| 40 | |||||||||||||||||||||||||||||
| 41 | # uncomment this to run the ### lines | ||||||||||||||||||||||||||||
| 42 | #use Devel::Comments; | ||||||||||||||||||||||||||||
| 43 | |||||||||||||||||||||||||||||
| 44 | 1 | ▶ | use constant 1.02; # for leading underscore | ||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||
| 45 | 1 | ▶ | use constant _UV_LIMIT => do { | ||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=3 SCAR=11.0
| |||||||||||||||||||||||||||||
| 46 | 1 | my $u = ~0 >> 1; | |||||||||||||||||||||||||||
| 47 | 1 | my $limit = 1; | |||||||||||||||||||||||||||
| 48 | 1 | for my $p (Math::Prime::XS::sieve_primes(100)) { | |||||||||||||||||||||||||||
| 49 | ### $p | ||||||||||||||||||||||||||||
| 50 | 16 | ▶ | if ($u < $p) { | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 51 | ### _UV_LIMIT stop before prime: "p=$p" | ||||||||||||||||||||||||||||
| 52 | 1 | last; | |||||||||||||||||||||||||||
| 53 | } | ||||||||||||||||||||||||||||
| 54 | 15 | $u -= ($u % $p); | |||||||||||||||||||||||||||
| 55 | 15 | $u /= $p; | |||||||||||||||||||||||||||
| 56 | 15 | $limit *= $p; | |||||||||||||||||||||||||||
| 57 | } | ||||||||||||||||||||||||||||
| 58 | $limit | ||||||||||||||||||||||||||||
| 59 | 1 | }; | |||||||||||||||||||||||||||
| 60 | ### _UV_LIMIT: _UV_LIMIT() | ||||||||||||||||||||||||||||
| 61 | |||||||||||||||||||||||||||||
| 62 | 3 | ▶ | sub rewind { | ||||||||||||||||||||||||||
|
Subroutine
rewind: called CC=1 SCAR=0.0
Pod
documented
| |||||||||||||||||||||||||||||
| 63 | 3 | my ($self) = @_; | |||||||||||||||||||||||||||
| 64 | ### Primorials rewind() | ||||||||||||||||||||||||||||
| 65 | 3 | $self->{'prime'} = 1; | |||||||||||||||||||||||||||
| 66 | 3 | $self->{'i'} = $self->i_start; | |||||||||||||||||||||||||||
| 67 | 3 | $self->{'f'} = 1; | |||||||||||||||||||||||||||
| 68 | } | ||||||||||||||||||||||||||||
| 69 | 10 | ▶ | sub next { | ||||||||||||||||||||||||||
|
Subroutine
next: called CC=5 SCAR=16.6
Pod
documented
| |||||||||||||||||||||||||||||
| 70 | 10 | my ($self) = @_; | |||||||||||||||||||||||||||
| 71 | ### Primorials next() ... | ||||||||||||||||||||||||||||
| 72 | |||||||||||||||||||||||||||||
| 73 | 10 | ▶ | if (my $i = $self->{'i'}++) { | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 74 | 8 | my $f = $self->{'f'}; | |||||||||||||||||||||||||||
| 75 | 8 | ▶ | if ($f >= _UV_LIMIT && ! ref $f) { | ||||||||||||||||||||||||||
|
Branch: 1 branch
Condition33%1/3
$f >= '614889782588491410' and not ref $f
MC/DC0%0/2
$f >= '614889782588491410' and not ref $f
$f >= '614889782588491410'
not ref $f
Truth table33%1/3
A and not(B)
A= $f >= '614889782588491410'B= not ref $f
| |||||||||||||||||||||||||||||
| 76 | 0 | $self->{'f'} = Math::NumSeq::_to_bigint($f); | |||||||||||||||||||||||||||
| 77 | } | ||||||||||||||||||||||||||||
| 78 | 8 | my $prime; | |||||||||||||||||||||||||||
| 79 | 8 | ▶ | do { | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 80 | 14 | $prime = $self->{'prime'}++; | |||||||||||||||||||||||||||
| 81 | } until (Math::Prime::XS::is_prime($prime)); | ||||||||||||||||||||||||||||
| 82 | 8 | return ($i, $self->{'f'} *= $prime); | |||||||||||||||||||||||||||
| 83 | |||||||||||||||||||||||||||||
| 84 | } else { | ||||||||||||||||||||||||||||
| 85 | 2 | return (0, 1); | |||||||||||||||||||||||||||
| 86 | } | ||||||||||||||||||||||||||||
| 87 | } | ||||||||||||||||||||||||||||
| 88 | |||||||||||||||||||||||||||||
| 89 | 18 | ▶ | sub ith { | ||||||||||||||||||||||||||
|
Subroutine
ith: called CC=6 SCAR=18.0
Pod
documented
| |||||||||||||||||||||||||||||
| 90 | 18 | my ($self, $i) = @_; | |||||||||||||||||||||||||||
| 91 | ### Primorials ith(): $i | ||||||||||||||||||||||||||||
| 92 | 18 | ▶ | if (_is_infinite($i)) { | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 93 | 0 | return $i; | |||||||||||||||||||||||||||
| 94 | } | ||||||||||||||||||||||||||||
| 95 | 18 | my $f = 1; | |||||||||||||||||||||||||||
| 96 | 18 | my $prime = 1; | |||||||||||||||||||||||||||
| 97 | 18 | ▶ | while ($i-- > 0) { | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 98 | 128 | ▶ | if ($f >= _UV_LIMIT && ! ref $f) { | ||||||||||||||||||||||||||
|
Branch: 1 branch
Condition100%3/3
$f >= '614889782588491410' and not ref $f
MC/DC100%2/2
$f >= '614889782588491410' and not ref $f
$f >= '614889782588491410'
not ref $f
Truth table100%3/3
A and not(B)
A= $f >= '614889782588491410'B= not ref $f
| |||||||||||||||||||||||||||||
| 99 | 1 | $f = Math::NumSeq::_to_bigint($f); | |||||||||||||||||||||||||||
| 100 | } | ||||||||||||||||||||||||||||
| 101 | 128 | ▶ | until (Math::Prime::XS::is_prime(++$prime)) {} | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 102 | 128 | $f *= $prime; | |||||||||||||||||||||||||||
| 103 | } | ||||||||||||||||||||||||||||
| 104 | 18 | return $f; | |||||||||||||||||||||||||||
| 105 | } | ||||||||||||||||||||||||||||
| 106 | |||||||||||||||||||||||||||||
| 107 | 424 | ▶ | sub pred { | ||||||||||||||||||||||||||
|
Subroutine
pred: called CC=5 SCAR=16.1
Pod
documented
| |||||||||||||||||||||||||||||
| 108 | 424 | my ($self, $value) = @_; | |||||||||||||||||||||||||||
| 109 | ### Primorials pred() | ||||||||||||||||||||||||||||
| 110 | 424 | my $prime = 2; | |||||||||||||||||||||||||||
| 111 | 424 | for (;;) { | |||||||||||||||||||||||||||
| 112 | 566 | ▶ | if ($value <= 1) { | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 113 | 10 | return ($value == 1); | |||||||||||||||||||||||||||
| 114 | } | ||||||||||||||||||||||||||||
| 115 | 556 | ▶ | if ($value % $prime) { | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 116 | 296 | return 0; # not divisible by this prime | |||||||||||||||||||||||||||
| 117 | } | ||||||||||||||||||||||||||||
| 118 | |||||||||||||||||||||||||||||
| 119 | 260 | $value /= $prime; | |||||||||||||||||||||||||||
| 120 | 260 | ▶ | if (($value % $prime) == 0) { | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 121 | 118 | return 0; # doubled prime factor | |||||||||||||||||||||||||||
| 122 | } | ||||||||||||||||||||||||||||
| 123 | |||||||||||||||||||||||||||||
| 124 | 142 | ▶ | until (Math::Prime::XS::is_prime(++$prime)) {} # next $prime | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 125 | } | ||||||||||||||||||||||||||||
| 126 | } | ||||||||||||||||||||||||||||
| 127 | |||||||||||||||||||||||||||||
| 128 | 43 | ▶ | sub value_to_i_floor { | ||||||||||||||||||||||||||
|
Subroutine
value_to_i_floor: called CC=5 SCAR=16.1
Pod
documented
| |||||||||||||||||||||||||||||
| 129 | 43 | my ($self, $value) = @_; | |||||||||||||||||||||||||||
| 130 | 43 | ▶ | if (_is_infinite($value)) { | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 131 | 0 | return $value; | |||||||||||||||||||||||||||
| 132 | } | ||||||||||||||||||||||||||||
| 133 | 43 | ▶ | if ($value < 2) { | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 134 | 17 | return $self->i_start; | |||||||||||||||||||||||||||
| 135 | } | ||||||||||||||||||||||||||||
| 136 | |||||||||||||||||||||||||||||
| 137 | 26 | my $i = 0; | |||||||||||||||||||||||||||
| 138 | 26 | my $prime = 2; | |||||||||||||||||||||||||||
| 139 | 26 | for (;;) { | |||||||||||||||||||||||||||
| 140 | ### $value | ||||||||||||||||||||||||||||
| 141 | ### $i | ||||||||||||||||||||||||||||
| 142 | |||||||||||||||||||||||||||||
| 143 | 87 | ▶ | if ($value < $prime) { | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 144 | 26 | return $i; | |||||||||||||||||||||||||||
| 145 | } | ||||||||||||||||||||||||||||
| 146 | 61 | $value = int($value/$prime); | |||||||||||||||||||||||||||
| 147 | |||||||||||||||||||||||||||||
| 148 | 61 | $i++; | |||||||||||||||||||||||||||
| 149 | 61 | ▶ | until (Math::Prime::XS::is_prime(++$prime)) {} # next $prime | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 150 | } | ||||||||||||||||||||||||||||
| 151 | } | ||||||||||||||||||||||||||||
| 152 | |||||||||||||||||||||||||||||
| 153 | # ENHANCE-ME: maybe a slightly squashed down log() would be close enough | ||||||||||||||||||||||||||||
| 154 | # | ||||||||||||||||||||||||||||
| 155 | 1 | *value_to_i_estimate = \&value_to_i_floor; | |||||||||||||||||||||||||||
| 156 | |||||||||||||||||||||||||||||
| 157 | 1 | 1; | |||||||||||||||||||||||||||
| 158 | __END__ | ||||||||||||||||||||||||||||