123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143 |
- #!/usr/bin/perl
- # Daniel "Trizen" Șuteu
- # Date: 12 January 2019
- # https://github.com/trizen
- # Generate the entire sequence of both-truncatable primes in a given base.
- # Optimization:
- # there are far fewer right-truncatable primes than are left-truncatable primes,
- # so we can generate only the RTPs and then check which ones are also LTPs.
- # Maximum value for each base is given in the following OEIS sequence:
- # https://oeis.org/A323137
- # Total number of primes that are both left-truncatable and right-truncatable in base n:
- # https://oeis.org/A323390
- # See also:
- # https://www.youtube.com/watch?v=azL5ehbw_24
- # https://en.wikipedia.org/wiki/Truncatable_prime
- # Related sequences:
- # https://oeis.org/A076586 - Total number of right truncatable primes in base n.
- # https://oeis.org/A076623 - Total number of left truncatable primes (without zeros) in base n.
- # https://oeis.org/A323390 - Total number of primes that are both left-truncatable and right-truncatable in base n.
- # https://oeis.org/A323396 - Irregular array read by rows, where T(n, k) is the k-th prime that is both left-truncatable and right-truncatable in base n.
- # New terms:
- #~ There are 27 both-truncatable primes in base 49 where largest is 6421
- #~ There are 235 both-truncatable primes in base 50 where largest is 297897697
- #~ There are 29 both-truncatable primes in base 51 where largest is 2399
- #~ There are 187 both-truncatable primes in base 52 where largest is 2276097403
- #~ There are 23 both-truncatable primes in base 53 where largest is 2281
- #~ There are 575 both-truncatable primes in base 54 where largest is 586812834217
- use 5.010;
- use strict;
- use warnings;
- use Math::GMPz;
- use ntheory qw(primes vecmax is_prob_prime);
- my $t = Math::GMPz::Rmpz_init_set_ui(1);
- my $sum = Math::GMPz::Rmpz_init_set_ui(0);
- sub digits2num {
- my ($arr, $base) = @_;
- Math::GMPz::Rmpz_set_ui($t, 1);
- Math::GMPz::Rmpz_set_ui($sum, 0);
- foreach my $d (@$arr) {
- Math::GMPz::Rmpz_addmul_ui($sum, $t, $d);
- Math::GMPz::Rmpz_mul_ui($t, $t, $base);
- }
- Math::GMPz::Rmpz_get_str($sum, 10);
- }
- sub is_left_truncatable {
- my ($n, $base) = @_;
- my @copy = @$n;
- for (my @arr = shift(@copy); @copy > 0; push(@arr, shift(@copy))) {
- is_prob_prime(digits2num(\@arr, $base)) || return 0;
- }
- return 1;
- }
- sub right_truncatable_primes {
- my ($p, $base) = @_;
- my @seq = ($p);
- foreach my $n (1 .. $base - 1) {
- my @next = ($n, @$p);
- if (is_prob_prime(digits2num(\@next, $base))) {
- push @seq, grep { is_left_truncatable($_, $base) } right_truncatable_primes(\@next, $base);
- }
- }
- return @seq;
- }
- sub both_truncatable_primes_in_base {
- my ($base) = @_;
- if ($base <= 2) {
- return;
- }
- my @right;
- foreach my $p (@{primes(2, $base - 1)}) {
- push @right, right_truncatable_primes([$p], $base);
- }
- map { digits2num($_, $base) } @right;
- }
- foreach my $base (3..30) {
- my @t = both_truncatable_primes_in_base($base);
- printf("There are %3d both-truncatable primes in base %2d where largest is %s\n", scalar(@t), $base, vecmax(@t));
- }
- __END__
- There are 2 both-truncatable primes in base 3 where largest is 23
- There are 3 both-truncatable primes in base 4 where largest is 11
- There are 5 both-truncatable primes in base 5 where largest is 67
- There are 9 both-truncatable primes in base 6 where largest is 839
- There are 7 both-truncatable primes in base 7 where largest is 37
- There are 22 both-truncatable primes in base 8 where largest is 1867
- There are 8 both-truncatable primes in base 9 where largest is 173
- There are 15 both-truncatable primes in base 10 where largest is 739397
- There are 6 both-truncatable primes in base 11 where largest is 79
- There are 35 both-truncatable primes in base 12 where largest is 105691
- There are 11 both-truncatable primes in base 13 where largest is 379
- There are 37 both-truncatable primes in base 14 where largest is 37573
- There are 17 both-truncatable primes in base 15 where largest is 647
- There are 22 both-truncatable primes in base 16 where largest is 3389
- There are 12 both-truncatable primes in base 17 where largest is 631
- There are 69 both-truncatable primes in base 18 where largest is 202715129
- There are 12 both-truncatable primes in base 19 where largest is 211
- There are 68 both-truncatable primes in base 20 where largest is 155863
- There are 18 both-truncatable primes in base 21 where largest is 1283
- There are 44 both-truncatable primes in base 22 where largest is 787817
- There are 13 both-truncatable primes in base 23 where largest is 439
- There are 145 both-truncatable primes in base 24 where largest is 109893629
- There are 16 both-truncatable primes in base 25 where largest is 577
- There are 47 both-truncatable primes in base 26 where largest is 4195880189
- There are 20 both-truncatable primes in base 27 where largest is 1811
- There are 77 both-truncatable primes in base 28 where largest is 14474071
- There are 13 both-truncatable primes in base 29 where largest is 379
- There are 291 both-truncatable primes in base 30 where largest is 21335388527
- There are 15 both-truncatable primes in base 31 where largest is 2203
- There are 89 both-truncatable primes in base 32 where largest is 1043557
- There are 27 both-truncatable primes in base 33 where largest is 2939
- There are 74 both-truncatable primes in base 34 where largest is 42741029
|