#!/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>") );
}