Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.forth > #60682

Rosetta: Truncatable primes

Show all headers | View raw

> A truncatable prime is a prime number that when you
> successively remove digits from one end of the prime, you are
> left with a new prime number; for example, the number 997 is
> called a left-truncatable prime as the numbers 997, 97, and 7
> are all prime. The number 7393 is a right-truncatable prime as
> the numbers 7393, 739, 73, and 7 formed by removing digits
> from its right are also prime. No zeroes are allowed in
> truncatable primes.
> 
> Task
> 
> The task is to find the largest left-truncatable and
> right-truncatable primes less than one million (base 10 is
> implied).
> 


(use srfi-41) ;; streams
(use streams-math)
(use streams-utils)
(use srfi-69) ;; hash tables
(use srfi-13) ;; string ops


(define primes-table (make-hash-table))

(define some-primes
  (stream-take-while
    (lambda(n)
      (hash-table-set! primes-table n #t)
      (< n 999999))
    prime-numbers-stream))


(define (check-right-trunc n)
  (let loop ((m n))
    (cond ((not (hash-table-exists? primes-table m)) 0)
          ((< m 10) n)
          (else (loop (fx/ m 10))))))

(define (check-left-trunc n)
  (let loop ((m n))
    (cond ((not (hash-table-exists? primes-table m)) 0)
          ((< m 10) n)
          (else
            (loop (string->number (string-copy (number->string m) 1)))))))

(define (compare func)
  (lambda(a b) (< (func a) (func b))))


(stream-maximum (compare check-right-trunc) some-primes)
739399

(stream-maximum (compare check-left-trunc) some-primes)
999907


-- 
I wrote until my fingers were blue, over and over: "Political
Correctness is a religion."  I proved it and showed you why it is so
important that Political Correctness is a religion.
 --- Bob Whitaker

Back to comp.lang.forth | Previous | Next — Next in thread | Find similar | Unroll thread

Thread

Rosetta: Truncatable primes "Robert L." <No_spamming@noWhere_7073.org> - 2017-06-13 07:23 +0000
  Re: Rosetta: Truncatable primes "Robert L." <No_spamming@noWhere_7073.org> - 2017-06-13 07:46 +0000

csiph-web