This is an automated email from the git hooks/post-receive script.
ppm-guest pushed a commit to annotated tag v0.15
in repository libmath-prime-util-perl.
commit f5ca1e0fc68881504427aacf9ea63c511df48291
Author: Dana Jacobsen <d...@acm.org>
Date: Mon Dec 3 01:53:07 2012 -0800
Tests for primorial, jordan_totient, divisor_sum
---
Changes | 2 +
MANIFEST | 1 +
Makefile.PL | 1 +
TODO | 3 --
lib/Math/Prime/Util.pm | 3 +-
t/19-moebius.t | 101 +++++++++++++++++++++++++++++++++++++++++++++----
t/20-primorial.t | 86 +++++++++++++++++++++++++++++++++++++++++
t/22-aks-prime.t | 38 +++----------------
8 files changed, 190 insertions(+), 45 deletions(-)
diff --git a/Changes b/Changes
index c660517..12a8152 100644
--- a/Changes
+++ b/Changes
@@ -13,6 +13,8 @@ Revision history for Perl extension Math::Prime::Util.
- BigFloat versions if no MPFR and BigFloat input.
- standard version if no MPFR and not a BigFloat.
+ - Add tests for primorial, jordan_totient, and divisor_sum.
+
0.14 29 November 2012
- Compilation and test issues:
diff --git a/MANIFEST b/MANIFEST
index 66eb448..6d62933 100644
--- a/MANIFEST
+++ b/MANIFEST
@@ -70,6 +70,7 @@ t/16-randomprime.t
t/17-pseudoprime.t
t/18-functions.t
t/19-moebius.t
+t/20-primorial.t
t/22-aks-prime.t
t/30-relations.t
t/31-threading.t
diff --git a/Makefile.PL b/Makefile.PL
index ad34e57..e5d16cc 100644
--- a/Makefile.PL
+++ b/Makefile.PL
@@ -35,6 +35,7 @@ WriteMakefile1(
META_MERGE => {
recommends => { 'Math::Prime::Util::GMP' => 0.04, },
recommends => { 'Math::BigInt::GMP' => 0, },
+ recommends => { 'Math::MPFR' => 0, },
},
MIN_PERL_VERSION => 5.006002,
diff --git a/TODO b/TODO
index a83b661..c97cc81 100644
--- a/TODO
+++ b/TODO
@@ -34,9 +34,6 @@
- Tests for:
- primorial
- jordan_totient
- divisor_sum
is_provable_prime
RiemannZeta
RiemannR
diff --git a/lib/Math/Prime/Util.pm b/lib/Math/Prime/Util.pm
index 855eec5..b044abe 100644
--- a/lib/Math/Prime/Util.pm
+++ b/lib/Math/Prime/Util.pm
@@ -839,8 +839,9 @@ sub jordan_totient {
sub divisor_sum {
my($n, $sub) = @_;
croak "Second argument must be a code ref" unless ref($sub) eq 'CODE';
- return 0 if defined $n && $n <= 1;
+ return 0 if defined $n && $n < 1;
_validate_positive_integer($n);
+ return ($n-$n+$sub->(1)) if $n == 1;
my @afactors = all_factors($n);
diff --git a/t/19-moebius.t b/t/19-moebius.t
index 55b1caa..3447e2b 100644
--- a/t/19-moebius.t
+++ b/t/19-moebius.t
@@ -3,7 +3,9 @@ use strict;
use warnings;
use Test::More;
-use Math::Prime::Util qw/moebius euler_phi/;
+use Math::Prime::Util qw/moebius euler_phi jordan_totient divisor_sum/;
+
+my $use64 = Math::Prime::Util::prime_get_config->{'maxbits'} > 32;
my @moeb_vals = (qw/ 1 -1 -1 0 -1 1 -1 0 0 1 -1 0 -1 1 1 0 -1 0 -1 0 /);
my %mertens = (
@@ -27,19 +29,55 @@ my %totients = (
123456789 => 82260072,
);
my @A000010 =
(0,1,1,2,2,4,2,6,4,6,4,10,4,12,6,8,8,16,6,18,8,12,10,22,8,20,12,18,12,28,8,30,16,20,16,24,12,36,18,24,16,40,12,42,20,24,22,46,16,42,20,32,24,52,18,40,24,36,28,58,16,60,30,36,32,48,20,66,32,44);
-@totients{0..$#A000010} = @A000010;
+#@totients{0..$#A000010} = @A000010;
+
+my @A001615 =
(1,3,4,6,6,12,8,12,12,18,12,24,14,24,24,24,18,36,20,36,32,36,24,48,30,42,36,48,30,72,32,48,48,54,48,72,38,60,56,72,42,96,44,72,72,72,48,96,56,90,72,84,54,108,72,96,80,90,60,144,62,96,96,96,84,144,68,108,96);
+
+my %jordan_totients = (
+ # A000010
+ 1 => [1, 1, 2, 2, 4, 2, 6, 4, 6, 4, 10, 4, 12, 6, 8, 8, 16, 6, 18, 8, 12,
10, 22, 8, 20, 12, 18, 12, 28, 8, 30, 16, 20, 16, 24, 12, 36, 18, 24, 16, 40,
12, 42, 20, 24, 22, 46, 16, 42, 20, 32, 24, 52, 18, 40, 24, 36, 28, 58, 16, 60,
30, 36, 32, 48, 20, 66, 32, 44],
+ # A007434
+ 2 => [1, 3, 8, 12, 24, 24, 48, 48, 72, 72, 120, 96, 168, 144, 192, 192, 288,
216, 360, 288, 384, 360, 528, 384, 600, 504, 648, 576, 840, 576, 960, 768, 960,
864, 1152, 864, 1368, 1080, 1344, 1152, 1680, 1152, 1848, 1440, 1728, 1584,
2208, 1536],
+ # A059376
+ 3 => [1, 7, 26, 56, 124, 182, 342, 448, 702, 868, 1330, 1456, 2196, 2394,
3224, 3584, 4912, 4914, 6858, 6944, 8892, 9310, 12166, 11648, 15500, 15372,
18954, 19152, 24388, 22568, 29790, 28672, 34580, 34384, 42408, 39312, 50652,
48006, 57096],
+ # A059377
+ 4 => [1, 15, 80, 240, 624, 1200, 2400, 3840, 6480, 9360, 14640, 19200,
28560, 36000, 49920, 61440, 83520, 97200, 130320, 149760, 192000, 219600,
279840, 307200, 390000, 428400, 524880, 576000, 707280, 748800, 923520, 983040,
1171200],
+ # A059378
+ 5 => [1, 31, 242, 992, 3124, 7502, 16806, 31744, 58806, 96844, 161050,
240064, 371292, 520986, 756008, 1015808, 1419856, 1822986, 2476098, 3099008,
4067052, 4992550, 6436342, 7682048, 9762500, 11510052, 14289858, 16671552,
20511148],
+ # A069091
+ 6 => [1, 63, 728, 4032, 15624, 45864, 117648, 258048, 530712, 984312,
1771560, 2935296, 4826808, 7411824, 11374272, 16515072, 24137568, 33434856,
47045880, 62995968, 85647744, 111608280, 148035888, 187858944, 244125000,
304088904, 386889048],
+ # A069092
+ 7 => [1, 127, 2186, 16256, 78124, 277622, 823542, 2080768, 4780782, 9921748,
19487170, 35535616, 62748516, 104589834, 170779064, 266338304, 410338672,
607159314, 893871738, 1269983744, 1800262812, 2474870590, 3404825446],
+);
+
+my %sigmak = (
+ # A0000005
+ 0 =>
[1,2,2,3,2,4,2,4,3,4,2,6,2,4,4,5,2,6,2,6,4,4,2,8,3,4,4,6,2,8,2,6,4,4,4,9,2,4,4,8,2,8,2,6,6,4,2,10,3,6,4,6,2,8,4,8,4,4,2,12,2,4,6,7,4,8,2,6,4,8,2,12,2,4,6,6,4,8,2,10,5,4,2,12,4,4,4,8,2,12,4,6,4,4,4,12,2,6,6,9,2,8,2,8],
+ # A000203
+ 1 => [1, 3, 4, 7, 6, 12, 8, 15, 13, 18, 12, 28, 14, 24, 24, 31, 18, 39, 20,
42, 32, 36, 24, 60, 31, 42, 40, 56, 30, 72, 32, 63, 48, 54, 48, 91, 38, 60, 56,
90, 42, 96, 44, 84, 78, 72, 48, 124, 57, 93, 72, 98, 54, 120, 72, 120, 80, 90,
60, 168, 62, 96, 104, 127, 84, 144, 68, 126, 96, 144],
+ # A001157
+ 2 => [1, 5, 10, 21, 26, 50, 50, 85, 91, 130, 122, 210, 170, 250, 260, 341,
290, 455, 362, 546, 500, 610, 530, 850, 651, 850, 820, 1050, 842, 1300, 962,
1365, 1220, 1450, 1300, 1911, 1370, 1810, 1700, 2210, 1682, 2500, 1850, 2562,
2366, 2650, 2210, 3410, 2451, 3255],
+ # A001158
+ 3 => [1, 9, 28, 73, 126, 252, 344, 585, 757, 1134, 1332, 2044, 2198, 3096,
3528, 4681, 4914, 6813, 6860, 9198, 9632, 11988, 12168, 16380, 15751, 19782,
20440, 25112, 24390, 31752, 29792, 37449, 37296, 44226, 43344, 55261, 50654,
61740, 61544],
+);
+
plan tests => 0 + 1
- + scalar @moeb_vals
+ + 1 # Small Moebius
+ scalar(keys %mertens)
- + scalar(keys %totients);
+ + 1 # Small Phi
+ + scalar(keys %totients)
+ + scalar(keys %jordan_totients)
+ + 2 # Dedekind psi calculated two ways
+ + 1 # Calculate J5 two different ways
+ + 2 * $use64 # Jordan totient example
+ + scalar(keys %sigmak);
ok(!eval { moebius(0); }, "moebius(0)");
-my $i = 1;
-foreach my $m (@moeb_vals) {
- is( moebius($i), $m, "moebius($i) == $m" );
- $i++;
+{
+ my @moebius = map { moebius($_) } (1 .. scalar @moeb_vals);
+ is_deeply( \@moebius, \@moeb_vals, "moebius 1 .. " . scalar @moeb_vals );
}
while (my($n, $mertens) = each (%mertens)) {
@@ -48,6 +86,53 @@ while (my($n, $mertens) = each (%mertens)) {
is( $M, $mertens, "Mertens($n) == $mertens" );
}
+{
+ my @phi = map { euler_phi($_) } (0 .. $#A000010);
+ is_deeply( \@phi, \@A000010, "euler_phi 0 .. $#A000010" );
+}
while (my($n, $phi) = each (%totients)) {
is( euler_phi($n), $phi, "euler_phi($n) == $phi" );
}
+
+###### Jordan Totient
+while (my($k, $tref) = each (%jordan_totients)) {
+ my @tlist;
+ foreach my $n (1 .. scalar @$tref) {
+ push @tlist, jordan_totient($k, $n);
+ }
+ is_deeply( \@tlist, $tref, "Jordan's Totient J_$k" );
+}
+
+{
+ my @psi_viaj;
+ my @psi_viamobius;
+ foreach my $n (1 .. scalar @A001615) {
+ push @psi_viaj, int(jordan_totient(2, $n) / jordan_totient(1, $n));
+ push @psi_viamobius, int($n * divisor_sum( $n, sub { moebius($_[0])**2 /
$_[0] } ) + 0.5);
+ }
+ is_deeply( \@psi_viaj, \@A001615, "Dedikind psi(n) = J_2(n)/J_1(n)" );
+ is_deeply( \@psi_viamobius, \@A001615, "Dedikind psi(n) = divisor_sum(n,
moebius(d)^2 / d)" );
+}
+
+{
+ my @J5_moebius = map { divisor_sum($_, sub { my $d=shift; $d**5 *
moebius($_/$d); }) } (0 .. 100);
+ my @J5_jordan = map { jordan_totient(5, $_) } (0 .. 100);
+ is_deeply( \@J5_moebius, \@J5_jordan, "Calculate J5 two different ways");
+}
+
+if ($use64) {
+ is( jordan_totient(4, 12345), 22902026746060800, "J_4(12345)" );
+ # Apostal page 48, 17a.
+ is( divisor_sum( 12345, sub { jordan_totient(4,shift) } ),
+ int(12345 ** 4),
+ "n=12345, k=4 : n**k = divisor_sum(n, jordan_totient(k, d))" );
+}
+
+###### Divisor sum
+while (my($k, $sigmaref) = each (%sigmak)) {
+ my @slist;
+ foreach my $n (1 .. scalar @$sigmaref) {
+ push @slist, divisor_sum( $n, sub { int($_[0] ** $k) } );
+ }
+ is_deeply( \@slist, $sigmaref, "Sum of divisors to the ${k}th power:
Sigma_$k" );
+}
diff --git a/t/20-primorial.t b/t/20-primorial.t
new file mode 100644
index 0000000..3546610
--- /dev/null
+++ b/t/20-primorial.t
@@ -0,0 +1,86 @@
+#!/usr/bin/env perl
+use strict;
+use warnings;
+
+use Test::More;
+use Math::Prime::Util qw/primorial pn_primorial/;
+
+my @pn_primorials = qw/
+1
+2
+6
+30
+210
+2310
+30030
+510510
+9699690
+223092870
+6469693230
+200560490130
+7420738134810
+304250263527210
+13082761331670030
+614889782588491410
+32589158477190044730
+1922760350154212639070
+117288381359406970983270
+7858321551080267055879090
+557940830126698960967415390
+40729680599249024150621323470
+3217644767340672907899084554130
+267064515689275851355624017992790
+23768741896345550770650537601358310
+2305567963945518424753102147331756070
+232862364358497360900063316880507363070
+23984823528925228172706521638692258396210
+2566376117594999414479597815340071648394470
+279734996817854936178276161872067809674997230
+31610054640417607788145206291543662493274686990
+/;
+
+my @small_primorials = grep { $_ <= ~0 } @pn_primorials;
+
+plan tests => 0
+ + 2 * (scalar @small_primorials)
+ + 2 * (scalar @pn_primorials)
+ + 2;
+
+my @small_primes = qw/
+2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71
+73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173
+179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277 281
+283 293 307 311 313 317 331 337 347 349 353 359 367 373 379 383 389 397 401 409
+419 421 431 433 439 443 449 457 461 463 467 479 487 491 499 503 509 521 523 541
+547 557 563 569 571 577 587 593 599 601 607 613 617 619 631 641 643 647 653 659
+661 673 677 683 691 701 709 719 727 733 739 743 751 757 761 769 773 787 797 809
+811 821 823 827 829 839 853 857 859 863 877 881 883 887 907 911 919 929 937 941
+/;
+sub nth_prime {
+ my $n = shift;
+ return 0 if $n <= 0;
+ die "Out of range for fake nth_prime: $n" unless defined $small_primes[$n-1];
+ $small_primes[$n-1];
+}
+
+# First we test native numbers
+foreach my $n (0 .. $#small_primorials) {
+ is( primorial(nth_prime($n)), $pn_primorials[$n], "primorial(nth($n))" );
+ is( pn_primorial($n), $pn_primorials[$n], "pn_primorial($n)" );
+}
+
+# Then load up BigInt and make sure everything works for big numbers
+require Math::BigInt;
+foreach my $n (0 .. $#pn_primorials) {
+ is( primorial(nth_prime($n)), $pn_primorials[$n], "primorial(nth($n))" );
+ is( pn_primorial($n), $pn_primorials[$n], "pn_primorial($n)" );
+}
+
+
+is( primorial(100), '2305567963945518424753102147331756070', "primorial(100)");
+
+is(
+ primorial(541),
+
'4711930799906184953162487834760260422020574773409675520188634839616415335845034221205289256705544681972439104097777157991804380284218315038719444943990492579030720635990538452312528339864352999310398481791730017201031090',
+ "primorial(541)"
+ );
diff --git a/t/22-aks-prime.t b/t/22-aks-prime.t
index 355bde6..040199f 100644
--- a/t/22-aks-prime.t
+++ b/t/22-aks-prime.t
@@ -9,38 +9,6 @@ my $use64 = Math::Prime::Util::prime_get_config->{'maxbits'} >
32;
my $extra = defined $ENV{RELEASE_TESTING} && $ENV{RELEASE_TESTING};
my $broken64 = (18446744073709550592 == ~0);
-my @small_primes = qw/
-2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97
-101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197
-199 211 223 227 229 233 239 241 251 257 263 269 271 277 281 283 293 307 311 313
-317 331 337 347 349 353 359 367 373 379 383 389 397 401 409 419 421 431 433 439
-443 449 457 461 463 467 479 487 491 499 503 509 521 523 541 547 557 563 569 571
-577 587 593 599 601 607 613 617 619 631 641 643 647 653 659 661 673 677 683 691
-701 709 719 727 733 739 743 751 757 761 769 773 787 797 809 811 821 823 827 829
-839 853 857 859 863 877 881 883 887 907 911 919 929 937 941 947 953 967 971 977
-983 991 997
-1009 1013 1019 1021 1031 1033 1039 1049 1051 1061 1063 1069 1087 1091 1093 1097
-1103 1109 1117 1123 1129 1151 1153 1163 1171 1181 1187 1193 1201 1213 1217 1223
-1229 1231 1237 1249 1259 1277 1279 1283 1289 1291 1297 1301 1303 1307 1319 1321
-1327 1361 1367 1373 1381 1399 1409 1423 1427 1429 1433 1439 1447 1451 1453 1459
-1471 1481 1483 1487 1489 1493 1499 1511 1523 1531 1543 1549 1553 1559 1567 1571
-1579 1583 1597 1601 1607 1609 1613 1619 1621 1627 1637 1657 1663 1667 1669 1693
-1697 1699 1709 1721 1723 1733 1741 1747 1753 1759 1777 1783 1787 1789 1801 1811
-1823 1831 1847 1861 1867 1871 1873 1877 1879 1889 1901 1907 1913 1931 1933 1949
-1951 1973 1979 1987 1993 1997 1999 2003 2011 2017 2027 2029 2039 2053 2063 2069
-2081 2083 2087 2089 2099 2111 2113 2129 2131 2137 2141 2143 2153 2161 2179 2203
-2207 2213 2221 2237 2239 2243 2251 2267 2269 2273 2281 2287 2293 2297 2309 2311
-2333 2339 2341 2347 2351 2357 2371 2377 2381 2383 2389 2393 2399 2411 2417 2423
-2437 2441 2447 2459 2467 2473 2477 2503 2521 2531 2539 2543 2549 2551 2557 2579
-2591 2593 2609 2617 2621 2633 2647 2657 2659 2663 2671 2677 2683 2687 2689 2693
-2699 2707 2711 2713 2719 2729 2731 2741 2749 2753 2767 2777 2789 2791 2797 2801
-2803 2819 2833 2837 2843 2851 2857 2861 2879 2887 2897 2903 2909 2917 2927 2939
-2953 2957 2963 2969 2971 2999 3001 3011 3019 3023 3037 3041 3049 3061 3067 3079
-3083 3089 3109 3119 3121 3137 3163 3167 3169 3181 3187 3191 3203 3209 3217 3221
-3229 3251 3253 3257 3259 3271 3299 3301 3307 3313 3319 3323 3329 3331 3343 3347
-3359 3361 3371 3373 3389 3391 3407 3413 3433 3449 3457 3461 3463 3467 3469 3491
-3499 3511 3517 3527 3529 3533 3539 3541 3547 3557 3559 3571 /;
-
plan tests => 6 # range
+ 1 # small number
+ 2 # medium numbers
@@ -58,7 +26,11 @@ ok(!is_aks_prime(-2), '-2 is not prime');
is( is_aks_prime(877), 1, "is_aks_prime(877) is true" );
# Perhaps let them know this is probably not a hung test?
-# This runs in milliseconds on an i3930K, but many seconds on an UltraSPARC.
+# This runs in milliseconds on an i3930K, but 1.5 minutes on an UltraSPARC.
+# These are the smallest numbers that actually run the code, so I don't know
+# how to make them run any faster. On the 32-bit UltraSPARC, it's the mulmod
+# that is painfully slow.
+
#diag "Unfortunately these tests are very slow.";
# The first number that makes it past the sqrt test to actually run.
--
Alioth's /usr/local/bin/git-commit-notice on
/srv/git.debian.org/git/pkg-perl/packages/libmath-prime-util-perl.git
_______________________________________________
Pkg-perl-cvs-commits mailing list
Pkg-perl-cvs-commits@lists.alioth.debian.org
http://lists.alioth.debian.org/cgi-bin/mailman/listinfo/pkg-perl-cvs-commits
