| 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 | |||||||||||||||||||||||||||||
| 19 | # http://mathworld.wolfram.com/GoldbachConjecture.html | ||||||||||||||||||||||||||||
| 20 | |||||||||||||||||||||||||||||
| 21 | |||||||||||||||||||||||||||||
| 22 | package Math::NumSeq::GoldbachCount; | ||||||||||||||||||||||||||||
| 23 | 1 | ▶ | use 5.004; | ||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||
| 24 | 1 | ▶ | use strict; | ||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||
| 25 | 1 | ▶ | use Math::Prime::XS 0.23 'is_prime'; # version 0.23 fix for 1928099 | ||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||
| 26 | |||||||||||||||||||||||||||||
| 27 | 1 | ▶ | use vars '$VERSION', '@ISA'; | ||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||
| 28 | 1 | $VERSION = 75; | |||||||||||||||||||||||||||
| 29 | 1 | @ISA = ('Math::NumSeq'); | |||||||||||||||||||||||||||
| 30 | 1 | *_is_infinite = \&Math::NumSeq::_is_infinite; | |||||||||||||||||||||||||||
| 31 | |||||||||||||||||||||||||||||
| 32 | 1 | ▶ | use Math::NumSeq::Primes; | ||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||
| 33 | |||||||||||||||||||||||||||||
| 34 | # uncomment this to run the ### lines | ||||||||||||||||||||||||||||
| 35 | #use Smart::Comments; | ||||||||||||||||||||||||||||
| 36 | |||||||||||||||||||||||||||||
| 37 | |||||||||||||||||||||||||||||
| 38 | # use constant name => Math::NumSeq::__('Goldbach Count'); | ||||||||||||||||||||||||||||
| 39 | 1 | ▶ | use constant description => Math::NumSeq::__('The number of ways i can be represented as P+Q for primes P and Q. The Goldbach conjecture is that all even i>=4 can be represented in at least one such way.'); | ||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||
| 40 | 1 | ▶ | use constant default_i_start => 1; | ||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||
| 41 | 1 | ▶ | use constant values_min => 0; | ||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||
| 42 | 1 | ▶ | use constant characteristic_count => 1; | ||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||
| 43 | 1 | ▶ | use constant characteristic_smaller => 1; | ||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||
| 44 | |||||||||||||||||||||||||||||
| 45 | # not documented yet | ||||||||||||||||||||||||||||
| 46 | 1 | ▶ | use constant parameter_info_array => | ||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||
| 47 | [ | ||||||||||||||||||||||||||||
| 48 | { | ||||||||||||||||||||||||||||
| 49 | name => 'on_values', | ||||||||||||||||||||||||||||
| 50 | share_key => 'on_values_even', | ||||||||||||||||||||||||||||
| 51 | type => 'enum', | ||||||||||||||||||||||||||||
| 52 | default => 'all', | ||||||||||||||||||||||||||||
| 53 | choices => ['all','even'], | ||||||||||||||||||||||||||||
| 54 | choices_display => [Math::NumSeq::__('All'), | ||||||||||||||||||||||||||||
| 55 | Math::NumSeq::__('Even')], | ||||||||||||||||||||||||||||
| 56 | # description => Math::NumSeq::__('...'), | ||||||||||||||||||||||||||||
| 57 | }, | ||||||||||||||||||||||||||||
| 58 | 1 | ]; | |||||||||||||||||||||||||||
| 59 | |||||||||||||||||||||||||||||
| 60 | #------------------------------------------------------------------------------ | ||||||||||||||||||||||||||||
| 61 | # cf A014092 - n not P+Q, ie. count=0, starting from value=1 | ||||||||||||||||||||||||||||
| 62 | # A014091 - n some P+Q, ie. count!=0 | ||||||||||||||||||||||||||||
| 63 | # A067187 - n one way P+Q, ie. count=1 | ||||||||||||||||||||||||||||
| 64 | # A067188 - n two ways, count=2 | ||||||||||||||||||||||||||||
| 65 | # A067189 - n three ways | ||||||||||||||||||||||||||||
| 66 | # A067190 - n four ways | ||||||||||||||||||||||||||||
| 67 | # A067191 - n five ways | ||||||||||||||||||||||||||||
| 68 | # A073610 - num primes n-p where p prime, so counting two ways | ||||||||||||||||||||||||||||
| 69 | # A045917 - 2n, ordered sum | ||||||||||||||||||||||||||||
| 70 | # A185297 - sum of the p's p+q=2n | ||||||||||||||||||||||||||||
| 71 | # A185298 - sum of the q's p+q=2n | ||||||||||||||||||||||||||||
| 72 | # A002372 - count for two odd primes | ||||||||||||||||||||||||||||
| 73 | # | ||||||||||||||||||||||||||||
| 74 | # A045917 - unordered 2n, start n=1 is 2 | ||||||||||||||||||||||||||||
| 75 | # odd or even primes, so n=2 is 4 count 1 for 2+2=4 | ||||||||||||||||||||||||||||
| 76 | # A002375 - unordered 2n, start n=1 is 2 | ||||||||||||||||||||||||||||
| 77 | # odd primes, so n=2 is 4 count 1 for 2+2=4 | ||||||||||||||||||||||||||||
| 78 | # | ||||||||||||||||||||||||||||
| 79 | 1 | my %oeis_anum = ('all' => 'A061358', # ordered p>=q, start n=0 | |||||||||||||||||||||||||||
| 80 | 'even' => 'A045917', # unordered sum, start n=1 is 2 | ||||||||||||||||||||||||||||
| 81 | # OEIS-Catalogue: A061358 i_start=0 | ||||||||||||||||||||||||||||
| 82 | # OEIS-Catalogue: A045917 on_values=even | ||||||||||||||||||||||||||||
| 83 | ); | ||||||||||||||||||||||||||||
| 84 | 2 | ▶ | sub oeis_anum { | ||||||||||||||||||||||||||
|
Subroutine
oeis_anum: called CC=1 SCAR=0.0
Pod
documented
| |||||||||||||||||||||||||||||
| 85 | 2 | my ($self) = @_; | |||||||||||||||||||||||||||
| 86 | 2 | return $oeis_anum{$self->{'on_values'}}; | |||||||||||||||||||||||||||
| 87 | } | ||||||||||||||||||||||||||||
| 88 | |||||||||||||||||||||||||||||
| 89 | #------------------------------------------------------------------------------ | ||||||||||||||||||||||||||||
| 90 | |||||||||||||||||||||||||||||
| 91 | 6 | ▶ | sub rewind { | ||||||||||||||||||||||||||
|
Subroutine
rewind: called CC=2 SCAR=6.9
Pod
documented
| |||||||||||||||||||||||||||||
| 92 | 6 | my ($self) = @_; | |||||||||||||||||||||||||||
| 93 | ### GoldbachCount rewind() ... | ||||||||||||||||||||||||||||
| 94 | 6 | $self->{'i'} = $self->i_start; | |||||||||||||||||||||||||||
| 95 | |||||||||||||||||||||||||||||
| 96 | # special case initial array for even so can then exclude prime p=2 from loop | ||||||||||||||||||||||||||||
| 97 | 6 | ▶ | $self->{'array'} = ($self->{'on_values'} eq 'even' | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 98 | ? [ 0, 0, 1, 1 ] | ||||||||||||||||||||||||||||
| 99 | : []); | ||||||||||||||||||||||||||||
| 100 | 6 | $self->{'size'} = 499; # must be odd for 2i case | |||||||||||||||||||||||||||
| 101 | } | ||||||||||||||||||||||||||||
| 102 | |||||||||||||||||||||||||||||
| 103 | 50 | ▶ | sub next { | ||||||||||||||||||||||||||
|
Subroutine
next: called CC=10 SCAR=23.0
Pod
documented
| |||||||||||||||||||||||||||||
| 104 | 50 | my ($self) = @_; | |||||||||||||||||||||||||||
| 105 | ### next(): "i=$self->{'i'}, arraylen=".scalar(@{$self->{'array'}}) | ||||||||||||||||||||||||||||
| 106 | |||||||||||||||||||||||||||||
| 107 | 50 | ▶ | unless (@{$self->{'array'}}) { | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 108 | 4 | $self->{'size'} = int(1.1 * $self->{'size'}) | 1; # must be odd | |||||||||||||||||||||||||||
| 109 | |||||||||||||||||||||||||||||
| 110 | 4 | my $lo = $self->{'i'}; | |||||||||||||||||||||||||||
| 111 | 4 | my $even_only = ($self->{'on_values'} eq 'even'); | |||||||||||||||||||||||||||
| 112 | 4 | ▶ | if ($even_only) { | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 113 | 2 | $lo *= 2; | |||||||||||||||||||||||||||
| 114 | } | ||||||||||||||||||||||||||||
| 115 | 4 | my $hi = $lo + $self->{'size'}; | |||||||||||||||||||||||||||
| 116 | ### range: "lo=$lo to hi=$hi" | ||||||||||||||||||||||||||||
| 117 | 4 | my @array; | |||||||||||||||||||||||||||
| 118 | 4 | $array[$hi-$lo] = 0; # array size | |||||||||||||||||||||||||||
| 119 | |||||||||||||||||||||||||||||
| 120 | 4 | my @primes = Math::NumSeq::Primes::_primes_list (0, $hi); | |||||||||||||||||||||||||||
| 121 | 4 | ▶ | if ($even_only) { | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 122 | 2 | shift @primes; # skip P=2 | |||||||||||||||||||||||||||
| 123 | } | ||||||||||||||||||||||||||||
| 124 | |||||||||||||||||||||||||||||
| 125 | { | ||||||||||||||||||||||||||||
| 126 | 4 | my $qamax = $#primes; | |||||||||||||||||||||||||||
| 127 | 4 | foreach my $pa (0 .. $#primes-1) { | |||||||||||||||||||||||||||
| 128 | 398 | foreach my $qa (reverse $pa .. $qamax) { | |||||||||||||||||||||||||||
| 129 | 12608 | my $sum = $primes[$pa] + $primes[$qa]; | |||||||||||||||||||||||||||
| 130 | ### at: "p=$primes[$pa] q=$primes[$qa] sum=$sum incr ".($sum-$lo) | ||||||||||||||||||||||||||||
| 131 | 12608 | ▶ | if ($sum > $hi) { | ||||||||||||||||||||||||||
|
Branch: 2 branches
| |||||||||||||||||||||||||||||
| 132 | 170 | $qamax = $qa-1; | |||||||||||||||||||||||||||
| 133 | } elsif ($sum < $lo) { | ||||||||||||||||||||||||||||
| 134 | 0 | last; | |||||||||||||||||||||||||||
| 135 | } else { | ||||||||||||||||||||||||||||
| 136 | 12438 | $array[$sum-$lo]++; | |||||||||||||||||||||||||||
| 137 | } | ||||||||||||||||||||||||||||
| 138 | } | ||||||||||||||||||||||||||||
| 139 | } | ||||||||||||||||||||||||||||
| 140 | } | ||||||||||||||||||||||||||||
| 141 | ### @array | ||||||||||||||||||||||||||||
| 142 | 4 | $self->{'array'} = \@array; | |||||||||||||||||||||||||||
| 143 | } | ||||||||||||||||||||||||||||
| 144 | |||||||||||||||||||||||||||||
| 145 | 50 | ▶ | my $value = shift @{$self->{'array'}} || 0; | ||||||||||||||||||||||||||
|
Condition100%2/2
shift @{$$self{'array'};} || 0
MC/DC100%1/1
shift @{$$self{'array'};} || 0
shift @{$$self{'array'};}
Truth table100%2/2
A
A= shift @{$$self{'array'};}
| |||||||||||||||||||||||||||||
| 146 | ### $value | ||||||||||||||||||||||||||||
| 147 | 50 | ▶ | if ($self->{'on_values'} eq 'even') { | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 148 | 16 | shift @{$self->{'array'}}; # skip odd | |||||||||||||||||||||||||||
| 149 | } | ||||||||||||||||||||||||||||
| 150 | 50 | return ($self->{'i'}++, $value); | |||||||||||||||||||||||||||
| 151 | } | ||||||||||||||||||||||||||||
| 152 | |||||||||||||||||||||||||||||
| 153 | 81 | ▶ | sub ith { | ||||||||||||||||||||||||||
|
Subroutine
ith: called CC=9 SCAR=22.1
Pod
documented
| |||||||||||||||||||||||||||||
| 154 | 81 | my ($self, $i) = @_; | |||||||||||||||||||||||||||
| 155 | ### ith(): $i | ||||||||||||||||||||||||||||
| 156 | |||||||||||||||||||||||||||||
| 157 | 81 | ▶ | if ($self->{'on_values'} eq 'even') { | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 158 | 27 | $i *= 2; | |||||||||||||||||||||||||||
| 159 | } | ||||||||||||||||||||||||||||
| 160 | 81 | ▶ | if ($i <= 3) { | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 161 | 18 | return 0; | |||||||||||||||||||||||||||
| 162 | } | ||||||||||||||||||||||||||||
| 163 | 63 | ▶ | unless ($i >= 0 && $i <= 0xFF_FFFF) { | ||||||||||||||||||||||||||
|
Branch: 1 branch
Condition33%1/3
$i >= 0 and $i <= 16777215
MC/DC0%0/2
$i >= 0 and $i <= 16777215
$i >= 0
$i <= 16777215
Truth table33%1/3
A and B
A= $i >= 0B= $i <= 16777215
| |||||||||||||||||||||||||||||
| 164 | 0 | return undef; | |||||||||||||||||||||||||||
| 165 | } | ||||||||||||||||||||||||||||
| 166 | 63 | $i = "$i"; # numize any Math::BigInt for speed | |||||||||||||||||||||||||||
| 167 | |||||||||||||||||||||||||||||
| 168 | 63 | ▶ | if ($i & 1) { | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 169 | ### odd, check prime: $i-2 | ||||||||||||||||||||||||||||
| 170 | 21 | ▶ | return (is_prime($i-2) ? 1 : 0); # odd only i=2+Q for prime Q | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 171 | } | ||||||||||||||||||||||||||||
| 172 | |||||||||||||||||||||||||||||
| 173 | 42 | my $count = 0; | |||||||||||||||||||||||||||
| 174 | 42 | my @primes = Math::NumSeq::Primes::_primes_list (0, $i-1); | |||||||||||||||||||||||||||
| 175 | ### @primes | ||||||||||||||||||||||||||||
| 176 | |||||||||||||||||||||||||||||
| 177 | 42 | my $pa = 0; | |||||||||||||||||||||||||||
| 178 | 42 | my $qa = $#primes; | |||||||||||||||||||||||||||
| 179 | 42 | ▶ | while ($pa <= $qa) { | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 180 | 199 | my $sum = $primes[$pa] + $primes[$qa]; | |||||||||||||||||||||||||||
| 181 | 199 | ▶ | if ($sum <= $i) { | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 182 | ### at: "p=$primes[$pa] q=$primes[$qa] incr=".($sum == $i) | ||||||||||||||||||||||||||||
| 183 | 125 | $count += ($sum == $i); | |||||||||||||||||||||||||||
| 184 | 125 | $pa++; | |||||||||||||||||||||||||||
| 185 | } else { | ||||||||||||||||||||||||||||
| 186 | 74 | $qa--; | |||||||||||||||||||||||||||
| 187 | } | ||||||||||||||||||||||||||||
| 188 | } | ||||||||||||||||||||||||||||
| 189 | |||||||||||||||||||||||||||||
| 190 | ### $count | ||||||||||||||||||||||||||||
| 191 | 42 | return $count; | |||||||||||||||||||||||||||
| 192 | } | ||||||||||||||||||||||||||||
| 193 | |||||||||||||||||||||||||||||
| 194 | 25 | ▶ | sub pred { | ||||||||||||||||||||||||||
|
Subroutine
pred: called CC=2 SCAR=8.1
Pod
documented
| |||||||||||||||||||||||||||||
| 195 | 25 | my ($self, $value) = @_; | |||||||||||||||||||||||||||
| 196 | ### HypotCount pred(): $value | ||||||||||||||||||||||||||||
| 197 | 25 | ▶ | return ($value >= 0 && $value == int($value)); | ||||||||||||||||||||||||||
|
Condition33%1/3
$value >= 0 && $value == int $value
MC/DC0%0/2
$value >= 0 && $value == int $value
$value >= 0
$value == int $value
Truth table33%1/3
A && B
A= $value >= 0B= $value == int $value
| |||||||||||||||||||||||||||||
| 198 | } | ||||||||||||||||||||||||||||
| 199 | |||||||||||||||||||||||||||||
| 200 | 1 | 1; | |||||||||||||||||||||||||||
| 201 | __END__ | ||||||||||||||||||||||||||||