M.Hiroi's Home Page

Memorandum

プログラミングに関する覚え書や四方山話です。
[ Home | 2017年 1月, 6月, 8月 ]

2017 年 8 月

8月13日

●献本お礼

このたび、笹川さんが電子書籍「まったく初めての人のためのISLisp」を出版されました。ご出版、おめでとうございます。先日、笹川さんからご著書を献本して頂きました。本当にありがとうございました。本書は Lisp のエッセンスがギュッと詰まっていて、最後まで楽しく読むことができました。二次方程式の解や行列の計算など、数学を題材にしているところもよかったです。やっぱり Lisp プログラミングは面白いな、と改めて思いました。


2017 年 6 月

6月25日

●新しいパソコン

今まで使っていたパソコン (Windows 7, 32 bit) が壊れたので、新しいパソコン (Windows 10, 64 bit) を買いました。CPU は CORE i5 (2.3 GHz) ですが、メモリを 8 G byte 搭載したのでパソコンの動作は快適です。特に、パソコンの起動やシャットダウンが Windows 7 よりも格段に速くなったのには驚きました。

せっかくメモリをたくさん搭載したので、VirtualBox のメモリを 2 G byte に設定して、いろいろな Linux を試してみました。この場合、ライブCDの部屋 のライブイメージを使うと簡単です。作者様に深く感謝いたします。たいていの Linux は動作するのですが、重量級のデスクトップを VirtulaBox で動かすには、CPU のパワーがちょっと足りないようです。そこで、今回は xubuntu をインストールすることにしました。

ご参考までに「たらいまわし関数」の実行結果を下表に示します。

表 : tak(22, 11, 0) の結果
処理系
Python (ver 2.7.12+)71.0
Ruby (ver 2.3.1p112)29.4
Gauche (ver 0.9.4)22.9
ocamlc (ver 4.02.3)16.6
SBCL (ver 1.3.3)5.20
JavaScript (Node.js v4.2.6)3.17
SML/NJ (ver 110.79)3.14
Julia (ver 0.4.7)2.06
Go (ver 1.6.3)1.97
SBCL (最適化)1.67
C# (Mono, ver 4.2.1.0)1.63
GCC -O2 (ver 6.2.0)1.40
Clang -O2 (ver 3.8.1)1.20
Rust -O (ver 1.18)1.20
ocamlopt (ver 4.02.3)1.11

ホスト OS との比較は GCC と Rust しか試していませんが、ほぼ同じ実行結果になりました。VirtualBox は本当に凄いなあ、と改めて実感しました。Rust は Mozilla が開発しているプログラミング言語で、最近 M.Hiroi が関心を持っている言語のひとつです。Windows, MacOS, Linux で動作するので、興味のある方は調べてみてください。

さて、最近は JavaScript や TypeScript を勉強しているのですが、そこで役に立っているのが Visual Studio Code (VSCode) というエディタです。

Microsoft 社が開発しているオープンソースのエディタで、Windows だけではなく MacOS や Linux でも動作します。高機能なエディタなのですが、デフォルトのままでも便利に使うことができます。TypeScript の場合、プログラムを打ち込むたびに構文をチェックしてくれるので、勉強がとてもはかどりました。xyzzy や Emacs もいいのですが、しばらくは VSCode を使ってみようかなと思っています。


2017 年 1 月

1月7日

●区間ふるい

自然数 n 以上 m 未満の区間にある素数を求めることを考えます。この場合、sqrt(m) 以下の素数表があれば、「エラトステネスの篩」で高速に求めることができます。参考 URL 1 によると、これを「区間ふるい」と呼ぶそうです。

一般に、エラトステネスの篩は配列を使った方が高速に動作しますが、ここではリストを使って簡単にプログラムを作ることにします。まあ、区間の幅が大きくなければ、リストでもそこそこに動作します。Gauche (Scheme) でプログラムを作ると次のようになります。

リスト : 区間ふるい

(use srfi-1)
(use math.prime)

;; 反転して連結する
(define (reverse-append xs ys)
  (let loop ((xs xs) (ys ys))
    (if (null? xs)
        ys
        (loop (cdr xs) (cons (car xs) ys)))))

