Anonymous user
Find largest left truncatable prime in a given base: Difference between revisions
Find largest left truncatable prime in a given base (view source)
Revision as of 16:34, 11 December 2020
, 3 years ago→{{header|Nim}
m (C code requires GMP library) |
|||
Line 1,210:
17 13563641583101</pre>
=={{header|Nim}}==
{{libheader|bignum}}
<lang Nim>import bignum, strformat
const
Primes = [2, 3, 5, 7, 11, 13, 17]
Digits = "0123456789abcdefghijklmnopqrstuvwxyz"
#---------------------------------------------------------------------------------------------------
func isProbablyPrime(n: Int): bool =
## Return true if "n" is not definitively composite.
probablyPrime(n, 25) != 0
#---------------------------------------------------------------------------------------------------
func maxLeftTruncablePrime(base: int): Int =
## Return the maximum left truncable prime for given base.
let base = base.int32
var primes: seq[Int]
# Initialize primes with one digit in given base.
for p in Primes:
if p < base:
primes.add(newInt(p))
else:
break
# Build prime list with one more digit per generation.
var next: seq[Int]
while true:
# Build the next generation (with one more digit).
for p in primes:
var pstr = ' ' & `$`(p, base) # ' ' as a placeholder for next digit.
for i in 1..<base:
pstr[0] = Digits[i]
let n = newInt(pstr, base)
if n.isProbablyPrime():
next.add(n)
if next.len == 0:
# No primes with this number of digits.
# Return the greatest prime in previous generation.
return max(primes)
# Prepare to build next generation.
primes = next
next.setLen(0)
#———————————————————————————————————————————————————————————————————————————————————————————————————
echo "Base Greatest left truncable prime"
echo "====================================="
for base in 3..17:
let m = maxLeftTruncablePrime(base)
echo &"{base:>3} {m}", if base > 10: " (" & `$`(m, base.int32) & ')' else: ""</lang>
{{out}}
<pre>Base Greatest left truncable prime
=====================================
3 23
4 4091
5 7817
6 4836525320399
7 817337
8 14005650767869
9 1676456897
10 357686312646216567629137
11 2276005673 (a68822827)
12 13092430647736190817303130065827539 (471a34a164259ba16b324ab8a32b7817)
13 812751503 (cc4c8c65)
14 615419590422100474355767356763 (d967ccd63388522619883a7d23)
15 34068645705927662447286191 (6c6c2ce2ceeea4826e642b)
16 1088303707153521644968345559987 (dbc7fba24fe6aec462abf63b3)
17 13563641583101 (6c66cc4cc83)</pre>
=={{header|PARI/GP}}==
| |||