| 1 | # Copyright 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::DedekindPsiCumulative; | ||||||||||
| 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::NumSeq::Primes; | ||||||||
|
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 | @ISA = ('Math::NumSeq'); | |||||||||
| 28 | |||||||||||
| 29 | 1 | ▶ | use Math::NumSeq::PrimeFactorCount;; | ||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||
| 30 | 1 | *_prime_factors = \&Math::NumSeq::PrimeFactorCount::_prime_factors; | |||||||||
| 31 | |||||||||||
| 32 | # uncomment this to run the ### lines | ||||||||||
| 33 | #use Smart::Comments; | ||||||||||
| 34 | |||||||||||
| 35 | |||||||||||
| 36 | # use constant name => Math::NumSeq::__('Dedekind Psi Cumulative'); | ||||||||||
| 37 | 1 | ▶ | use constant description => Math::NumSeq::__('Cumulative Dedekind Psi function.'); | ||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||
| 38 | 1 | ▶ | use constant default_i_start => 1; | ||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||
| 39 | 1 | ▶ | use constant characteristic_integer => 1; | ||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||
| 40 | 1 | ▶ | use constant characteristic_increasing => 1; | ||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||
| 41 | 1 | ▶ | use constant values_min => 1; | ||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||
| 42 | |||||||||||
| 43 | # A001615 dedekind psi | ||||||||||
| 44 | # A019268 dedekind psi first of n steps | ||||||||||
| 45 | # A019269 number of steps | ||||||||||
| 46 | # A173290 dedekind psi cumulative | ||||||||||
| 47 | # | ||||||||||
| 48 | 1 | ▶ | use constant oeis_anum => 'A173290'; | ||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||
| 49 | |||||||||||
| 50 | 3 | ▶ | sub rewind { | ||||||||
|
Subroutine
rewind: called CC=1 SCAR=0.0
Pod
documented
| |||||||||||
| 51 | 3 | my ($self) = @_; | |||||||||
| 52 | 3 | $self->{'i'} = $self->i_start; | |||||||||
| 53 | 3 | $self->{'total'} = 0; | |||||||||
| 54 | } | ||||||||||
| 55 | |||||||||||
| 56 | 24 | ▶ | sub next { | ||||||||
|
Subroutine
next: called CC=1 SCAR=0.0
Pod
documented
| |||||||||||
| 57 | 24 | my ($self) = @_; | |||||||||
| 58 | |||||||||||
| 59 | 24 | my $i = $self->{'i'}++; | |||||||||
| 60 | return ($i, | ||||||||||
| 61 | 24 | $self->{'total'} += _psi($i)); | |||||||||
| 62 | } | ||||||||||
| 63 | |||||||||||
| 64 | 24 | ▶ | sub _psi { | ||||||||
|
Subroutine
_psi: called CC=4 SCAR=13.9
| |||||||||||
| 65 | 24 | my ($n) = @_; | |||||||||
| 66 | ### _psi(): $n | ||||||||||
| 67 | 24 | my ($good, @primes) = _prime_factors($n); | |||||||||
| 68 | 24 | ▶ | return undef unless $good; | ||||||||
|
Branch: 1 branch
| |||||||||||
| 69 | |||||||||||
| 70 | 24 | my $prev = 0; | |||||||||
| 71 | 24 | foreach my $p (@primes) { | |||||||||
| 72 | 38 | ▶ | if ($p != $prev) { | ||||||||
|
Branch: 1 branch
| |||||||||||
| 73 | 28 | $n /= $p; | |||||||||
| 74 | 28 | $n *= $p+1; | |||||||||
| 75 | 28 | $prev = $p; | |||||||||
| 76 | } | ||||||||||
| 77 | } | ||||||||||
| 78 | ### $n | ||||||||||
| 79 | 24 | return $n; | |||||||||
| 80 | } | ||||||||||
| 81 | |||||||||||
| 82 | # v1.02 for leading underscore | ||||||||||
| 83 | 1 | ▶ | use constant 1.02 _PI => 4*atan2(1,1); # similar to Math::Complex pi() | ||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||
| 84 | |||||||||||
| 85 | # Enrique Pérez Herrero in the OEIS | ||||||||||
| 86 | # value = 15*n^2/(2*Pi^2) + O(n*log(n)) | ||||||||||
| 87 | # | ||||||||||
| 88 | # sqrt(value) = sqrt(15/2)/pi * n | ||||||||||
| 89 | # n = sqrt(value) * pi/sqrt(15/2) | ||||||||||
| 90 | # with pi/sqrt(15/2) ~= 39/34 for the benefit of Math::BigInt which can't | ||||||||||
| 91 | # do BigInt*flonum | ||||||||||
| 92 | # | ||||||||||
| 93 | # very close even neglecting n*log(n) | ||||||||||
| 94 | # | ||||||||||
| 95 | 21 | ▶ | sub value_to_i_estimate { | ||||||||
|
Subroutine
value_to_i_estimate: called CC=2 SCAR=6.9
Pod
documented
| |||||||||||
| 96 | 21 | my ($self, $value) = @_; | |||||||||
| 97 | 21 | ▶ | if ($value <= 1) { return 1; } | ||||||||
|
Branch: 1 branch
| |||||||||||
| 98 | 13 | return int (sqrt(int($value)) * 39/34); | |||||||||
| 99 | } | ||||||||||
| 100 | |||||||||||
| 101 | 1 | 1; | |||||||||
| 102 | __END__ | ||||||||||