;; 素数表の生成
(define (first-sieve n)
  (let loop ((xs (iota (- n 2) 2)) (ps '()))
    (if (> (* (car xs) (car xs)) n)
        (reverse-append ps xs)
        (loop (remove (lambda (x) (zero? (mod x (car xs)))) (cdr xs))
              (cons (car xs) ps)))))

;; 素数表
(define prime-list (first-sieve 65536))

;; 区間ふるい
(define (segment-sieve low high)
  (let loop ((xs (iota (- high low) low)) (ps prime-list))
    (if (>= (* (car ps) (car ps)) high)
        xs
        (loop (remove (lambda (x) (and (zero? (mod x (car ps)))
                                       (not (= x (car ps)))))
                      xs)
              (cdr ps)))))

(define (segment-sieve1 low high)
  (let loop ((xs (iota (- high low) low)) (ps *primes*))
    (if (>= (* (car ps) (car ps)) high)
        xs
        (loop (remove (lambda (x) (and (zero? (mod x (car ps)))
                                       (not (= x (car ps)))))
                      xs)
              (cdr ps)))))

関数 first-sieve は 2 以上 n 未満の素数表を作ります。たとえば、65536 までの素数表を作れば、符号付き 32 bit 整数の範囲であれば、区間ふるいを実行することができます。関数 segment-prime は low 以上 high 未満の素数を区間ふるいで求めます。区間と素数表が重なる場合があるので、remove で要素を削除するとき、要素 x が素数で割り切れるだけではなく、x が素数自身ではないことを確認しています。segment-sieve1 は Gauche の素数列 (無限リスト) を使ったバージョンです。

簡単な実行例を示します。

gosh> (segment-sieve 2 100)
(2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97)
gosh> (segment-sieve #x7fffff00 #x7fffffff)
(2147483399 2147483423 2147483477 2147483489 2147483497 2147483543 2147483549 
2147483563 2147483579 2147483587 2147483629)
gosh> (segment-sieve1 2 100)
(2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97)
gosh> (segment-sieve1 #x80000000 #x80000100)
(2147483659 2147483693 2147483713 2147483743 2147483777 2147483783 2147483813 
2147483857 2147483867 2147483869 2147483887 2147483893)

最後の例のように、segment-sieve1 は符号付き 32 bit 整数の上限値 (2147483647) を超えても区間ふるいを実行することができます。

●参考 URL

  1. 区間ふるい, (各種アルゴリズムの C++ による実装, 前原貴憲さん)

1月3日

1 月 1 日に出題したパズルの 解答 です。


1月1日

あけましておめでとうございます

旧年中は大変お世話になりました
本年も M.Hiroi's Home Page をよろしくお願い申し上げます


●新春パズル「素数で遊ぼう」

29 と 2017 は素数なので、それに関する問題を考えてみました。

  1. 29 は 10 番目の素数 (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, ...) です。2017 は何番目の素数でしょうか。
  2. 2017 番目の素数を求めてください。
  3. 2017 の各桁を足すと 10 になります。各桁の総和が 10 になる 5000 以下の素数を求めてください。
  4. 各桁の総和が 29 になる 10000 以下の素数を求めてください。
  5. 差が 2 である素数の組を「双子素数 (twin prime)」といいます。(29, 31) は 5 番目の双子素数です。2017 番目の双子素数を求めてください。

●解答

●Ruby

Ruby (ruby 2.3) には素数を扱うライブラリ prime と遅延評価を行う Enumerator::Lazy があるので簡単に答えを求めることができます。

irb> require 'prime'
=> true
irb> Prime.each.take_while {|x| x <= 2017}.length
=> 306
irb> Prime.each.take(2017)[-1]
=> 17539
irb> def digitSum(x)
irb> a = 0
irb> while x > 0
irb> a += x % 10
irb> x /= 10
irb> end
irb> a
irb>end
=> :digitSum
irb> Prime.each.take_while{|x| x <= 5000}.select{|x| digitSum(x) == 10}
=> [19, 37, 73, 109, 127, 163, 181, 271, 307, 433, 523, 541, 613, 631, 811, 1009,
 1063, 1117, 1153, 1171, 1423, 1531, 1621, 1801, 2017, 2053, 2143, 2161, 2251, 2341,
 2503, 2521, 3061, 3313, 3331, 3511, 4051, 4231]
irb> Prime.each.take_while{|x| x <= 10000}.select{|x| digitSum(x) == 29}
=> [2999, 3989, 4799, 4889, 5879, 5897, 5987, 6599, 6689, 6779, 6869, 6959, 6977,
 7499, 7589, 7877, 7949, 8597, 8669, 8849, 8867, 9479, 9497, 9587, 9677, 9749, 9767,
 9839, 9857, 9929]
irb> Prime.each.each_cons(2).lazy.select{|p, r| r - p == 2}.take(2017).force[-1]
=> [183509, 183511]

●Gauche

Gauche (version 0.9.4) にも素数を扱うライブラリ math.prime と遅延リストを扱う gauche.lazy があるので簡単に答えを求めることができます。

gosh> (use math.prime)
#<undef>
gosh> (use srfi-1)
#<undef>
gosh> (use gauche.lazy)
#<undef>
gosh> (length (take-while (lambda (x) (<= x 2017)) (primes)))
306
gosh> (list-ref (primes) (- 2017 1))
17539
gosh> (define (digit-sum n) (let loop ((n n) (a 0)) (if (zero? n) a (loop (quotient n 10) (+ a (mod n 10))))))
digit-sum
gosh> (filter (lambda (x) (= (digit-sum x) 10)) (take-while (lambda (x) (<= x 5000)) (primes)))
(19 37 73 109 127 163 181 271 307 433 523 541 613 631 811 1009 1063 1117 1153 1171 
1423 1531 1621 1801 2017 2053 2143 2161 2251 2341 2503 2521 3061 3313 3331 3511 4051 
4231)
gosh> (filter (lambda (x) (= (digit-sum x) 29)) (take-while (lambda (x) (<= x 10000)) (primes)))
(2999 3989 4799 4889 5879 5897 5987 6599 6689 6779 6869 6959 6977 7499 7589 7877 7949 
8597 8669 8849 8867 9479 9497 9587 9677 9749 9767 9839 9857 9929)
gosh> (define pair-primes (lmap (lambda (a b) (cons a b)) (primes) (drop (primes) 1)))
pair-primes
gosh> (list-ref (lfilter (lambda (x) (= (- (cdr x) (car x)) 2)) pair-primes) (- 2017 1))
(183509 . 183511)

●Haskell

拙作のページ お気楽 Haskell プログラミング入門遅延評価 で作成した「素数列の生成」を使って解を求めました。

リスト : 素数列の生成 (primes.hs)

checkPrime :: Integer -> Bool
checkPrime n =
  all (\x -> mod n x /= 0) (takeWhile (\x -> x * x <= n) primes)

primesFrom :: Integer -> [Integer]
primesFrom n
  | checkPrime n = n : primesFrom (n + 2)
  | otherwise    = primesFrom (n + 2)

primes = 2 : 3 : 5 : primesFrom 7

splitDigit :: Integer -> [Integer]
splitDigit 0 = []
splitDigit n = n `mod` 10 : splitDigit(n `div` 10)

digitSum :: Integer -> Integer
digitSum n = sum (splitDigit n)
Prelude> :l primes.hs
[1 of 1] Compiling Main             ( primes.hs, interpreted )
Ok, modules loaded: Main.
*Main> length (takeWhile (\x -> x <= 2017) primes)
306
*Main> primes !! (2017 - 1)
17539
*Main> filter (\x -> digitSum x == 10) (takeWhile (\x -> x <= 5000) primes)
[19,37,73,109,127,163,181,271,307,433,523,541,613,631,811,1009,1063,1117,1153,
1171,1423,1531,1621,1801,2017,2053,2143,2161,2251,2341,2503,2521,3061,3313,3331,
3511,4051,4231]
*Main> filter (\x -> digitSum x == 29) (takeWhile (\x -> x <= 10000) primes)
[2999,3989,4799,4889,5879,5897,5987,6599,6689,6779,6869,6959,6977,7499,7589,7877,
7949,8597,8669,8849,8867,9479,9497,9587,9677,9749,9767,9839,9857,9929]
*Main> (filter (\(a, b) -> b - a == 2) (zip primes (tail primes))) !! (2017 - 1)
(183509,183511)

なお、Haskell には素数を扱うライブラリ Data.Numbers.Primes があるので、それをインストールすると高速に処理することができます。ライブラリは次のコマンドで簡単にインストールすることができます。

cabal install primes
Prelude> import Data.Numbers.Primes
Prelude Data.Numbers.Primes> let {splitDigit 0 = []; splitDigit n = n `mod` 10 : splitDigit(n `div` 10)}
Prelude Data.Numbers.Primes> let digitSum n = sum (splitDigit n)
Prelude Data.Numbers.Primes> length (takeWhile (\x -> x <= 2017) primes)
306
Prelude Data.Numbers.Primes> primes !! (2017 - 1)
17539
Prelude Data.Numbers.Primes> filter (\x -> digitSum x == 10) (takeWhile (\x -> x <= 5000) primes)
[19,37,73,109,127,163,181,271,307,433,523,541,613,631,811,1009,1063,1117,1153,
1171,1423,1531,1621,1801,2017,2053,2143,2161,2251,2341,2503,2521,3061,3313,3331,
3511,4051,4231]
Prelude Data.Numbers.Primes> filter (\x -> digitSum x == 29) (takeWhile (\x -> x <= 10000) primes)
[2999,3989,4799,4889,5879,5897,5987,6599,6689,6779,6869,6959,6977,7499,7589,7877,
7949,8597,8669,8849,8867,9479,9497,9587,9677,9749,9767,9839,9857,9929]
Prelude Data.Numbers.Primes> (filter (\(a, b) -> b - a == 2) (zip primes (tail primes))) !! (2017 - 1)
(183509,183511)

●Java

拙作のページ 続・お気楽 Java プログラミング入門 で作成した immutable な遅延ストリーム を使ったプログラムです。

リスト : 「素数で遊ぼう」の解答

import immutable.*;
import static immutable.LazyStream.*;

public class primeproblem {
  // 素数列
  static LazyStream<Integer> primes =
    cons(2, () -> cons(3, () -> cons(5, () -> primesFrom(7))));

  static int nextPrime(int n) {
    while (true) {
      LazyStream<Integer> ps = primes;
      while (true) {
        int p = ps.first();
        if (p * p > n) return n;
        if (n % p == 0) break;
        ps = ps.rest();
      }
      n += 2;
    }
  }

  static LazyStream<Integer> primesFrom(int n) {
    int p = nextPrime(n);
    return cons(p, () -> primesFrom(p + 2));
  }

  static int digitSum(int n) {
    int a = 0;
    while (n > 0) {
      a += n % 10;
      n /= 10;
    }
    return a;
  }
  
  public static void main(String[] args) {
    System.out.println("----- Q01 -----");
    System.out.println(primes.takeWhile(x -> x <= 2017).size());
    System.out.println("----- Q02 -----");
    System.out.println(primes.get(2017 - 1));
    System.out.println("----- Q03 -----");
    System.out.println(primes.filter(x -> digitSum(x) == 10).takeWhile(x -> x < 5000));
    System.out.println("----- Q04 -----");
    System.out.println(primes.filter(x -> digitSum(x) == 29).takeWhile(x -> x < 10000));
    System.out.println("----- Q05 -----");
    LazyStream<Pair<Integer, Integer>> twin =
      LazyStream.zipWith((x, y) -> Pair.pair(x, y), primes, primes.rest()).filter(p -> p.getSnd() - p.getFst() == 2);
    System.out.println(twin.get(2017 - 1));
  }
}
C>java primeproblem
----- Q01 -----
306
----- Q02 -----
17539
----- Q03 -----
[19, 37, 73, 109, 127, 163, 181, 271, 307, 433, 523, 541, 613, 631, 811, 1009, 
1063, 1117, 1153, 1171, 1423, 1531, 1621, 1801, 2017, 2053, 2143, 2161, 2251, 
2341, 2503, 2521, 3061, 3313, 3331, 3511, 4051, 4231]
----- Q04 -----
[2999, 3989, 4799, 4889, 5879, 5897, 5987, 6599, 6689, 6779, 6869, 6959, 6977, 
7499, 7589, 7877, 7949, 8597, 8669, 8849, 8867, 9479, 9497, 9587, 9677, 9749, 
9767, 9839, 9857, 9929]
----- Q05 -----
(183509, 183511)

Copyright (C) 2017 Makoto Hiroi
All rights reserved.

[ Home ]