| 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::PowerFlip; | ||||||||||||||||||||||||||||
| 19 | 2 | ▶ | use 5.004; | ||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||
| 20 | 2 | ▶ | use strict; | ||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||
| 21 | |||||||||||||||||||||||||||||
| 22 | 2 | ▶ | use vars '$VERSION', '@ISA'; | ||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||
| 23 | 2 | $VERSION = 75; | |||||||||||||||||||||||||||
| 24 | |||||||||||||||||||||||||||||
| 25 | 2 | ▶ | use Math::NumSeq; | ||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||
| 26 | 2 | ▶ | use Math::NumSeq::Base::IterateIth; | ||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||
| 27 | 2 | @ISA = ('Math::NumSeq::Base::IterateIth', | |||||||||||||||||||||||||||
| 28 | 'Math::NumSeq'); | ||||||||||||||||||||||||||||
| 29 | 2 | *_is_infinite = \&Math::NumSeq::_is_infinite; | |||||||||||||||||||||||||||
| 30 | 2 | *_to_bigint = \&Math::NumSeq::_to_bigint; | |||||||||||||||||||||||||||
| 31 | |||||||||||||||||||||||||||||
| 32 | 2 | ▶ | use Math::NumSeq::PrimeFactorCount;; | ||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||
| 33 | 2 | *_prime_factors = \&Math::NumSeq::PrimeFactorCount::_prime_factors; | |||||||||||||||||||||||||||
| 34 | |||||||||||||||||||||||||||||
| 35 | # uncomment this to run the ### lines | ||||||||||||||||||||||||||||
| 36 | #use Smart::Comments; | ||||||||||||||||||||||||||||
| 37 | |||||||||||||||||||||||||||||
| 38 | |||||||||||||||||||||||||||||
| 39 | 2 | ▶ | use constant name => Math::NumSeq::__('Prime Exponent Flip'); | ||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||
| 40 | 2 | ▶ | use constant description => Math::NumSeq::__('Flip each prime and its exponent, so for example 3^8 -> 8^3'); | ||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||
| 41 | 2 | ▶ | use constant default_i_start => 1; | ||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||
| 42 | 2 | ▶ | use constant characteristic_increasing => 0; | ||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||
| 43 | 2 | ▶ | use constant characteristic_non_decreasing => 0; | ||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||
| 44 | 2 | ▶ | use constant characteristic_integer => 1; | ||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||
| 45 | 2 | ▶ | use constant characteristic_smaller => 1; | ||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||
| 46 | 2 | ▶ | use constant values_min => 1; # at i=1 | ||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||
| 47 | |||||||||||||||||||||||||||||
| 48 | |||||||||||||||||||||||||||||
| 49 | #------------------------------------------------------------------------------ | ||||||||||||||||||||||||||||
| 50 | # cf A005117 squarefrees have all exponents 1 so value=1 | ||||||||||||||||||||||||||||
| 51 | # A013929 non-squarefrees have some exponent>1 so value>1 | ||||||||||||||||||||||||||||
| 52 | # A005361 product of exponents of prime factorization | ||||||||||||||||||||||||||||
| 53 | |||||||||||||||||||||||||||||
| 54 | 2 | ▶ | use constant oeis_anum => 'A008477'; | ||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||
| 55 | |||||||||||||||||||||||||||||
| 56 | #------------------------------------------------------------------------------ | ||||||||||||||||||||||||||||
| 57 | |||||||||||||||||||||||||||||
| 58 | 2 | ▶ | use constant 1.02 _UV_LIMIT => 31**2; # is value=2**31 | ||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||
| 59 | |||||||||||||||||||||||||||||
| 60 | 1079 | ▶ | sub ith { | ||||||||||||||||||||||||||
|
Subroutine
ith: called CC=8 SCAR=21.0
Pod
documented
| |||||||||||||||||||||||||||||
| 61 | 1079 | my ($self, $i) = @_; | |||||||||||||||||||||||||||
| 62 | ### PowerFlip ith(): $i | ||||||||||||||||||||||||||||
| 63 | |||||||||||||||||||||||||||||
| 64 | 1079 | ▶ | if (_is_infinite($i)) { | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 65 | 0 | return $i; | |||||||||||||||||||||||||||
| 66 | } | ||||||||||||||||||||||||||||
| 67 | 1079 | $i = abs($i); | |||||||||||||||||||||||||||
| 68 | |||||||||||||||||||||||||||||
| 69 | 1079 | my ($good, @primes) = _prime_factors($i); | |||||||||||||||||||||||||||
| 70 | 1079 | ▶ | return undef unless $good; | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 71 | |||||||||||||||||||||||||||||
| 72 | 1079 | ▶ | if (! @primes) { | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 73 | 9 | return $i; # 0,1 unchanged | |||||||||||||||||||||||||||
| 74 | } | ||||||||||||||||||||||||||||
| 75 | |||||||||||||||||||||||||||||
| 76 | 1070 | my $value = 1; | |||||||||||||||||||||||||||
| 77 | 1070 | my $log = 0; | |||||||||||||||||||||||||||
| 78 | |||||||||||||||||||||||||||||
| 79 | 1070 | for (;;) { | |||||||||||||||||||||||||||
| 80 | 3280 | ▶ | my $p = shift @primes || last; | ||||||||||||||||||||||||||
|
Condition100%2/2
shift @primes || (last)
MC/DC100%1/1
shift @primes || (last)
shift @primes
Truth table100%2/2
A
A= shift @primes
| |||||||||||||||||||||||||||||
| 81 | 2210 | my $count = 1; | |||||||||||||||||||||||||||
| 82 | 2210 | ▶ | while (@primes && $primes[0] == $p) { | ||||||||||||||||||||||||||
|
Branch: 1 branch
Condition100%3/3
@primes and $primes[0] == $p
MC/DC100%2/2
@primes and $primes[0] == $p
@primes
$primes[0] == $p
Truth table100%3/3
A and B
A= @primesB= $primes[0] == $p
| |||||||||||||||||||||||||||||
| 83 | 788 | shift @primes; | |||||||||||||||||||||||||||
| 84 | 788 | $count++; | |||||||||||||||||||||||||||
| 85 | } | ||||||||||||||||||||||||||||
| 86 | 2210 | $log += $p*log($count); | |||||||||||||||||||||||||||
| 87 | 2210 | ▶ | if ($log > 31) { | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 88 | 0 | $count = _to_bigint($count); | |||||||||||||||||||||||||||
| 89 | } | ||||||||||||||||||||||||||||
| 90 | 2210 | $value *= $count ** $p; | |||||||||||||||||||||||||||
| 91 | } | ||||||||||||||||||||||||||||
| 92 | 1070 | return $value; | |||||||||||||||||||||||||||
| 93 | } | ||||||||||||||||||||||||||||
| 94 | |||||||||||||||||||||||||||||
| 95 | 8 | ▶ | sub pred { | ||||||||||||||||||||||||||
|
Subroutine
pred: called CC=8 SCAR=23.2
Pod
documented
| |||||||||||||||||||||||||||||
| 96 | 8 | my ($self, $value) = @_; | |||||||||||||||||||||||||||
| 97 | ### PowerFlip pred(): $value | ||||||||||||||||||||||||||||
| 98 | |||||||||||||||||||||||||||||
| 99 | # ! is_square_free() | ||||||||||||||||||||||||||||
| 100 | |||||||||||||||||||||||||||||
| 101 | 8 | ▶ | unless ($value >= 0 && $value <= 0xFFFF_FFFF) { | ||||||||||||||||||||||||||
|
Branch: 1 branch
Condition33%1/3
$value >= 0 and $value <= 4294967295
MC/DC0%0/2
$value >= 0 and $value <= 4294967295
$value >= 0
$value <= 4294967295
Truth table33%1/3
A and B
A= $value >= 0B= $value <= 4294967295
| |||||||||||||||||||||||||||||
| 102 | 0 | return undef; | |||||||||||||||||||||||||||
| 103 | } | ||||||||||||||||||||||||||||
| 104 | 8 | ▶ | if ($value != int($value)) { | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 105 | 0 | return 0; | |||||||||||||||||||||||||||
| 106 | } | ||||||||||||||||||||||||||||
| 107 | 8 | $value = "$value"; # numize Math::BigInt for speed | |||||||||||||||||||||||||||
| 108 | |||||||||||||||||||||||||||||
| 109 | 8 | ▶ | if ($value < 2) { | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 110 | 6 | return 1; | |||||||||||||||||||||||||||
| 111 | } | ||||||||||||||||||||||||||||
| 112 | |||||||||||||||||||||||||||||
| 113 | 2 | my $limit = sqrt($value) + 1; | |||||||||||||||||||||||||||
| 114 | |||||||||||||||||||||||||||||
| 115 | 2 | ▶ | for (my $p = 2; $p <= $limit; $p += 2-($p==2)) { | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 116 | 3 | ▶ | next if ($value % $p); | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 117 | ### prime factor: $p | ||||||||||||||||||||||||||||
| 118 | 2 | $value /= $p; | |||||||||||||||||||||||||||
| 119 | |||||||||||||||||||||||||||||
| 120 | 2 | ▶ | if (($value % $p) == 0) { | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 121 | # found a square factor | ||||||||||||||||||||||||||||
| 122 | 2 | return 1; | |||||||||||||||||||||||||||
| 123 | } | ||||||||||||||||||||||||||||
| 124 | |||||||||||||||||||||||||||||
| 125 | 0 | $limit = sqrt($value) + 1; | |||||||||||||||||||||||||||
| 126 | ### divided out: "$p, new limit $limit" | ||||||||||||||||||||||||||||
| 127 | } | ||||||||||||||||||||||||||||
| 128 | |||||||||||||||||||||||||||||
| 129 | ### final: $value | ||||||||||||||||||||||||||||
| 130 | # $value now either 1 or a prime, no square factor found | ||||||||||||||||||||||||||||
| 131 | |||||||||||||||||||||||||||||
| 132 | 0 | return 0; | |||||||||||||||||||||||||||
| 133 | } | ||||||||||||||||||||||||||||
| 134 | |||||||||||||||||||||||||||||
| 135 | 2 | 1; | |||||||||||||||||||||||||||
| 136 | __END__ | ||||||||||||||||||||||||||||