59 lines
1.7 KiB
CoffeeScript
59 lines
1.7 KiB
CoffeeScript
# You could have symmetric algorithms for max right and left
|
|
# truncatable numbers, but they lend themselves to slightly
|
|
# different optimizations.
|
|
|
|
max_right_truncatable_number = (n, f) ->
|
|
# This algorithm only evaluates 37 numbers for primeness to
|
|
# get the max right truncatable prime < 1000000. Its
|
|
# optimization is that it prunes candidates for
|
|
# the first n-1 digits before having to iterate through
|
|
# the 10 possibilities for the last digit.
|
|
if n < 10
|
|
candidate = n
|
|
while candidate > 0
|
|
return candidate if f(candidate)
|
|
candidate -= 1
|
|
else
|
|
left = Math.floor n / 10
|
|
while left > 0
|
|
left = max_right_truncatable_number left, f
|
|
right = 9
|
|
while right > 0
|
|
candidate = left * 10 + right
|
|
return candidate if candidate <= n and f(candidate)
|
|
right -= 1
|
|
left -= 1
|
|
throw Error "none found"
|
|
|
|
max_left_truncatable_number = (max, f) ->
|
|
# This is a pretty straightforward countdown. The first
|
|
# optimization here would probably be to cache results of
|
|
# calling f on small numbers.
|
|
is_left_truncatable = (n) ->
|
|
candidate = 0
|
|
power_of_ten = 1
|
|
while n > 0
|
|
r = n % 10
|
|
return false if r == 0
|
|
n = Math.floor n / 10
|
|
candidate = r * power_of_ten + candidate
|
|
power_of_ten *= 10
|
|
return false unless f(candidate)
|
|
true
|
|
do ->
|
|
n = max
|
|
while n > 0
|
|
return n if is_left_truncatable n, f
|
|
n -= 1
|
|
throw Error "none found"
|
|
|
|
is_prime = (n) ->
|
|
return false if n == 1
|
|
return true if n == 2
|
|
for d in [2..n]
|
|
return false if n % d == 0
|
|
return true if d * d >= n
|
|
|
|
|
|
console.log "right", max_right_truncatable_number(999999, is_prime)
|
|
console.log "left", max_left_truncatable_number(999999, is_prime)
|