Project Euler - Problem 12

問題

原文

What is the value of the first triangle number to have over five hundred divisors?
日本語訳

501 個以上の約数をもつ最初の三角数はいくらか。

解答

約数の個数は素因数分解の結果から求めることができます。例えばn = p^a * q^b（pとqは素数）という合成数がある場合、約数は以下の表のようになります：

1	p	p²	...	p^a
q	p * q	p² * q		p^a * q
q²	p * q²	p² * q²		p^a * q²
...
q^b	p * q^b	p² * q^b		p^a * q^b

p⁰ = q⁰ = 1であることを考えれば、0..aの(a + 1)通りのpのべき乗と、0..bの(b + 1)通りのqのべき乗を掛け合わせた数がnの約数であることが分かります。これは素因数が3つ以上の場合も同様で、一般にp^a * q^b * r^c * ...の約数は(a + 1)(b + 1)(c + 1)...個存在します。

Problem 3で使った素因数分解を行う関数factorizeを改良し、各素因数について、べき乗回数をcdrに入れたペアのリストを返すようにしました。

(define (triangle-number n) (* (+ 1 n) (/ n 2)))
(define (factorize n)
  (define max-divisor (floor->exact (sqrt n)))
  (define (factorize-1 n div result)
    (if (> div max-divisor)
        (if (= n 1) result (cons (cons n 1) result))
        (let count ((n n) (i 0))
          (define (divisor? m) (zero? (modulo n m)))
          (if (divisor? div) (count (/ n div) (+ i 1))
              (factorize-1 n (+ div 2)
                           (if (zero? i) result
                               (cons (cons div i) result)))))))
  (let prepare ((n n) (i 0))
    (if (even? n) (prepare (/ n 2) (+ i 1))
        (factorize-1 n 3 (if (zero? i) '() (cons (cons 2 i) '()))))))
(define (num-of-divisors-of n)
  (apply * (map (lambda (factor) (+ (cdr factor) 1)) (factorize n))))
(define (solve)
  (let loop ((i 1))
    (define tri (triangle-number i))
    (if (> (num-of-divisors-of tri) 500) tri
        (loop (+ i 1)))))
(define (main argv)
  (display (solve))
  (newline))

参考文献

mathschallenge.net

このブログの人気の投稿

Perl の新 class 構文を使ってみる

Perl 5 のオブジェクト指向機能は基本的には Python の影響を受けたものだが、データを名前空間 (package) に bless する機構だけで Perl 4 以来の名前空間とサブルーチンをそのままクラスとメソッドに転換し第一級のオブジェクト指向システムとした言語設計は驚嘆に価する。実際この言語のオブジェクトシステムは動的型付言語のオブジェクト指向プログラミングに要求されるおよそあらゆる機能を暗にサポートしており、CPAN には Moose を筆頭とした屋下屋オブジェクトシステムが複数存在しているがその多くは Pure Perl ライブラリである。つまり「やろうと思えば全部手書きで実現できる」わけである。そういうわけで Perl のオブジェクト指向プログラミングサポートは機能面では (静的型検査の不在という現代的には極めて重大な欠如を除けば) 申し分ないのだが、しかし Moose その他の存在が示しているように一つ明らかな欠点がある。記述の冗長さだ。コンストラクタを含むあらゆるメソッドは第一引数としてレシーバを受ける単なるサブルーチンとして明示的に書く必要があるし、オブジェクトのインスタンス変数 (a.k.a. プロパティ / データメンバ) は bless されたデータに直接的ないし間接的にプログラマ定義の方法で格納されるためアクセス手段は実装依存である。これはカプセル化の観点からは望ましい性質だが、他者の書いたクラスを継承するときに問題となる。ある日データ表現を変更した親クラスがリリースされると突然自分の書いた子クラスが実行時エラーを起こすようになるわけだ。そうならないためにはインスタンス変数へのアクセスに (protected な) アクセサを使う必要があるのだが、そのためには親クラスが明示的にそれらを提供している必要があるし、そもそも Perl にはメソッドのアクセス修飾子というものがないので完全な制御を与えるならばオブジェクトの内部状態がすべて public になってしまう。そのような事情もあり、特にパフォーマンスが問題にならないようなアプリケーションコードでは Moose のようなリッチな語彙を提供するオブジェクトシステムを使うことが公式のチュートリアルでも推奨されてきた。Perl コアのオブジェクトシステムの改良は...

