| 1 | # Copyright 2010, 2011, 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 | |||||||||||||||||||||||||||||||||||||||||||
| 19 | # cf | ||||||||||||||||||||||||||||||||||||||||||
| 20 | # http://mathworld.wolfram.com/dePolignacsConjecture.html | ||||||||||||||||||||||||||||||||||||||||||
| 21 | # consecutive primes difference is every even number infinitely many times | ||||||||||||||||||||||||||||||||||||||||||
| 22 | |||||||||||||||||||||||||||||||||||||||||||
| 23 | # 1, | ||||||||||||||||||||||||||||||||||||||||||
| 24 | # 127, 149, 251, 331, | ||||||||||||||||||||||||||||||||||||||||||
| 25 | # 337, 373, 509, 599, | ||||||||||||||||||||||||||||||||||||||||||
| 26 | # 701, 757, 809, 877, | ||||||||||||||||||||||||||||||||||||||||||
| 27 | # 905, 907, 959, 977, | ||||||||||||||||||||||||||||||||||||||||||
| 28 | # 997, | ||||||||||||||||||||||||||||||||||||||||||
| 29 | |||||||||||||||||||||||||||||||||||||||||||
| 30 | package Math::NumSeq::PolignacObstinate; | ||||||||||||||||||||||||||||||||||||||||||
| 31 | 2 | ▶ | use 5.004; | ||||||||||||||||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||||||||||||||||
| 32 | 2 | ▶ | use strict; | ||||||||||||||||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||||||||||||||||
| 33 | |||||||||||||||||||||||||||||||||||||||||||
| 34 | 2 | ▶ | use vars '$VERSION', '@ISA'; | ||||||||||||||||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||||||||||||||||
| 35 | 2 | $VERSION = 75; | |||||||||||||||||||||||||||||||||||||||||
| 36 | 2 | ▶ | use Math::NumSeq; | ||||||||||||||||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||||||||||||||||
| 37 | 2 | @ISA = ('Math::NumSeq'); | |||||||||||||||||||||||||||||||||||||||||
| 38 | 2 | *_is_infinite = \&Math::NumSeq::_is_infinite; | |||||||||||||||||||||||||||||||||||||||||
| 39 | |||||||||||||||||||||||||||||||||||||||||||
| 40 | 2 | ▶ | use Math::NumSeq::Primes; # for primes_list() | ||||||||||||||||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||||||||||||||||
| 41 | 2 | ▶ | use Math::Prime::XS 'is_prime'; | ||||||||||||||||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||||||||||||||||
| 42 | |||||||||||||||||||||||||||||||||||||||||||
| 43 | # uncomment this to run the ### lines | ||||||||||||||||||||||||||||||||||||||||||
| 44 | #use Smart::Comments; | ||||||||||||||||||||||||||||||||||||||||||
| 45 | |||||||||||||||||||||||||||||||||||||||||||
| 46 | |||||||||||||||||||||||||||||||||||||||||||
| 47 | # use constant name => Math::NumSeq::__('Polignac Obstinate'); | ||||||||||||||||||||||||||||||||||||||||||
| 48 | 2 | ▶ | use constant description => Math::NumSeq::__('Odd integers N not representable as prime+2^k.'); | ||||||||||||||||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||||||||||||||||
| 49 | 2 | ▶ | use constant values_min => 1; | ||||||||||||||||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||||||||||||||||
| 50 | 2 | ▶ | use constant characteristic_increasing => 1; | ||||||||||||||||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||||||||||||||||
| 51 | 2 | ▶ | use constant characteristic_integer => 1; | ||||||||||||||||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||||||||||||||||
| 52 | 2 | ▶ | use constant i_start => 1; | ||||||||||||||||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||||||||||||||||
| 53 | |||||||||||||||||||||||||||||||||||||||||||
| 54 | # cf A133122 - demanding k>0, so 1,3,127,... as 3 no longer representable | ||||||||||||||||||||||||||||||||||||||||||
| 55 | # A065381 - primes not p+2^k k>=0, filtering from odds to primes | ||||||||||||||||||||||||||||||||||||||||||
| 56 | # | ||||||||||||||||||||||||||||||||||||||||||
| 57 | 2 | ▶ | use constant oeis_anum => 'A006285'; # with k>=0 so 1,127,... | ||||||||||||||||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||||||||||||||||
| 58 | |||||||||||||||||||||||||||||||||||||||||||
| 59 | |||||||||||||||||||||||||||||||||||||||||||
| 60 | 6 | ▶ | sub rewind { | ||||||||||||||||||||||||||||||||||||||||
|
Subroutine
rewind: called CC=1 SCAR=0.0
Pod
documented
| |||||||||||||||||||||||||||||||||||||||||||
| 61 | 6 | my ($self) = @_; | |||||||||||||||||||||||||||||||||||||||||
| 62 | 6 | $self->{'i'} = $self->i_start; | |||||||||||||||||||||||||||||||||||||||||
| 63 | 6 | $self->{'string'} = ''; | |||||||||||||||||||||||||||||||||||||||||
| 64 | 6 | vec($self->{'string'},3/2,1) = 1; # 2+2^0=3 | |||||||||||||||||||||||||||||||||||||||||
| 65 | 6 | $self->{'done'} = -1; | |||||||||||||||||||||||||||||||||||||||||
| 66 | 6 | _resieve ($self, 20); | |||||||||||||||||||||||||||||||||||||||||
| 67 | } | ||||||||||||||||||||||||||||||||||||||||||
| 68 | |||||||||||||||||||||||||||||||||||||||||||
| 69 | 45 | ▶ | sub _resieve { | ||||||||||||||||||||||||||||||||||||||||
|
Subroutine
_resieve: called CC=4 SCAR=13.9
| |||||||||||||||||||||||||||||||||||||||||||
| 70 | 45 | my ($self, $hi) = @_; | |||||||||||||||||||||||||||||||||||||||||
| 71 | ### _resieve() ... | ||||||||||||||||||||||||||||||||||||||||||
| 72 | |||||||||||||||||||||||||||||||||||||||||||
| 73 | 45 | $self->{'hi'} = $hi; | |||||||||||||||||||||||||||||||||||||||||
| 74 | 45 | my $sref = \$self->{'string'}; | |||||||||||||||||||||||||||||||||||||||||
| 75 | 45 | vec($$sref,$hi,1) = 0; # pre-extend | |||||||||||||||||||||||||||||||||||||||||
| 76 | 45 | my @primes = Math::NumSeq::Primes::_primes_list (3, $hi-1); | |||||||||||||||||||||||||||||||||||||||||
| 77 | 45 | ▶ | for (my $power = 2; $power < $hi; $power *= 2) { | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||
| 78 | 390 | foreach my $p (@primes) { | |||||||||||||||||||||||||||||||||||||||||
| 79 | 347606 | ▶ | if ((my $v = $p + $power) > $hi) { | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||
| 80 | 344 | last; | |||||||||||||||||||||||||||||||||||||||||
| 81 | } else { | ||||||||||||||||||||||||||||||||||||||||||
| 82 | 347262 | vec($$sref,$v/2,1) = 1; | |||||||||||||||||||||||||||||||||||||||||
| 83 | } | ||||||||||||||||||||||||||||||||||||||||||
| 84 | } | ||||||||||||||||||||||||||||||||||||||||||
| 85 | } | ||||||||||||||||||||||||||||||||||||||||||
| 86 | } | ||||||||||||||||||||||||||||||||||||||||||
| 87 | |||||||||||||||||||||||||||||||||||||||||||
| 88 | 3004 | ▶ | sub next { | ||||||||||||||||||||||||||||||||||||||||
|
Subroutine
next: called CC=3 SCAR=11.0
Pod
documented
| |||||||||||||||||||||||||||||||||||||||||||
| 89 | 3004 | my ($self) = @_; | |||||||||||||||||||||||||||||||||||||||||
| 90 | ### Obstinate next(): $self->{'i'} | ||||||||||||||||||||||||||||||||||||||||||
| 91 | |||||||||||||||||||||||||||||||||||||||||||
| 92 | 3004 | my $v = $self->{'done'}; | |||||||||||||||||||||||||||||||||||||||||
| 93 | 3004 | my $sref = \$self->{'string'}; | |||||||||||||||||||||||||||||||||||||||||
| 94 | 3004 | my $hi = $self->{'hi'}; | |||||||||||||||||||||||||||||||||||||||||
| 95 | |||||||||||||||||||||||||||||||||||||||||||
| 96 | 3004 | for (;;) { | |||||||||||||||||||||||||||||||||||||||||
| 97 | ### consider: "v=".($v+1)." cf done=$self->{'done'}" | ||||||||||||||||||||||||||||||||||||||||||
| 98 | 48041 | ▶ | if (($v+=2) > $hi) { | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||
| 99 | _resieve ($self, | ||||||||||||||||||||||||||||||||||||||||||
| 100 | 39 | $hi = ($self->{'hi'} *= 2)); | |||||||||||||||||||||||||||||||||||||||||
| 101 | } | ||||||||||||||||||||||||||||||||||||||||||
| 102 | 48041 | ▶ | unless (vec($$sref,$v/2,1)) { | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||
| 103 | return ($self->{'i'}++, | ||||||||||||||||||||||||||||||||||||||||||
| 104 | 3004 | $self->{'done'} = $v); | |||||||||||||||||||||||||||||||||||||||||
| 105 | } | ||||||||||||||||||||||||||||||||||||||||||
| 106 | } | ||||||||||||||||||||||||||||||||||||||||||
| 107 | } | ||||||||||||||||||||||||||||||||||||||||||
| 108 | |||||||||||||||||||||||||||||||||||||||||||
| 109 | 96078 | ▶ | sub pred { | ||||||||||||||||||||||||||||||||||||||||
|
Subroutine
pred: called CC=8 SCAR=21.1
Pod
documented
| |||||||||||||||||||||||||||||||||||||||||||
| 110 | 96078 | my ($self, $value) = @_; | |||||||||||||||||||||||||||||||||||||||||
| 111 | ### Obstinate pred(): $value | ||||||||||||||||||||||||||||||||||||||||||
| 112 | |||||||||||||||||||||||||||||||||||||||||||
| 113 | 96078 | ▶ | 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
| |||||||||||||||||||||||||||||||||||||||||||
| 114 | 0 | return undef; | |||||||||||||||||||||||||||||||||||||||||
| 115 | } | ||||||||||||||||||||||||||||||||||||||||||
| 116 | 96078 | ▶ | if ($value != int($value) | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
Condition100%6/6
$value != int $value or $value < 127 or $value % 2 == 0
$value != int $value or $value < 127
MC/DC100%3/3
$value != int $value or $value < 127 or $value % 2 == 0
$value != int $value
$value < 127
$value % 2 == 0
Truth table100%4/4
A or B or C
A= $value != int $valueB= $value < 127C= $value % 2 == 0
| |||||||||||||||||||||||||||||||||||||||||||
| 117 | || $value < 127 | ||||||||||||||||||||||||||||||||||||||||||
| 118 | || ($value % 2) == 0) { | ||||||||||||||||||||||||||||||||||||||||||
| 119 | 48352 | return ($value == 1); | |||||||||||||||||||||||||||||||||||||||||
| 120 | } | ||||||||||||||||||||||||||||||||||||||||||
| 121 | 47726 | $value = "$value"; # numize Math::BigInt for speed | |||||||||||||||||||||||||||||||||||||||||
| 122 | |||||||||||||||||||||||||||||||||||||||||||
| 123 | # Maybe an is_any_prime(...) | ||||||||||||||||||||||||||||||||||||||||||
| 124 | 47726 | ▶ | for (my $power = 2; $power < $value; $power *= 2) { | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||
| 125 | 216735 | ▶ | if (is_prime($value - $power)) { | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||
| 126 | 44727 | return 0; | |||||||||||||||||||||||||||||||||||||||||
| 127 | } | ||||||||||||||||||||||||||||||||||||||||||
| 128 | } | ||||||||||||||||||||||||||||||||||||||||||
| 129 | 2999 | return 1; | |||||||||||||||||||||||||||||||||||||||||
| 130 | } | ||||||||||||||||||||||||||||||||||||||||||
| 131 | |||||||||||||||||||||||||||||||||||||||||||
| 132 | 2 | 1; | |||||||||||||||||||||||||||||||||||||||||
| 133 | __END__ | ||||||||||||||||||||||||||||||||||||||||||