Problem29

30分プログラム、その302。Problem29 via Project Euler。

2 ≤ a ≤ 5 と 2 ≤ b ≤ 5について, abを全て考えてみよう:

• 2^2=4, 2^3=8, 2^4=16, 2^5=32
• 3^2=9, 3^3=27, 3^4=81, 3^5=243
• 4^2=16, 4^3=64, 4^4=256, 4^5=1024
• 5^2=25, 5^3=125, 5^4=625, 5^5=3125

これらを小さい順に並べ, 同じ数を除いたとすると, 15個の項を得る:
4, 8, 9, 16, 25, 27, 32, 64, 81, 125, 243, 256, 625, 1024, 3125

2 ≤ a ≤ 100, 2 ≤ b ≤ 100 で同じことをしたときいくつの異なる項が存在するか?

特に工夫せずに、全部で計算して数えてみた。

ところで、Project Eulerを紙とペンで解いている人が結構いて驚いた。

使い方

$ time gosh problem29.scm
9183
gosh problem29.scm  8.17s user 0.22s system 61% cpu 13.730 total

ソースコード

#! /opt/local/bin/gosh
;; -*- mode:scheme; coding:utf-8 -*-
;;
;; problem29.scm -
;;
;; Copyright(C) 2008 by mzp
;; Author: MIZUNO Hiroki / mzpppp at gmail dot com
;; http://howdyworld.org
;;
;; Timestamp: 2008/05/11 21:44:31
;;
;; This program is free software; you can redistribute it and/or
;; modify it under MIT Lincence.
;;
(use srfi-1)
(use util.combinations)
(use gauche.collection)

(define (range a b)
  (let1 size (+ (- b a) 1)
    (iota size a)))

(define (f a b)
  (let1 xs (range a b)
    (length
     (group-collection
      (map
       (lambda (xs) (expt (car xs) (cadr xs)))
       (cartesian-product (list xs xs)))))))

(define (main args)
  (print (f 2 100)))

参考

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