123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130 |
- #!/usr/bin/perl
- # Smallest squarefree palindrome with exactly n distinct prime factors.
- # https://oeis.org/A046399
- # Known terms:
- # 1, 2, 6, 66, 858, 6006, 222222, 22444422, 244868442, 6434774346, 438024420834, 50146955964105, 2415957997595142, 495677121121776594, 22181673755737618122, 8789941164994611499878
- # Corrected term:
- # a(15) = 5521159517777159511255
- # New term found by Michael S. Branicky:
- # a(16) = 477552751050050157255774
- # Lower-bounds:
- # a(17) > 252020044615415406440021243
- # a(17) > 252020044615424516440020252
- # Timings:
- # a(12) is found in 0.2 seconds
- # a(13) is found in 6.5 seconds
- # a(14) is found in 9.7 seconds
- # a(15) is found in 17 minutes
- # While searching for a(17), it took 9 hours to check the range [63005011153853239757078527, 126010022307706479514157054].
- # While searching for a(17), it took 33 hours to check the range [126010022307707703220010621, 252020044615415406440021243]
- # Tried to sieve the range [252020044615424516440020252, 282020044615424516440020282], but the program didn't finish after 8 hours... (I had to stop the program after 8 hours)
- use 5.020;
- use ntheory qw(:all);
- use experimental qw(signatures);
- use Math::GMPz;
- sub squarefree_omega_palindromes ($A, $B, $k, $callback) {
- $A = vecmax($A, pn_primorial($k));
- $A = Math::GMPz->new("$A");
- my $u = Math::GMPz::Rmpz_init();
- my $v = Math::GMPz::Rmpz_init();
- sub ($m, $lo, $k) {
- Math::GMPz::Rmpz_tdiv_q($u, $B, $m);
- Math::GMPz::Rmpz_root($u, $u, $k);
- my $hi = Math::GMPz::Rmpz_get_ui($u);
- if ($lo > $hi) {
- return;
- }
- if ($k == 1) {
- Math::GMPz::Rmpz_cdiv_q($u, $A, $m);
- if (Math::GMPz::Rmpz_fits_ulong_p($u)) {
- $lo = vecmax($lo, Math::GMPz::Rmpz_get_ui($u));
- }
- elsif (Math::GMPz::Rmpz_cmp_ui($u, $lo) > 0) {
- if (Math::GMPz::Rmpz_cmp_ui($u, $hi) > 0) {
- return;
- }
- $lo = Math::GMPz::Rmpz_get_ui($u);
- }
- if ($lo > $hi) {
- return;
- }
- foreach my $p (@{primes($lo, $hi)}) {
- Math::GMPz::Rmpz_mul_ui($v, $m, $p);
- my $s = Math::GMPz::Rmpz_get_str($v, 10);
- if ($s eq reverse($s)) {
- my $r = Math::GMPz::Rmpz_init_set($v);
- say("Found upper-bound: ", $r);
- $B = $r if ($r < $B);
- $callback->($r);
- }
- }
- return;
- }
- my $z = Math::GMPz::Rmpz_init();
- foreach my $p (@{primes($lo, $hi)}) {
- if ($p == 5 and Math::GMPz::Rmpz_even_p($m)) {
- ## last digit can't be zero
- }
- else {
- Math::GMPz::Rmpz_mul_ui($z, $m, $p);
- __SUB__->($z, $p+1, $k-1);
- }
- }
- }->(Math::GMPz->new(1), 2, $k);
- }
- sub a($n) {
- if ($n == 0) {
- return 1;
- }
- #my $x = Math::GMPz->new(pn_primorial($n));
- my $x = Math::GMPz->new("252020044615424516440020252");
- #my $y = (5*$x)>>2;
- my $y = Math::GMPz->new("282020044615424516440020282");
- while (1) {
- say("Sieving range: [$x, $y]");
- my @v;
- squarefree_omega_palindromes($x, $y, $n, sub ($k) {
- push @v, $k;
- });
- @v = sort { $a <=> $b } @v;
- if (scalar(@v) > 0) {
- return $v[0];
- }
- $x = $y+1;
- $y = (5*$x)>>2;
- }
- }
- foreach my $n (17) {
- say "a($n) = ", a($n);
- }
|