Problem 35 - 循環素数

簡単そうなのからいくよ。

Problem 35 - Project Euler

The number, 197, is called a circular prime because all rotations of the digits: 197, 971, and 719, are themselves prime.

There are thirteen such primes below 100: 2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, and 97.

How many circular primes are there below one million?

197は循環素数?と呼ばれる。197,971,719と、ぐるっと回しても、ぜーんぶ素数だからだ。

100以下では2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, 97の13個がある。

100万以下の循環素数は何個ある?

循環素数と呼ばれてるのかどうかは知らない(汗


今まで作ってきたユーティリティを総動員で解いてみる。

(define (split-map f l)
  (letrec ((iter (lambda (acc l)
                   (if (null? l)
                       '()
                       (cons (f acc l)
                             (iter (cons (car l) acc) (cdr l)))))))
          (iter '() l)))

(define (number->list n . base)
  (letrec ((b (if (null? base) 10 (car base)))
           (iter (lambda (acc n)
                   (let ((q (quotient n b))
                         (m (cons (modulo n b) acc)))
                        (if (zero? q)
                            m
                            (iter m q))))))
          (iter '() n)))

(define (list->number l)
  (letrec ((iter (lambda (l cont)
                  (if (null? l)
                      (cont 0 0)
                      (iter (cdr l) (lambda (sum k)
                                      (cont (+ (* (car l) (expt 10 k)) sum)
                                            (+ k 1))))))))
          (iter l (lambda (sum k) sum))))

(define (k n)
  (inexact->exact (floor (/ (log n) (log 10)))))

(define (prime? n)
  (define (trial-divisor t)
    (or (< n (* t t))
        (and (not (zero? (remainder n t)))
             (trial-divisor (+ t 2)))))
  (if (even? n)
      (= n 2)
      (trial-divisor 3)))
  • split-map
    • 分割map。新登場。
    • 前のリストが逆順になっちゃうんだよね。
  • number->list,list->number
    • 1234 <-> (1 2 3 4)とする。
  • k
    • 桁数。新登場。
  • prime?

というユーティリティ達を使って、

素数リストを作って > 数字を分解 > 循環したリストを作る > 数字に戻す > 素数判定 > 全部生き残ったら > リストに追加 > いくつあるかな?

という流れ。

(length 
  (fold-right
          (lambda (x acc)
            (if (= (k (- x 1))
                   (length (filter prime?
                                   (cdr (map (lambda (l)
                                               (list->number l))
                                             (split-map (lambda (f b)
                                                          (append b (reverse f)))
                                                        (number->list x)))))))

                (cons x acc)
                acc))
          '()
          (filter prime? (iota (- 1000000 1) 2)))) ; 55

うは。

同じ計算を何度もしてる所があるので、なんとかしたい所。