1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253 |
- #!/usr/bin/ruby
- # Generate right-truncatable primes in a given base.
- # See also:
- # https://oeis.org/A076586 -- Total number of right truncatable primes in base n.
- # https://oeis.org/A023107 -- Largest integer in which every prefix is prime in base n (written in base 10).
- # https://www.youtube.com/watch?v=azL5ehbw_24
- # https://en.wikipedia.org/wiki/Truncatable_prime
- func generate_from_prefix(p, base, digits) {
- var seq = [p]
- digits.each {|d|
- var num = (base*p + d)
- if (num.is_prime) {
- seq << __FUNC__(num, base, digits)...
- }
- }
- return seq
- }
- func right_truncatable_primes(base) { # finite sequence for each base
- var prime_digits = (base-1 -> primes) # prime digits < base
- var end_digits = (1 ..^ base -> grep { .is_coprime(base) })
- prime_digits.map {|p| generate_from_prefix(p, base, end_digits)... }\
- .sort
- }
- for n in (3..15) {
- var rtp = right_truncatable_primes(n)
- say ("There are #{'%3d' % rtp.len} right-truncatable primes in base #{'%2d' % n}, where largest is #{rtp.max}")
- }
- __END__
- There are 4 right-truncatable primes in base 3, where largest is 71
- There are 7 right-truncatable primes in base 4, where largest is 191
- There are 14 right-truncatable primes in base 5, where largest is 2437
- There are 36 right-truncatable primes in base 6, where largest is 108863
- There are 19 right-truncatable primes in base 7, where largest is 6841
- There are 68 right-truncatable primes in base 8, where largest is 4497359
- There are 68 right-truncatable primes in base 9, where largest is 1355840309
- There are 83 right-truncatable primes in base 10, where largest is 73939133
- There are 89 right-truncatable primes in base 11, where largest is 6774006887
- There are 179 right-truncatable primes in base 12, where largest is 18704078369
- There are 176 right-truncatable primes in base 13, where largest is 122311273757
- There are 439 right-truncatable primes in base 14, where largest is 6525460043032393259
- There are 373 right-truncatable primes in base 15, where largest is 927920056668659
|