Find largest left truncatable prime in a given base: Difference between revisions

Content added Content deleted
(→‎{{header|Perl 6}}: make it racy)
Line 1,003: Line 1,003:


=={{header|Julia}}==
=={{header|Julia}}==
This solution keeps candidate values in an array. A new digit is added with each generation, removing the previous generation's primes from the front of the list (<tt>shift!</tt>) and adding new candidates to the end of the list (<tt>append!</tt>) with each generation. The maximum value yielded in each generation is tracked as a provisional answer. Once the array is emptied (because no digit could be added to any of the previous generation's primes to yield a prime), the algorithm is finished and the answer found.
This solution keeps candidate values in an array. A new digit is added with each generation, removing the previous generation's primes from the front of the list (<tt>popfirstt!</tt>) and adding new candidates to the end of the list (<tt>append!</tt>) with each generation. The maximum value yielded in each generation is tracked as a provisional answer. Once the array is emptied (because no digit could be added to any of the previous generation's primes to yield a prime), the algorithm is finished and the answer found.


This solution is limited to a base of 17, to keep the processing time to well under a minute (about 15 seconds on an old but decent quality notebook). (I've let it run to as high as 23, but that took something like 20 minutes as I was otherwise occupied.) I did attempt a few optimizations of this general approach (such as moving the logic of <tt>addmsdigit</tt> into <tt>lefttruncprime</tt> and being clever about identifying the maximum of a given generation) but none of these tweaks resulted in a significant improvement in efficiency.
This solution is limited to a base of 17, to keep the processing time to well under a minute (about 15 seconds on an old but decent quality notebook). (I've let it run to as high as 23, but that took something like 20 minutes as I was otherwise occupied.) I did attempt a few optimizations of this general approach (such as moving the logic of <tt>addmsdigit</tt> into <tt>lefttruncprime</tt> and being clever about identifying the maximum of a given generation) but none of these tweaks resulted in a significant improvement in efficiency.
<lang julia>using Primes
<lang julia>using Primes, Printf

function addmsdigit(p::Integer, b::Integer, s::Integer)
function addmsdigit(p::Integer, b::Integer, s::Integer)
a = Vector{typeof(p)}(0)
a = Vector{typeof(p)}()
q = p
q = p
for i in 1:(b-1)
for i in 1:(b-1)
Line 1,018: Line 1,018:
return a
return a
end
end

function lefttruncprime(pbase::Integer)
function lefttruncprime(pbase::Integer)
a = Vector{BigInt}(0)
a = Vector{BigInt}()
append!(a, primes(pbase - 1))
append!(a, primes(pbase - 1))
mlt = zero(BigInt)
mlt = zero(BigInt)
Line 1,028: Line 1,028:
s *= pbase
s *= pbase
for i in 1:length(a)
for i in 1:length(a)
p = shift!(a)
p = popfirst!(a)
append!(a, addmsdigit(p, pbase, s))
append!(a, addmsdigit(p, pbase, s))
end
end
Line 1,034: Line 1,034:
return mlt
return mlt
end
end

lo, hi = 3, 17
lo, hi = 3, 17
println("The largest left truncatable primes for bases", @sprintf(" %d to %d.", lo, hi))
println("The largest left truncatable primes for bases", @sprintf(" %d to %d.", lo, hi))
for i in lo:hi
for i in lo:hi
mlt = lefttruncprime(i)
mlt = lefttruncprime(i)
@printf("%10d %-30d (%s)\n", i, mlt, base(i, mlt))
@printf("%10d %-30d (%s)\n", i, mlt, string(mlt, base=i))
end</lang>
end
⚫
</lang>{{out}}

⚫
{{out}}
<pre>
<pre>
The largest left truncatable primes for bases 3 to 17.
The largest left truncatable primes for bases 3 to 17.
Retrieved from "https://rosettacode.org/wiki/Find_largest_left_truncatable_prime_in_a_given_base"