スキップしてメイン コンテンツに移動

Project Euler - Problem 27

問題

しばらく止まってましたが今日から再開。

  • 原文

    Considering quadratics of the form:

    n2 + an + b, where |a| < 1000 and |b| < 1000

    Find the product of the coefficients, a and b, for the quadratic expression that produces the maximum number of primes for consecutive values of n, starting with n = 0.

  • 日本語訳

    |a| < 1000, |b| < 1000 として以下の二次式を考える (ここで|a|は絶対値):

    n2 + an + b

    n=0から始めて連続する整数で素数を生成したときに最長の長さとなる上の二次式の, 係数a, bの積を答えよ.

解答

最大探索範囲は-999 <= a <= 999、-999 <= b <= 999なので、およそ4,000,000通りの係数の組合せを試すことになります。組合せ毎に数列を生成して、それが素数か判定するわけですからたまりません。簡単な検討を加えて範囲を絞りましょう。

与えられた二次式をf(n)とおくと、f(0) = b、f(1) = a + b + 1です。 f(n)が長さ2以上の素数列を生成するならこれらは素数ですから、次のことがいえます:

  1. bは素数である
  2. a + b + 1は素数である
  3. b = 2のとき、aは偶数である
  4. それ以外のとき、aは奇数である

素数判定関数is_primeには同じ引数が与えられることがよくあるのでメモ化しています。

#!/usr/bin/perl

use strict;
use warnings;
use feature qw/say/;

sub prime_seq_len($$) {
  my ($coeff_a, $coeff_b) = @_;
  my $len = 0;
  my $n = 0;
  $len++, $n++ while is_prime($n * ($n + $coeff_a) + $coeff_b);
  return $len;
}

{
  my %primes = ( 2 => 1 );
  sub is_prime(_) {
    my $n = abs shift;

    unless (exists $primes{$n}) {
      return 0 if $n < 2 or $n % 2 == 0;

      my $is_prime = 1;
      for (my $i = 3; $i <= sqrt $n; $i += 2) {
        if ($n % $i == 0) {
          $is_prime = 0;
          last;
        }
      }
      $primes{$n} = $is_prime;
    }

    return $primes{$n};
  }
}

my $longest = 0;
my $product;
for my $coeff_b (grep { is_prime } -999 .. 999) {
  my $modulo = $coeff_b == 2 ? 0 : 1;
  my @a_cands = grep { $_ % 2 == $modulo
                         and is_prime($_ + $coeff_b + 1) } -999 .. 999;
  for my $coeff_a (@a_cands) {
    my $len = prime_seq_len($coeff_a, $coeff_b);
    if ($longest < $len) {
      $longest = $len;
      $product = $coeff_a * $coeff_b;
    }
  }
}

say $product;

追記

コメントで匿名氏に御指摘いただきました。

b = n = 2とするとf(2) = 22 + 2a + 2となり、これは明らかに(2より大きい)偶数です。 つまりb = 2のとき、生成する素数列の長さは高々2であり、無視できることになります。

前掲のコードでb = 2のケースを考慮している部分($moduloのあたり)は不要になりました:

my $longest = 0;
my $product;
for my $coeff_b (grep { is_prime } -999 .. 999) {
  my @a_cands = grep { $_ % 2 != 0
                         and is_prime($_ + $coeff_b + 1) } -999 .. 999;
  for my $coeff_a (@a_cands) {
    my $len = prime_seq_len($coeff_a, $coeff_b);
    if ($longest < $len) {
      $longest = $len;
      $product = $coeff_a * $coeff_b;
    }
  }
}

say $product;

コメント

  1. b = 2 の場合、n が偶数の時には必ず f(n) は偶数になってしまうので、f(n) が素数になるのは n が 2 未満の場合に限られます。
    最初から b = 2 の場合は考えなくてよいのでは?

    返信削除
  2. コメント承認が遅くなってすいませんでした。

    b=n=2の時偶数になるのはその通りです。
    完全に見落としていました。御指摘ありがとうございます。

    返信削除

コメントを投稿

このブログの人気の投稿

開発環境の構築に asdf が便利なので anyenv から移行した

プロジェクト毎に異なるバージョンの言語処理系やツールを管理するために、pyenv や nodenv など *env の利用はほとんど必須となっている。 これらはほとんど一貫したコマンド体系を提供しており、同じ要領で様々な環境構築ができる非常に便利なソフトウェアだが、それを使うことで別の問題が出てくる: *env 自身の管理である。 無数の *env をインストールし、シェルを設定し、場合によりプラグインを導入し、アップデートに追従するのは非常に面倒な作業だ。 幸いなことにこれをワンストップで解決してくれるソリューションとして anyenv がある。これは各種 *env のパッケージマネージャというべきもので、一度 anyenv をインストールすれば複数の *env を簡単にインストールして利用できる。さらに anyenv-update プラグインを導入すればアップデートまでコマンド一発で完了する。素晴らしい。 そういうわけでもう長いこと anyenv を使ってきた。それで十分だった。 ——のだが、 ここにもう一つ、対抗馬となるツールがある。 asdf である。anyenv に対する asdf の優位性は大きく2つある: 一貫性と多様性だ。 一貫性 “Manage multiple runtime versions with a single CLI tool” という触れ込み通り、asdf は様々な言語やツールの管理について一貫したインタフェースを提供している。対して anyenv は *env をインストールするのみで、各 *env はそれぞれ個別のインタフェースを持っている。 基本的なコマンド体系は元祖である rbenv から大きく外れないにしても、例えば jenv のように単体で処理系を導入する機能を持たないものもある。それらの差異はユーザが把握し対応する必要がある。 多様性 asdf はプラグインシステムを持っている。というより asdf 本体はインタフェースを規定するだけで、環境構築の実務はすべてプラグイン任せである。 そのプラグインの数は本稿を書いている時点でおよそ 300 を数える。これは言語処理系ばかりでなく jq などのユーティリティや MySQL のようなミドルウェアも含むが、いずれにしても膨大なツールが asdf を使えば

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 (大文字なことに注意) ブロックが自分の宣言されたスコープ内で投げられた例外を捕らえる

