1#!/usr/bin/env perl
2use strict;
3use warnings;
4
5use Test::More;
6use Math::Prime::Util qw/euler_phi jordan_totient carmichael_lambda
7                         divisor_sum moebius inverse_totient/;
8
9#my $extra = defined $ENV{EXTENDED_TESTING} && $ENV{EXTENDED_TESTING};
10#my $usexs = Math::Prime::Util::prime_get_config->{'xs'};
11#my $usegmp= Math::Prime::Util::prime_get_config->{'gmp'};
12my $use64 = Math::Prime::Util::prime_get_config->{'maxbits'} > 32;
13$use64 = 0 if $use64 && 18446744073709550592 == ~0;
14
15my %totients = (
16    -123456 => 0,
17     123456 => 41088,
18     123457 => 123456,
19  123456789 => 82260072,
20);
21my @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);
22#@totients{0..$#A000010} = @A000010;
23
24my @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);
25
26plan tests => 2 + 10 + scalar(keys %totients)
27                + 1 # Small Carmichael Lambda
28                + 5 # inverse_totient
29                ;
30
31###### euler_phi (totient)
32{
33  my @phi = map { euler_phi($_) } (0 .. $#A000010);
34  is_deeply( \@phi, \@A000010, "euler_phi 0 .. $#A000010" );
35}
36{
37  my @phi = euler_phi(0, $#A000010);
38  is_deeply( \@phi, \@A000010, "euler_phi with range: 0, $#A000010" );
39}
40{
41  my $s = 0;
42  $s += $_ for euler_phi(1, 240);
43  is($s, 17544, "sum of totients to 240");
44}
45while (my($n, $phi) = each (%totients)) {
46  is( euler_phi($n), $phi, "euler_phi($n) == $phi" );
47}
48is_deeply( [euler_phi(0,0)], [0],     "euler_phi(0,0)" );
49is_deeply( [euler_phi(1,0)], [],      "euler_phi with end < start" );
50is_deeply( [euler_phi(0,1)], [0,1],   "euler_phi 0-1" );
51is_deeply( [euler_phi(1,2)], [1,1],   "euler_phi 1-2" );
52is_deeply( [euler_phi(1,3)], [1,1,2], "euler_phi 1-3" );
53is_deeply( [euler_phi(2,3)], [1,2],   "euler_phi 2-3" );
54is_deeply( [euler_phi(10,20)], [4,10,4,12,6,8,8,16,6,18,8], "euler_phi 10-20" );
55is_deeply( [euler_phi(1513,1537)],
56   [qw/1408 756 800 756 1440 440 1260 576 936 760 1522 504 1200 648
57       1016 760 1380 384 1530 764 864 696 1224 512 1456/],
58           "euler_phi(1513,1537)" );
59# negative euler_phi returns zero
60is_deeply( [euler_phi(-5,5)], [0,0,0,0,0,0,1,1,2,2,4], "euler_phi -5 to 5" );
61
62###### Carmichael Lambda
63{
64  my @lambda = map { carmichael_lambda($_) } (0 .. $#A002322);
65  is_deeply( \@lambda, \@A002322, "carmichael_lambda with range: 0, $#A000010" );
66}
67
68###### Inverse Totient
69{
70  my $tot = 0;
71  $tot += 0+inverse_totient($_) for 0..100;
72  is($tot, 198, "Totient count 0-100 = 198");
73  is(0+inverse_totient(1728), 62, "inverse_totient(1728) = 62");
74  is(0+inverse_totient(362880), 1138, "inverse_totient(9!) = 1138");
75  is_deeply( [inverse_totient(10000008)], [10555583,15000039,21111166,30000078], "inverse_totient(10000008)" );
76  ok( scalar(grep { $_ == 123456789} inverse_totient(82260072)) == 1, "inverse_totient(82260072) includes 123456789" );
77}
78