| 1 | # Copyright 2012, 2013, 2014, 2016, 2018, 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 | |||||||||||||||||||||||||||||
| 19 | # http://mathworld.wolfram.com/DeletablePrime.html | ||||||||||||||||||||||||||||
| 20 | # | ||||||||||||||||||||||||||||
| 21 | |||||||||||||||||||||||||||||
| 22 | |||||||||||||||||||||||||||||
| 23 | package Math::NumSeq::DeletablePrimes; | ||||||||||||||||||||||||||||
| 24 | 2 | ▶ | use 5.004; | ||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||
| 25 | 2 | ▶ | use strict; | ||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||
| 26 | 2 | ▶ | use Math::Prime::XS 0.23 'is_prime'; # version 0.23 fix for 1928099 | ||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||
| 27 | |||||||||||||||||||||||||||||
| 28 | 2 | ▶ | use vars '$VERSION', '@ISA'; | ||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||
| 29 | 2 | $VERSION = 75; | |||||||||||||||||||||||||||
| 30 | |||||||||||||||||||||||||||||
| 31 | 2 | ▶ | use Math::NumSeq; | ||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||
| 32 | 2 | ▶ | use Math::NumSeq::Primes; | ||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||
| 33 | 2 | @ISA = ('Math::NumSeq'); | |||||||||||||||||||||||||||
| 34 | 2 | *_is_infinite = \&Math::NumSeq::_is_infinite; | |||||||||||||||||||||||||||
| 35 | |||||||||||||||||||||||||||||
| 36 | # uncomment this to run the ### lines | ||||||||||||||||||||||||||||
| 37 | #use Smart::Comments; | ||||||||||||||||||||||||||||
| 38 | |||||||||||||||||||||||||||||
| 39 | |||||||||||||||||||||||||||||
| 40 | # use constant name => Math::NumSeq::__('Deletable Primes'); | ||||||||||||||||||||||||||||
| 41 | 2 | ▶ | use constant description => Math::NumSeq::__('Deletable primes, being primes where deleting a digit gives another prime from which in turn a digit can be deleted, etc.'); | ||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||
| 42 | 2 | ▶ | use constant i_start => 1; | ||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||
| 43 | 2 | ▶ | use constant characteristic_increasing => 1; | ||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||
| 44 | 2 | ▶ | use constant values_min => 2; | ||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||
| 45 | |||||||||||||||||||||||||||||
| 46 | use Math::NumSeq::Base::Digits | ||||||||||||||||||||||||||||
| 47 | 2 | ▶ | 'parameter_info_array'; # radix parameter | ||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||
| 48 | |||||||||||||||||||||||||||||
| 49 | |||||||||||||||||||||||||||||
| 50 | #------------------------------------------------------------------------------ | ||||||||||||||||||||||||||||
| 51 | |||||||||||||||||||||||||||||
| 52 | # cf A080603 deleting a digit leaves a prime | ||||||||||||||||||||||||||||
| 53 | # A179336 primes containing at least one prime digit | ||||||||||||||||||||||||||||
| 54 | # a superset of the deletables | ||||||||||||||||||||||||||||
| 55 | # | ||||||||||||||||||||||||||||
| 56 | # http://mathworld.wolfram.com/TruncatablePrime.html | ||||||||||||||||||||||||||||
| 57 | # A024770 left truncatable primes | ||||||||||||||||||||||||||||
| 58 | # A024785 left truncatable primes, no zero digits | ||||||||||||||||||||||||||||
| 59 | # A077390 left-and-right truncatable primes | ||||||||||||||||||||||||||||
| 60 | # A137812 left or right truncatable primes | ||||||||||||||||||||||||||||
| 61 | # finite 149677 elements to 8939662423123592347173339993799 | ||||||||||||||||||||||||||||
| 62 | # | ||||||||||||||||||||||||||||
| 63 | 2 | my @oeis_anum; | |||||||||||||||||||||||||||
| 64 | |||||||||||||||||||||||||||||
| 65 | 2 | $oeis_anum[2] = 'A096246'; | |||||||||||||||||||||||||||
| 66 | # $oeis_anum[3] = 'A319596'; # PENDING exclude 3 maybe | ||||||||||||||||||||||||||||
| 67 | 2 | $oeis_anum[4] = 'A321657'; | |||||||||||||||||||||||||||
| 68 | 2 | $oeis_anum[5] = 'A321700'; | |||||||||||||||||||||||||||
| 69 | 2 | $oeis_anum[10] = 'A080608'; | |||||||||||||||||||||||||||
| 70 | # OEIS-Catalogue: A096246 radix=2 | ||||||||||||||||||||||||||||
| 71 | # OEIS-Catalogue: A321657 radix=4 | ||||||||||||||||||||||||||||
| 72 | # OEIS-Catalogue: A321700 radix=5 | ||||||||||||||||||||||||||||
| 73 | # OEIS-Catalogue: A080608 | ||||||||||||||||||||||||||||
| 74 | |||||||||||||||||||||||||||||
| 75 | 2 | ▶ | sub oeis_anum { | ||||||||||||||||||||||||||
|
Subroutine
oeis_anum: called CC=1 SCAR=0.0
Pod
documented
| |||||||||||||||||||||||||||||
| 76 | 2 | my ($self) = @_; | |||||||||||||||||||||||||||
| 77 | 2 | return $oeis_anum[$self->{'radix'}]; | |||||||||||||||||||||||||||
| 78 | } | ||||||||||||||||||||||||||||
| 79 | |||||||||||||||||||||||||||||
| 80 | # base=3 | ||||||||||||||||||||||||||||
| 81 | # 3 = 10 from 100 = 9 | ||||||||||||||||||||||||||||
| 82 | # 101 = 10 | ||||||||||||||||||||||||||||
| 83 | # 102 = 11 prime, but delete 0 to 12 = 5 then del 1 to 2 | ||||||||||||||||||||||||||||
| 84 | # 110 = 12 | ||||||||||||||||||||||||||||
| 85 | # 120 = 15 | ||||||||||||||||||||||||||||
| 86 | # fromdigits([1,2,0],3) | ||||||||||||||||||||||||||||
| 87 | |||||||||||||||||||||||||||||
| 88 | |||||||||||||||||||||||||||||
| 89 | #------------------------------------------------------------------------------ | ||||||||||||||||||||||||||||
| 90 | |||||||||||||||||||||||||||||
| 91 | 8 | ▶ | sub rewind { | ||||||||||||||||||||||||||
|
Subroutine
rewind: called CC=1 SCAR=0.0
Pod
documented
| |||||||||||||||||||||||||||||
| 92 | 8 | my ($self) = @_; | |||||||||||||||||||||||||||
| 93 | 8 | $self->{'i'} = $self->i_start; | |||||||||||||||||||||||||||
| 94 | 8 | my $primes_seq = $self->{'primes_seq'} = Math::NumSeq::Primes->new; | |||||||||||||||||||||||||||
| 95 | } | ||||||||||||||||||||||||||||
| 96 | |||||||||||||||||||||||||||||
| 97 | 28 | ▶ | sub next { | ||||||||||||||||||||||||||
|
Subroutine
next: called CC=3 SCAR=11.0
Pod
documented
| |||||||||||||||||||||||||||||
| 98 | 28 | my ($self) = @_; | |||||||||||||||||||||||||||
| 99 | 28 | my $primes_seq = $self->{'primes_seq'}; | |||||||||||||||||||||||||||
| 100 | 28 | for (;;) { | |||||||||||||||||||||||||||
| 101 | 34 | ▶ | (undef, my $prime) = $primes_seq->next | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 102 | or return; | ||||||||||||||||||||||||||||
| 103 | 34 | ▶ | if (_prime_is_deletable($self,$prime)) { | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 104 | 28 | return ($self->{'i'}++, $prime); | |||||||||||||||||||||||||||
| 105 | } | ||||||||||||||||||||||||||||
| 106 | } | ||||||||||||||||||||||||||||
| 107 | } | ||||||||||||||||||||||||||||
| 108 | |||||||||||||||||||||||||||||
| 109 | 94 | ▶ | sub pred { | ||||||||||||||||||||||||||
|
Subroutine
pred: called CC=2 SCAR=6.9
Pod
documented
| |||||||||||||||||||||||||||||
| 110 | 94 | my ($self, $value) = @_; | |||||||||||||||||||||||||||
| 111 | ### pred(): $value | ||||||||||||||||||||||||||||
| 112 | 94 | ▶ | return ($self->Math::NumSeq::Primes::pred($value) | ||||||||||||||||||||||||||
|
Condition100%3/3
$self->Math::NumSeq::Primes::pred($value) && _prime_is_deletable($self, $value)
MC/DC100%2/2
$self->Math::NumSeq::Primes::pred($value) && _prime_is_deletable($self, $value)
$self->Math::NumSeq::Primes::pred($value)
_prime_is_deletable($self, $value)
Truth table100%3/3
A && B
A= $self->Math::NumSeq::Primes::pred($value)B= _prime_is_deletable($self, $value)
| |||||||||||||||||||||||||||||
| 113 | && _prime_is_deletable($self,$value)); | ||||||||||||||||||||||||||||
| 114 | } | ||||||||||||||||||||||||||||
| 115 | |||||||||||||||||||||||||||||
| 116 | 67 | ▶ | sub _prime_is_deletable { | ||||||||||||||||||||||||||
|
Subroutine
_prime_is_deletable: called CC=13 SCAR=25.6
| |||||||||||||||||||||||||||||
| 117 | 67 | my ($self, @pending) = @_; | |||||||||||||||||||||||||||
| 118 | |||||||||||||||||||||||||||||
| 119 | 67 | my $radix = $self->{'radix'}; | |||||||||||||||||||||||||||
| 120 | 67 | ▶ | my $target = ($radix == 2 ? 4 : $radix); | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 121 | |||||||||||||||||||||||||||||
| 122 | 67 | ▶ | while (@pending) { | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 123 | ### pending: join(', ',map{sprintf "%b", $_}@pending) | ||||||||||||||||||||||||||||
| 124 | |||||||||||||||||||||||||||||
| 125 | 107 | my $value = pop @pending; | |||||||||||||||||||||||||||
| 126 | 107 | ▶ | next unless is_prime($value); | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 127 | 83 | ▶ | if ($value < $target) { | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 128 | ### reached single digit, or 2,3 for binary ... | ||||||||||||||||||||||||||||
| 129 | 56 | return 1; | |||||||||||||||||||||||||||
| 130 | } | ||||||||||||||||||||||||||||
| 131 | |||||||||||||||||||||||||||||
| 132 | 27 | my $prev = -1; | |||||||||||||||||||||||||||
| 133 | 27 | ▶ | if ($radix == 10) { | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 134 | 19 | ▶ | foreach my $i (($value =~ /^.(0+)/ ? length($1) : 0) | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 135 | .. | ||||||||||||||||||||||||||||
| 136 | length($value)-1) { | ||||||||||||||||||||||||||||
| 137 | 38 | my $digit = substr($value,$i,1); | |||||||||||||||||||||||||||
| 138 | 38 | ▶ | next if $digit eq $prev; | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 139 | 35 | $prev = $digit; | |||||||||||||||||||||||||||
| 140 | 35 | push @pending, substr($value,0,$i) . substr($value,$i+1); | |||||||||||||||||||||||||||
| 141 | } | ||||||||||||||||||||||||||||
| 142 | } else { | ||||||||||||||||||||||||||||
| 143 | |||||||||||||||||||||||||||||
| 144 | 8 | ▶ | for (my $pow = 1; $value > $pow; $pow *= $radix) { | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 145 | 21 | my $low = $value % $pow; | |||||||||||||||||||||||||||
| 146 | 21 | my $high = int($value/$pow); | |||||||||||||||||||||||||||
| 147 | |||||||||||||||||||||||||||||
| 148 | 21 | my $digit = $high % $radix; # being deleted | |||||||||||||||||||||||||||
| 149 | 21 | ▶ | last if $high < $radix && $prev == 0; # don't delete high,0,... | ||||||||||||||||||||||||||
|
Branch: 1 branch
Condition100%3/3
$high < $radix and $prev == 0
MC/DC100%2/2
$high < $radix and $prev == 0
$high < $radix
$prev == 0
Truth table100%3/3
A and B
A= $high < $radixB= $prev == 0
| |||||||||||||||||||||||||||||
| 150 | 20 | ▶ | next if $digit eq $prev; | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 151 | 13 | $prev = $digit; | |||||||||||||||||||||||||||
| 152 | |||||||||||||||||||||||||||||
| 153 | |||||||||||||||||||||||||||||
| 154 | 13 | push @pending, int($high/$radix) * $pow + $low; | |||||||||||||||||||||||||||
| 155 | } | ||||||||||||||||||||||||||||
| 156 | } | ||||||||||||||||||||||||||||
| 157 | } | ||||||||||||||||||||||||||||
| 158 | 11 | return 0; | |||||||||||||||||||||||||||
| 159 | } | ||||||||||||||||||||||||||||
| 160 | |||||||||||||||||||||||||||||
| 161 | 2 | 1; | |||||||||||||||||||||||||||
| 162 | __END__ | ||||||||||||||||||||||||||||