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

Groups > comp.lang.forth > #60683

Re: Rosetta: Truncatable primes

Show all headers | View raw

On 6/13/2017, Robert L. wrote:

> > 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


The prime isn't allowed to contain a zero.

(define (check-left-trunc n)
  (if (substring-index "0" (number->string n)) 0
    (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))))))))

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

-- 
Professor Goldman ... claimed that he and "most historians" regarded history
as a "weapon" to be used for "determining people's ideas and attitudes."
 --- Revilo P. Oliver, "The Price of the Head"

Back to comp.lang.forth | Previous | Next — Previous 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