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

Groups > comp.lang.forth > #60682 > unrolled thread

Rosetta: Truncatable primes

Back to article view | Back to comp.lang.forth

Contents

  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

#60682 — Rosetta: Truncatable primes

> 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

[toc] | [next] | [standalone]

#60683

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"

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.forth

csiph-web