#!/usr/bin/env perl
use strict;
use warnings;
use Test::More;
use Math::Prime::Util::GMP qw/moebius liouville totient jordan_totient
exp_mangoldt carmichael_lambda
znorder znprimroot is_primitive_root
chinese ramanujan_tau/;
my $extra = defined $ENV{EXTENDED_TESTING} && $ENV{EXTENDED_TESTING};
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 %totients = (
123456 => 41088,
123457 => 123456,
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;
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 @A002322 = (0,1,1,2,2,4,2,6,2,6,4,10,2,12,6,4,4,16,6,18,4,6,10,22,2,20,12,18,6,28,4,30,8,10,16,12,6,36,18,12,4,40,6,42,10,12,22,46,4,42,20,16,12,52,18,20,6,18,28,58,4,60,30,6,16,12,10,66,16,22,12,70,6,72,36,20,18,30,12,78,4,54,40,82,6,16,42,28,10,88,12,12,22,30,46,36,8,96,42,30,20,100,16,102,12,12,52,106,18,108,20,36,12,112,18,44,28,12,58,48,4,110,60,40,30,100,6,126,32,42,12,130,10,18,66,36,16,136,22,138,12,46,70,60,12,28,72,42,36,148,20,150,18,48,30,60,12,156,78,52,8,66,54,162,40,20,82,166,6,156,16,18,42,172,28,60,20,58,88,178,12,180,12,60,22,36,30,80,46,18,36,190,16,192,96,12,42,196,30,198,20);
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, 23436248, 28629150, 32505856, 38974100, 44015536, 52501944, 58335552, 69343956, 76759038, 89852664, 99168256, 115856200, 126078612, 147008442, 159761600, 183709944, 199526602, 229345006, 245825536, 282458442, 302637500, 343605152, 368321664],
# 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 @liouville_pos = (qw/24 51 94 183 294 629 1488 3684 8006 8510 32539 57240
103138 238565 444456 820134 1185666 3960407 4429677 13719505 29191963
57736144 134185856 262306569 324235872 563441153 1686170713 2489885844/);
my @liouville_neg = (qw/23 47 113 163 378 942 1669 2808 8029 9819 23863 39712
87352 210421 363671 562894 1839723 3504755 7456642 14807115 22469612
49080461 132842464 146060791 279256445 802149183 1243577750 3639860654/);
push @liouville_pos, (qw/1260238066729040 10095256575169232896/);
push @liouville_neg, (qw/1807253903626380 12063177829788352512/);
my %mangoldt = (
-13 => 1,
0 => 1,
1 => 1,
2 => 2,
3 => 3,
4 => 2,
5 => 5,
6 => 1,
7 => 7,
8 => 2,
9 => 3,
10 => 1,
11 => 11,
25 => 5,
27 => 3,
399981 => 1,
399982 => 1,
399983 => 399983,
823543 => 7,
83521 => 17,
130321 => 19,
);
my @mult_orders = (
[1, 35, 1],
[2, 35, 12],
[4, 35, 6],
[6, 35, 2],
[7, 35],
[2, "1000000000000031", 81788975100],
[1, 1, 1],
[0, 0],
[1, 0],
[25, 0],
[1, 1, 1],
[19, 1, 1],
[1, 19, 1],
[2, 19, 18],
[3, 20, 4],
[57,1000000003,189618],
[67,999999749,30612237],
[22,999991815,69844],
[10,2147475467,31448382],
[141,2147475467,1655178],
[7410,2147475467,39409],
[31407,2147475467,266],
[2, "2405286912458753", 1073741824], # Pari #1031
);
my %primroots = (
-11 => 2,
0 => undef,
1 => 0,
2 => 1,
3 => 2,
4 => 3,
5 => 2,
6 => 5,
7 => 3,
8 => undef,
9 => 2,
10 => 3, # 3 is the smallest root. Pari gives the other root 7.
1729 => undef, # Pari goes into an infinite loop.
5109721 => 94,
17551561 => 97,
90441961 => 113,
1407827621 => 2,
1520874431 => 17,
1685283601 => 164,
100000001 => undef, # Without an early exit, this will essentially hang.
"2232881419280027" => 6,
"14123555781055773271" => 6,
"89637484042681" => 335,
"9223372036854775837" => 5,
);
my %rtau = (
0 => 0,
1 => 1,
2 => -24,
3 => 252,
4 => -1472,
5 => 4830,
53 => -1596055698,
106 => 38305336752,
243 => 13400796651732,
16089 => "12655813883111729342208",
83456 => "130596522071273977247956992",
);
$rtau{123456} = "206775765874925539386458112" if $extra;
$rtau{982348} = "598906847188833667374229665444608" if $extra;
my @crts = (
[ [], 0 ],
[ [[4,5]], 4 ],
[ [[77,11]], 0 ],
[ [[0,5],[0,6]], 0 ],
[ [[14,5],[0,6]], 24 ],
[ [[10,11],[4,22],[9,19]], undef ],
[ [[77,13],[79,17]], 181 ],
[ [[2,3],[3,5],[2,7]], 23 ],
[ [[10,11],[4,12],[12,13]], 1000 ],
[ [[42,127],[24,128]], 2328 ], # Some tests from Mod::Int
[ [[32,126],[23,129]], 410 ],
[ [[2328,16256],[410,5418]], 28450328 ],
[ [[1,10],[11,100]], 11 ],
[ [[11,100],[22,100]], undef ],
[ [[1753051086,3243410059],[2609156951,2439462460]], "6553408220202087311"],
[ [ ["6325451203932218304","2750166238021308"],
["5611464489438299732","94116455416164094"] ],
"1433171050835863115088946517796" ],
[ [ ["1762568892212871168","8554171181844660224"],
["2462425671659520000","2016911328009584640"] ],
"188079320578009823963731127992320" ],
[ [ ["856686401696104448","11943471150311931904"],
["6316031051955372032","13290002569363587072"] ],
"943247297188055114646647659888640" ],
[ [[-3105579549,3743000622],[-1097075646,1219365911]], "2754322117681955433"],
[ [ ["-925543788386357567","243569243147991"],
["-1256802905822510829","28763455974459440"] ],
"837055903505897549759994093811" ],
[ [ ["-2155972909982577461","8509855219791386062"],
["-5396280069505638574","6935743629860450393"] ],
"12941173114744545542549046204020289525" ],
[ [[3,5],[2,0]], undef ], # three tests that we handle zeros.
[ [[3,0],[2,3]], undef ],
[ [[3,5],[3,0],[2,3]], undef ],
);
plan tests => 1
+ 1 # moeb_vals
+ 1 + scalar(keys %totients)
+ scalar(keys %jordan_totients)
+ 1 # Small Carmichael Lambda
+ scalar(@liouville_pos) + scalar(@liouville_neg)
+ scalar(keys %mangoldt)
+ scalar(@mult_orders)
+ scalar(keys %primroots) + 1
+ 3 # is_primitive_root
+ scalar(keys %rtau)
+ scalar(@crts)
+ 10;
###### moebius
ok(!eval { moebius(0); }, "moebius(0)");
{
my @moebius = map { moebius($_) } (1 .. scalar @moeb_vals);
is_deeply( \@moebius, \@moeb_vals, "moebius 1 .. " . scalar @moeb_vals );
}
###### totient
{
my @phi = map { totient($_) } (0 .. $#A000010);
is_deeply( \@phi, \@A000010, "totient 0 .. $#A000010" );
}
while (my($n, $phi) = each (%totients)) {
is( totient($n), $phi, "euler_phi($n) == $phi" );
}
###### Jordan Totient
while (my($k, $tref) = each (%jordan_totients)) {
my @tlist = map { jordan_totient($k, $_) } 1 .. scalar @$tref;
is_deeply( \@tlist, $tref, "Jordan's Totient J_$k" );
}
###### Carmichael Lambda
{
my @lambda = map { carmichael_lambda($_) } (0 .. $#A002322);
is_deeply( \@lambda, \@A002322, "carmichael_lambda with range: 0, $#A000010" );
}
###### liouville
foreach my $i (@liouville_pos) {
is( liouville($i), 1, "liouville($i) = 1" );
}
foreach my $i (@liouville_neg) {
is( liouville($i), -1, "liouville($i) = -1" );
}
###### Exponential of von Mangoldt
while (my($n, $em) = each (%mangoldt)) {
is( exp_mangoldt($n), $em, "exp_mangoldt($n) == $em" );
}
###### znorder
foreach my $moarg (@mult_orders) {
my ($a, $n, $exp) = @$moarg;
my $zn = znorder($a, $n);
is( $zn, $exp, "znorder($a, $n) = " . ((defined $exp) ? $exp : "<undef>") );
}
###### znprimroot
while (my($n, $root) = each (%primroots)) {
is( znprimroot($n), $root, "znprimroot($n) == " . ((defined $root) ? $root : "<undef>") );
}
is( znprimroot("-100000898"), 31, "znprimroot(\"-100000898\") == 31" );
###### is_primitive_root
ok(!is_primitive_root(3,"1000000000000000000000000000057"), "3 is not a primitive root mod 10^30+57");
ok( is_primitive_root(5,"1000000000000000000000000000057"), "5 is a primitive root mod 10^30+57");
ok( is_primitive_root(3,"1000000000000000000000000000066"), "3 is a primitive root mod 10^30+66");
###### Various with specific values
is(totient("9082348072348972344232348972345"),"6196599862139600370393700256064", "totient(9082348072348972344232348972345)");
is(jordan_totient(4,"9082348072348972344232348972345"),"6790726211626980360097015112160435536604703765653198944780917706227632058693872718134564711592636975392545473161803366400000", "jordan_totient(4,9082348072348972344232348972345)");
is(carmichael_lambda("9082348072348972344232348972345"),"129095830461241674383202088668", "carmichael_lambda(9082348072348972344232348972345)");
is(totient("9082348072348972344232348972353"),"5682424092695951433712276501440", "totient(9082348072348972344232348972353)");
is(jordan_totient(7,"9082348072348972344232348972353"),"5095518312757196744226274674573606050126361160581316878353842679128612307851086686674388236784494856239490781063311007858142493527563560083079291494558455443094226241877357726178655478871147887413922557679205648656960", "jordan_totient(7,9082348072348972344232348972353)");
is(carmichael_lambda("9082348072348972344232348972353"),"118383835264498988202339093780", "carmichael_lambda(9082348072348972344232348972353)");
is(moebius("9082348072348972344232348972353"),-1,"moebius(9082348072348972344232348972353)");
is(liouville("9082348072348972344232348972353"),-1,"liouville(9082348072348972344232348972353)");
is(znorder(17,"100000000000000000000000065"),"11018158296270848614660","znorder(17,100000000000000000000000065)");
#is(znprimroot("1000000000000000000000000000066"),3,"znprimroot(1000000000000000000000000000066)");
is(znprimroot("9218092345892375982375972365235234234238"),7,"znprimroot(9218092345892375982375972365235234234238)");
###### Ramanujan Tau
while (my($n, $tau) = each (%rtau)) {
is( ramanujan_tau($n), $tau, "Ramanujan Tau($n) = $tau" );
}
###### chinese
foreach my $carg (@crts) {
my($aref, $exp) = @$carg;
my $crt = chinese(@$aref);
is( $crt, $exp, "crt(".join(",",map { "[@$_]" } @$aref).") = " . ((defined $exp) ? $exp : "<undef>") );
}