Problem46

30分プログラム、その320。Problem46 - Project Euler。

Christian Goldbachは全ての奇合成数は平方数の2倍と素数と和で表せると予想した.

• 9 = 7 + 2×1²
• 15 = 7 + 2×2²
• 21 = 3 + 2×3²
• 25 = 7 + 2×3²
• 27 = 19 + 2×2²
• 33 = 31 + 2×1²

後に, この予想は誤りであることが分かった.
平方数の2倍と素数の和で表せない最小の奇合成数を答えよ

1だろ。奇数1と奇数1の合成数で、最小の素数より小さいんだから。
というのは置いといて、奇数の無限リストと奇数の無限リストの積をそのまま作ると、無限リストの無限リストになってしまい、辿れなくなる。
そこで、無限オブ無限にならって、斜めに走査するようにした。

ところで、プログラミングGaucheが行方不明なんですけど、どこに置いたんでしょう?

使い方

$ gosh problem46.scm
0 0 9
1 0 15
2 0 21
....
56 22 5405
55 23 5537
54 24 5661
109 53 5777
gosh problem46.scm  14.01s user 0.36s system 72% cpu 19.789 total

ソースコード

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

(use util.stream)

(define (sieve xs)
  (let1 x (stream-car xs)
    (stream-cons x
		 (sieve (stream-filter
			 (lambda (n) (not (= (modulo n x) 0)))
			 (stream-cdr xs))))))

(define *primes* (sieve (stream-iota -1 2)))

(define (square? n)
  (let1 m (floor->exact (sqrt n))
    (= (* m m) n)))

(define (integer? n)
  (= (floor->exact n) n))

(define (satisfy? n)
  (let1 primes (stream-take-while (cut < <> n) *primes*)
    (stream-find (lambda(p)
		   (let1 m (/. (- n p) 2)
		     (and (integer? m) (square? m))))
		 primes)))

(define (odd n)
  (+ (* 2 n) 1))

(define (loop i j)
  (let* ([x (odd (+ i 1))]
	 [y (odd (+ j 1))]
	 [z (* x y)])
    (cond ((not (satisfy? z))
	   (print x " " y " " z))
	  ((>= i j) 
	   (print i " " j " " z)
	   (loop (- i 1) (+ j 1)))
	  (else 
	   (loop (+ i j 1) 0)))))

(define (main _)
  (loop 0 0))

参考

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