123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162 |
- #!/usr/bin/perl
- # Composite numbers n such that phi(n) divides p*(n - 1) for some prime factor p of n-1.
- # https://oeis.org/A338998
- # Known terms:
- # 1729, 12801, 5079361, 34479361, 3069196417
- use 5.020;
- use strict;
- use warnings;
- use experimental qw(signatures);
- use Storable;
- use Math::GMPz;
- use ntheory qw(:all);
- use Math::Prime::Util::GMP;
- use experimental qw(signatures);
- use Math::Sidef qw(trial_factor);
- use List::Util qw(uniq);
- use POSIX qw(ULONG_MAX);
- my $carmichael_file = "cache/factors-carmichael.storable";
- my $carmichael = retrieve($carmichael_file);
- #~ sub my_euler_phi ($factors) { # assumes n is squarefree
- #~ Math::Prime::Util::GMP::vecprod(map { ($_ < ~0) ? ($_ - 1) : Math::Prime::Util::GMP::subint($_, 1) } @$factors);
- #~ }
- sub my_euler_phi ($factors) { # assumes n is squarefree
- state $t = Math::GMPz::Rmpz_init();
- state $u = Math::GMPz::Rmpz_init();
- Math::GMPz::Rmpz_set_ui($t, 1);
- foreach my $p (@$factors) {
- if ($p < ULONG_MAX) {
- Math::GMPz::Rmpz_mul_ui($t, $t, $p - 1);
- }
- else {
- Math::GMPz::Rmpz_set_str($u, $p, 10);
- Math::GMPz::Rmpz_sub_ui($u, $u, 1);
- Math::GMPz::Rmpz_mul($t, $t, $u);
- }
- }
- return $t;
- }
- sub is_smooth_over_prod ($n, $k) {
- state $g = Math::GMPz::Rmpz_init_nobless();
- state $t = Math::GMPz::Rmpz_init_nobless();
- Math::GMPz::Rmpz_set($t, $n);
- Math::GMPz::Rmpz_gcd($g, $t, $k);
- while (Math::GMPz::Rmpz_cmp_ui($g, 1) > 0) {
- Math::GMPz::Rmpz_remove($t, $t, $g);
- return 1 if Math::GMPz::Rmpz_cmp_ui($t, 1) == 0;
- Math::GMPz::Rmpz_gcd($g, $t, $g);
- }
- return 0;
- }
- my $t = Math::GMPz::Rmpz_init();
- my $nm1 = Math::GMPz::Rmpz_init();
- while (my ($key, $value) = each %$carmichael) {
- # length($key) <= 30 or next;
- Math::GMPz::Rmpz_set_str($nm1, $key, 10);
- Math::GMPz::Rmpz_sub_ui($nm1, $nm1, 1);
- my @factors = split(' ', $value);
- my $phi = my_euler_phi(\@factors);
- Math::GMPz::Rmpz_gcd($t, $phi, $nm1);
- Math::GMPz::Rmpz_divexact($t, $phi, $t);
- #~ if (Math::GMPz::Rmpz_divisible_p($nm1, $t)) {
- if (Math::GMPz::Rmpz_divisible_p($nm1, $t)) {
- if (is_prime(Math::GMPz::Rmpz_get_str($t, 10))) {
- say "\nFound term: $key\n";
- }
- else {
- say "$t -> ", $key;
- }
- }
- }
- __END__
- # No terms > 2^64 are known.
- # If we relax the problem such that k is allowed to be composite, then we have (k -> n):
- 256 -> 161053591977104597648385
- 4320 -> 1442607709754537310156481
- 276480 -> 121311396642375203328001
- 36664320 -> 18307378995828443136001
- 39243204 -> 522701579776994601985
- 164647296 -> 710498768604458891905
- 239368932 -> 166767515214109647553
- 239855616 -> 69331699150300274689
- 344198160 -> 26220447360756492481
- 470271360 -> 22577695684076482561
- 494534656 -> 9370403366634042163201
- 690069744 -> 26412091255782290298241
- 847888206 -> 508856401419300817312321
- 1008611352 -> 225751988643126523201
- 1022867120 -> 151320171400394261761
- 1270746144 -> 1973514672419436576001
- 1355878368 -> 25043558587894400823361
- 1713960000 -> 405475097425913520001
- 2595175200 -> 79919351614524024001
- 3936306240 -> 22695373452873769921
- 4414596480 -> 2819631734736201434649601
- 4766062840 -> 305022961592329915047961
- 5256049760 -> 1454162635820073015201
- 6723894240 -> 23152815997129790193601
- 9337407520 -> 588513459619254160321
- 12358835370 -> 271556534518852228430401
- 14172416640 -> 57199945443705577825921
- 14385833280 -> 8449460360571792219841
- 20042190000 -> 3976684712865158490001
- 22016352600 -> 43988320199517413227201
- 23021417472 -> 2484569421264140859210670081
- 35963136000 -> 3221275513469123100672001
- 42830346240 -> 38223250373318642652303361
- 47342232000 -> 2479639741736856792912001
- 100711683072 -> 172991335211656109051905
- 225735802880 -> 24454143142535092272994713601
- 299747952000 -> 3373971932766269202480001
- 521132748000 -> 24305672075484052148160001
- 638306611200 -> 244560890510134115626598401
- 648369446400 -> 21566311675749133571835648001
- 768266286228 -> 19674209294344913441970817
- 938064067200 -> 33803763411350231745638401
- 1050025132800 -> 4775814557195289074611201
- 1127001600000 -> 77755530778217753011200001
- 1231491998240 -> 1585372177726779981269921
- 1299266121600 -> 566296873170734780865792001
- 1712586456000 -> 18856002135543697675152001
- 3473510584320 -> 256551983459660482787450881
- 6546891384000 -> 60060884070685995775533024001
- 7062492272640 -> 169302315858010163156179353601
- 10390842000000 -> 224159025932793824796000001
- 11788391160000 -> 1836659845422904698410760001
- 14246648367828 -> 7429200724594400259443892735745
- 20751621203808 -> 6753985548147606751087157673985
- 28322297280000 -> 22584599278031754549573120001
- 43712316942336 -> 5423553691041141223181881345
- 53989739274240 -> 26468027537347458252574433281
- 144645490376640 -> 22031534549990632963014227521
- 194461205316000 -> 16267018441058472048178342860001
- 231593852160000 -> 280329366963716628966650880001
- 1004376125491200 -> 851213068769837939865599760537601
|