macOS で GUI 版 Emacs を使う設定

macOS であっても端末エミュレータ上で CLI 版 Emacs を使っているプログラマは多いと思うが、端末側に修飾キーを取られたり東アジア文字の文字幅判定が狂ってウィンドウ描画が崩れたりなどしてあまり良いことがない。 それなら GUI 版の Emacs.app を使った方がマウスも使える上に treemacs などはアイコンも表示されてリッチな UI になる。 しかし何事も完璧とはいかないもので、CLI だと問題なかったものが GUI だと面倒になることがある。その最大の原因はシェルの子プロセスではないという点である。つまり macOS の GUI アプリケーションは launchd が起動しその環境変数やワーキングディレクトリを引き継ぐので、ファイルを開こうとしたらホームディレクトリ ( ~/ ) でなくルートディレクトリ ( / ) を見に行くし、ホームディレクトリなり /opt/local なりに好き勝手にインストールしたツールを run-* 関数やら shell やら flycheck やらで実行しようとしてもパスが通っていない。 ワーキングディレクトリに関しては簡単な解決策があり、 default-directory という変数をホームディレクトリに設定すれば良い。ただし起動時にスプラッシュスクリーンを表示する設定の場合、このバッファのワーキングディレクトリは command-line-default-directory で設定されており、デフォルト値が解決される前に適用されてしまうので併せて明示的に初期化する必要がある: (setq default-directory "~/") (setq command-line-default-directory "~/") 次にパスの問題だが、まさにこの問題を解決するために exec-path-from-shell というパッケージがある。これを使うとユーザのシェル設定を推定し、ログインシェルとして起動した場合の環境変数 PATH と MANPATH を取得して Emacs 上で同じ値を setenv する、という処理をやってくれる。MELPA にあるので package-install するだけで使えるようになる。 このパッケージは GUI

BuckleScript が ReScript に改称し独自言語を導入した

Via: BuckleScript Good and Bad News - Psellos OCaml / ReasonML 文法と標準ライブラリを採用した JavaScript トランスパイラである BuckleScript が ReScript に改称した。 公式サイトによると改称の理由は、 Unifying the tools in one coherent platform and core team allows us to build features that wouldn’t be possible in the original BuckleScript + Reason setup. (単一のプラットフォームとコアチームにツールを統合することで従来の BuckleScript + Reason 体制では不可能であった機能開発が可能になる) とのこと。要は Facebook が主導する外部プロジェクトである ReasonML に依存せずに開発を進めていくためにフォークするという話で、Chromium のレンダリングエンジンが Apple の WebKit から Google 主導の Blink に切り替わったのと似た動機である (プログラミング言語の分野でも Object Pascal が Pascal を逸脱して Delphi Language になったとか PLT Scheme (の第一言語) が RnRS とは別路線に舵を切って Racket になったとか、割とよくある話である。) 公式ブログの Q&A によると OCaml / ReasonML 文法のサポートは継続され、既存の BuckleScript プロジェクトは問題なくビルドできるとのこと。ただし現時点で公式ドキュメントは ReScript 文法のみに言及しているなど、サポート水準のティアを分けて ReScript 文法を優遇することで移行を推進していく方針である。 上流である OCaml の更新は取り込み、AST の互換性も維持される。将来 ReScript から言語機能が削除されることは有り得るが、OCaml / ReasonML からは今日の BuckleScript が提供する機能すべてにアクセスできる。 現時点における ReScript の

部分継続チュートリアル

この文書について これは Community Scheme Wiki で公開されている composable-continuations-tutorial (2010年09月30日版)の日本語訳です。 誤字脱字・誤訳などがありましたらコメントあるいはメールで御指摘いただけると幸いです。 本訳は原文のライセンスに基づき Creative Commons Attribution-ShareAlike 2.0 Generic の下で公開されます。 Original text: Copyright© 2006-2010 Community Scheme Wiki Japanese translation: Copyright© 2011 SATOH Koichi 本文 部分継続(Composable continuation)は継続区間を具象化することで制御を逆転させるものです。 ウンザリするほど複雑な概念を表す長ったらしいジャーゴンのように聞こえますが、実際はそうではありません。今からそれを説明します。 reset と shift という2つのスペシャルフォームを導入するところから始めましょう [1] 。 (reset expression) は特別な継続を作るなりスタックに目印を付けるなりしてから expression を評価します。簡単に言えば、 expression が評価されるとき、あとから参照できる評価中の情報が存在するということです。 実際には shift がこの情報を参照します。 (shift variable expression) は目印のついた場所、つまり reset を使った場所にジャンプし、その場所から shift を呼び出した場所までのプログラムの断片を保存します; これはプログラムの区間を「部分継続」として知られる組み合わせ可能な手続きに具象化し、この手続きに variable を束縛してから expression を評価します。 組み合わせ可能(Composable)という語はその手続きが呼び出し元に戻ってくるため、他の手続きと組み合わせられることから来ています。 Composable continuationの別名として例えば限定継続(Delimited continuation)や部分継続(Partia