Problem41

30分プログラム、その314。Problem41 - Project Euler。

n桁の数がPandigitalであるとは, 1からnまでの数を各桁に1つずつもつことである. 例えば2143は4桁のPandigital数であり, かつ素数である.
n桁のPandigitalな素数の中で最大の数を答えよ.

nが大きいPanditital数から調べて最初の素数を出力するようにした。n=9から始めないといけないんだけれども、あまりにも数が大きすぎるのでn=7で試してみたら、正解した。これでよしとしよう。

使い方

gosh> (solve)
(7 6 5 2 4 1 3)

ソースコード

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

(use srfi-1)
(use util.combinations)

(define (prime? n)
  (case n
    ([1] #f)
    ([2] #t)
    (else
     (not (find
	   (lambda (x) (= 0 (modulo n x)))
	   (iota (floor->exact (sqrt n)) 2))))))
  
(define (panditital-for-each f n)
  "n桁のpanditital数の生成"
  (permutations-for-each f (reverse (iota n 1))))

(define (join xs)
  (fold (lambda(x y) (+ (* 10 y) x)) 0 xs))

(define (solve)
  (call/cc (lambda (break)
	     (map (lambda (n)
		    (panditital-for-each
		     (lambda (p)
		       (print p)
		       (if (prime? (join p))
			   (break p)))
		     n))
		  (reverse (iota 7 1))))))

参考

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