Perl 7 より先に Perl 5.34 が出るぞという話

Perl 5 の次期バージョンとして一部後方互換でない変更 (主に間接オブジェクト記法の削除とベストプラクティスのデフォルトでの有効化) を含んだメジャーバージョンアップである Perl 7 がアナウンスされたのは昨年の 6 月のことだったが、その前に Perl 5 の次期周期リリースである Perl 5.34 が 5 月にリリース予定である。現在開発版は Perl 5.33.8 がリリースされておりユーザから見える変更は凍結、4 月下旬の 5.33.9 で全コードが凍結され 5 月下旬に 5.34.0 としてリリース予定とのこと。そういうわけで事前に新機能の予習をしておく。 8進数数値リテラルの新構文見た瞬間「マジかよ」と口に出た。これまで Perl はプレフィクス 0 がついた数値リテラルを8進数と見做してきたが、プレフィクスに 0o (zero, small o) も使えるようになる。もちろんこれは2進数リテラルの 0b や 16進数リテラルの 0x との一貫性のためである。リテラルと同じ解釈で文字列を数値に変換する組み込み関数 oct も` 新構文を解するようになる。昨今無数の言語に取り入れられているリテラル記法ではあるが、この記法の問題は o (small o) と 0 (zero) の区別が難しいことで、より悪いことに大文字も合法である： 0O755 Try / Catch 構文 Perl 5 のリリース以来 30 年ほど待たれた実験的「新機能」である。 Perl 5 における例外処理が特別な構文でなかったのは予約語を増やさない配慮だったはずだが、TryCatch とか Try::Tiny のようなモジュールが氾濫して当初の意図が無意味になったというのもあるかも知れない。 use feature qw/ try / ; no warnings qw/ experimental::try / ; try { failable_operation(); } catch ( $e ) { recover_from_error( $e ); } Raku (former Perl 6) だと CATCH (大文字なことに注意) ブロックが自分の宣言されたスコープ内で投げられた例外を捕らえる...

Perl 5.42 が出たので perldelta を読んだ

去る2025年7月2日に Perl 5.42 がリリースされた。ので例によって perldelta を一通り眺めた。このバージョンは実験的機能である組込みのクラス構文の実装が進展した。他にもパフォーマンスの改良、組み込み関数・演算子・C レベル API の追加、多数のバグ修正があるが劇的な変化ではなく、発見・修正された脆弱性もかなり限定的な問題なので刺さる機能がなければ急いで移行する必要はあまりないように思われる。以下主だった新機能の抜粋。 source::encoding プラグマソースコードが特定の文字エンコーディングで記述されていることを宣言するプラグマ。サポートされているエンコーディングは ASCII と UTF-8 のみである。 use source::encoding 'ascii' が宣言された字句的スコープにおいて非 ASCII 文字を記述するとコンパイル時エラーが発生するようになる。 use source::encoding 'utf8' は単に use utf8 のシノニムである。 Perl 5 は 2000 年にリリースされたバージョン 5.6 から UTF-8 によるソースコード記述をサポートしているが、後方互換性のため既定では ASCII を前提としており、 utf8 プラグマを使わない限り文字列リテラルや RegExp リテラルはバイト列として解釈されるし、識別子にも英数字および '_' しか使うことができない。識別子はともかく「リテラルは既定でバイト列である」という意味論は極めて誤用しやすい。Unicode 文字列のつもりで渡した値が意図せずバイト列であったために実行時警告・エラーを得た経験は非英語圏のプログラマなら一度ならずあるだろう。このプラグマはそのような初歩的なバグをコンパイル時に検出することで、Perl プログラムの最も頻出するエラーの一つを実質的に解消しようとしている。ちなみに use v5.42 すると自動で use source::encoding 'ascii' も有効になるので、今まさに警告を吐いているようなアプリケーションをアップグレードする際は注意が必要である。 any / all 演算子実験的...

LIBLINEAR 2.41 で One-class SVM が使えるようになったので Perl から触ってみよう

改訂 (Sep 15, 2020): 必要のない手順を含んでいたのでサンプルコードと記述を修正しました。 CPAN に Algorithm::LibLinear 0.22 がリリースされました (しました。) 高速な線形 SVM およびロジスティック回帰による複数の機械学習アルゴリズムを実装したライブラリである LIBLINEAR への Perl バインディングです。利用している LIBLINEAR のバージョンが LIBLINEAR 2.30 から LIBLINEAR 2.41 に上がったことで新しいソルバが追加され、One-class SVM (OC-SVM) による一値分類が利用可能になっています (しました。) OC-SVM って何一値分類を SVM でやること。一値分類って何ある値が学習したクラスに含まれるか否かを決定する問題。 HBO の「シリコンバレー」に出てきた「ホットドッグ」と「ホットドッグ以外」を識別するアプリが典型。「ホットドッグ以外」の方は犬でも神でも一つの指輪でも何でも含まれるのがミソ。二値分類の場合正反両者のデータを集める必要があるのに対して、一値分類の学習器は正例データのみしか要求しない (ものが多い。) 主な用途は外れ値検出で、もちろんホットドッグやホットドッグ様のものを検出したりもできる。使い方手順自体は他の二値ないし多値分類問題と同じです。つまり、訓練パラメータを決めて訓練データセットで訓練してテストデータセットで確度を検証して十分良くなったらモデルを保存するといういつもの流れ。訓練パラメータ use 5.032 ; use Algorithm::LibLinear ; my $learner = Algorithm::LibLinear ->new( epsilon => 0.01 , nu => 0.75 , solver => ' ONECLASS_SVM ' , ); solver => 'ONECLASS_SVM' が一値分類用のソルバです。LIBLINEAR の train コマンドで言うところの -s 21 。 OC-SVM の良いところは (ハイパー)...

Project Euler - Problem 35

問題原文 How many circular primes are there below one million? 日本語訳 100万未満の巡回素数は何個か? 解答回転させた数値がすべて素数ということは、すべての桁が奇数でなければいけません(ただし2を除く)。追記匿名氏にコメントでご指摘頂いたのでコードを一部修正しました。いずれかの桁に5がある場合も、回転させると必ず5の倍数が現れるので除外できます。もっと追記前の修正に間違いが入っているのをご指摘頂いたので修正しました。 5自体は素数なので、巻き添えで除外してはいけません。 #!/usr/bin/env perl use strict; use warnings; use feature qw/say state/; use List::MoreUtils qw/all none/; sub is_prime($) { state %memos; my $n = shift; return 0 if $n < 2; return 1 if $n == 2; return 1 if $n == 3; return $memos{$n} if exists $memos{$n}; $memos{$n} = none { $n % $_ == 0 } 2 .. sqrt $n; } sub rotate($) { my $n = shift; substr($n, 1) . substr($n, 0, 1); } sub rotations($) { my $n = shift; my %seen = ($n => 1); $seen{$n} = 1 until exists $seen{$n = rotate $n}; keys %seen; } sub is_circular_prime($) { state %memos; my $n = shift; return 0 if $n =~ /[024568]/ and $n != 2 and $n != 5; return $memos{$n} if exists $memos{$n}; my ...

僕のIT革命

このブログを検索