Problem 56 - Project Euler

30分プログラム、その333。Problem56 - ProjectEuler。

Googol (10¹⁰⁰)は非常に大きな数である: 1の後に0が100個続く. 100¹⁰⁰は想像を絶する. 1の後に0が200回続く. その大きさにも関わらず, 両者とも桁の和は1である.
a, b < 100について自然数a^bを考える. 桁の和の最大を答えよ.

最近、数字を桁ごとに分解する問題が多い気がする。
特に何事もなくあっさり解けた。

使い方

gosh> (solve 100)
972

ソースコード

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

(use srfi-1)

(define (int->list n)
  (if (= 0 n)
      '()
      (cons (modulo n 10)
	    (int->list (quotient n 10)))))

(define (map2 f xs ys)
  (append-map (lambda (y) (map (cut f <> y) xs))
	      ys))

(define (solve n)
  (let1 xs (iota (- n 1) 1)
    (apply max (map2 (lambda (a b) 
		       (apply + (int->list (expt a b))))
		     xs xs))))

参考

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