experimental-projects/pseudoprimes/programs/carmichael_p==3_mod_80.pl

#!/usr/bin/perl

# Let p_1..p_k be distinct prime numbers and let n = p_1 * ... p_k.

# If the following conditions hold:
#   a) k == 1 (mod 4) or k == 3 (mod 4)
#   b) p_i == 3 (mod 80) for every i in {1..k}.
#   c) (p_i-1) | (n-1) for every i in {1..k}.
#   d) (p_i+1) | (n+1) for every i in {1..k}.

# Then n is a counter-example to Agrawal's conjecture.

# Carmichael numbers with all prime factors p == 3 (mod 80):
#   330468624532072027
#   1358406397003392026912594827
#   194462892367341977828363075381947

use 5.020;
use strict;
use warnings;

use Math::GMPz;
use ntheory      qw(:all);
use experimental qw(signatures);
use Math::Prime::Util::GMP;

sub pretest ($n) {

    my $rem = $n % 80;
    ($rem == 27 or $rem == 3) || return;

    foreach my $p (5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 89, 97) {
        if (Math::GMPz::Rmpz_divisible_ui_p($n, $p)) {
            return;
        }
    }

    return 1;
}

sub isok ($n) {    # Carmichael number

    pretest($n)                               || return;
    Math::Prime::Util::GMP::is_carmichael($n) || return;

    say "Candidate: $n";

    vecall { Math::GMPz->new($_) % 80 == 3 } Math::Prime::Util::GMP::factor($n);
}

sub isok2 ($n) {    # Lucas-Carmichael number

    pretest($n) || return;
    is_power($n) && return;

    say "Candidate: $n";

    my $t = $n + 1;
    vecall { my $p = Math::GMPz->new($_); ($p % 80 == 3) and ($t % ($p + 1) == 0) } Math::Prime::Util::GMP::factor($n);
}

my %seen;

while (<>) {
    next if /^\h*#/;
    /\S/ or next;
    my $n = (split(' ', $_))[-1];

    $n || next;

    next if ($n < ~0);
    next if (length($n) > 35);

#<<<
    next if ($n eq '7901877332421117604277233556001994548174031728058485631926375876865078028180049751981627864304181541061183590498201673009039329539171539230651776950727307');
    next if ($n eq '105216055594390884840438324972769319399722594046651360392070071794973423530188471087867855419188813164954561140227145977855514336985746250989366318940490798583710597151720075427387437940535767395296272532149397065590267303873620351321073058502920032770522836726669005262088263964215455869031740912313201227043');
    next if ($n eq '19045993130340238960516619526438196400111100205282343586730655491361145656716279531133626430434529862564012117981039124164877101697940176896586158417605958263877200848913504507021277579950088169124892268426377618637450987170274052735330198112915008469887168631791088882138462895976241696424319684682694737684482873770270608671767351537287446887784007605238000642746275451764369774864238904543361007743399722804711123700499775470397792907613698576886427753795632702382124771629436498075085327724596322478489152628386513622447595060065193541715781044580768866541780025974180911498465786060216591028528938508564952141307');
    next if ($n eq '6941543021392713730431668387068999032987505813628626223678951265009922979171494889619620919629218172938050022712650390231108995307237169269667644098333312684776469399924110119789527532161256933656112818109620945798457804143586629828296071826627003328849527952336389650813108369731049080747183836913592892951933560765345204468790419691959105305515726737868378312872715843312320064073674571001295106119373097331445689095722655847864191050899780290639922180983329597857624757187701943317347314318342630851888782724340309365489828447876503970224596096163190175586664838655752084811432643865453475409306234610422754846201955355349982116992680801631254169733179214516679698471486732095757632702985749004267668618407596194879010235811205069773345370151540294560707067912911972617117872568917574563797510424723636252899372760040898527772334935423922327351299656281932266256675132502702322760435460536571309302586539469310861406622510368133332971804029286468542260235396204271045794929827474636467550655521103657096119618759746982193439030809406498947869770588717242290031299573971411197982166717351757954266001066384132372994264058429334563291496657469558139808375030168417007373133166391119553220773091860698215980720042621281779381114805103592526045494482900527480395872621990534353634675251867');
    next if ($n eq '2887148238050771212671429597130393991977609459279722700926516024197432303799152733116328983144639225941977803110929349655578418949441740933805615113979999421542416933972905423711002751042080134966731755152859226962916775325475044445856101949404200039904432116776619949629539250452698719329070373564032273701278453899126120309244841494728976885406024976768122077071687938121709811322297802059565867');
#>>>

    Math::Prime::Util::GMP::is_pseudoprime($n, 2) || next;

    $n = Math::GMPz::Rmpz_init_set_str($n, 10);

    if (isok($n)) {
        say "\n$n\n" if !$seen{$n}++;
    }
}