Probem37

30分プログラム、その310。Problem37 - ProjectEuler。

3797は面白い性質を持っている. まずそれ自身が素数であり, 左から右に桁を除いたときに全て素数になっている (3797, 797, 97, 7). 同様に右から左に桁を除いたときも全て素数である (3797, 379, 37, 3).
右から切り詰めても左から切り詰めても素数になるような素数は11個しかない. 総和を求めよ.
注: 2, 3, 5, 7を切り詰め可能な素数とは考えない.

ダメだ。10個までしかどうしても見付からない。あと、1個か。何か見落しがあるんだろうか。

使い方

$ gosh problem37.scm
0 23
1 37
2 53
3 73
4 313
5 317
6 373
7 797
8 3137
9 3797
^C*** UNHANDLED-SIGNAL-ERROR: unhandled signal 2 (SIGINT)

ソースコード

#! /opt/local/bin/gosh
;; -*- mode:scheme; coding:utf-8 -*-
;;
;; problem37.scm -
;;
;; Copyright(C) 2008 by mzp
;; Author: MIZUNO Hiroki / mzpppp at gmail dot com
;; http://howdyworld.org
;;
;; Timestamp: 2008/05/25 21:03:47
;;
;; This program is free software; you can redistribute it and/or
;; modify it under MIT Lincence.
;;

(use srfi-1)
(define (prime? n)
  (cond
   ([= n 2] #t)
   ([<= 2 n]
    (every (lambda (x) (not (= (modulo n x) 0))) 
	   (iota (- (ceiling->exact (sqrt n)) 1) 2)))
   (else #f)))
  

(define (shift n)
  (floor->exact (/. n 10)))

(define (log10 n)
  (/ (log n) (log 10)))

(define (r-shift n)
  (let1 w (expt 10 (floor->exact (log10 n)))
    (modulo n w)))

(define (shift-list n)
  (unfold (cut = <> 0)
	  identity
	  (cut shift <>)
	  n))

(define (rshift-list n)
  (unfold (cut = <> 0)
	  identity
	  (cut r-shift <>)
	  n))

(define (satisfy? n)
  (and (every prime? (shift-list n))
       (every prime? (rshift-list n))))

(define (loop c sum n)
  (cond
   ([= c 11] sum)
   ([satisfy? n]
    (print c " " n)
    (loop (+ c 1) (+ sum n) (+ n 1)))
   (else
    (loop c sum (+ n 1)))))
  
(define (main _)
  (print (loop 0 0 10)))

参考

• 過去の30分プログラム
• Problem 37 - PukiWiki

追記(2008/05/26)

走らせ続けたら解けました。だいたい5分ぐらいかかりました。