僕のIT革命

問題 原文 Let d 1 be the 1 st digit, d 2 be the 2 nd digit, and so on. In this way, we note the following: d 2 d 3 d 4 =406 is divisible by 2 d 3 d 4 d 5 =063 is divisible by 3 d 4 d 5 d 6 =635 is divisible by 5 d 5 d 6 d 7 =357 is divisible by 7 d 6 d 7 d 8 =572 is divisible by 11 d 7 d 8 d 9 =728 is divisible by 13 d 8 d 9 d 10 =289 is divisible by 17 Find the sum of all 0 to 9 pandigital numbers with this property. 日本語訳 d 1 を1桁目, d 2 を2桁目の数とし, 以下順にd n を定義する. この記法を用いると次のことが分かる. d 2 d 3 d 4 =406は2で割り切れる d 3 d 4 d 5 =063は3で割り切れる d 4 d 5 d 6 =635は5で割り切れる d 5 d 6 d 7 =357は7で割り切れる d 6 d 7 d 8 =572は11で割り切れる d 7 d 8 d 9 =728は13で割り切れる d 8 d 9 d 10 =289は17で割り切れる このような性質をもつ0から9のPandigital数の総和を求めよ. 解答 Problem 41 と同様に Pandigital数 を作るだけです。途中で枝切りして無駄な計算を省いています。 除数を保持する配列は一応定数にしてみました。定数の宣言には標準プラグマに constant がありますが、コードが分かり易い Attribute::Constant というCPANモジュールを使っています。 #!/usr/bin/env perl use strict; use wa...

問題 原文 By converting each letter in a word to a number corresponding to its alphabetical position and adding these values we form a word value. For example, the word value for SKY is 19 + 11 + 25 = 55 = t 10 . If the word value is a triangle number then we shall call the word a triangle word. Using words.txt (right click and 'Save Link/Target As...'), a 16K text file containing nearly two-thousand common English words, how many are triangle words? 日本語訳 単語中のアルファベットを数値に変換した後に和をとる. この和を「単語の値」と呼ぶことにする. 例えば SKY は 19 + 11 + 25 = 55 = t 10 である. 単語の値が三角数であるとき, その単語を三角語と呼ぶ. 16Kのテキストファイル word.txt 中に約2000語の英単語が記されている. 三角語はいくつあるか? 解答 42問目! ちょっと拍子抜けするほど簡単です。三角数を片っ端から計算して連想配列に入れておき、文字列の値を計算して照合するだけです。 #!/usr/bin/env perl use strict; use warnings; use feature qw/say/; use List::Util qw/sum/; sub word_value($) { my $offset = ord('A') - 1; sum map { ord($_) - $offset } split //, uc shift; } sub tri_num($) { my $n = shift; $n * ($n + 1) / 2...

問題 原文 What is the largest n-digit pandigital prime that exists? 日本語訳 n桁のPandigitalな素数の中で最大の数を答えよ. 解答 ある数が3の倍数のとき、その各桁を足し合わせた数もまた3の倍数であり、その逆もいえます： n = a m-1 a m-2 ...a 0 = a m-1 ×10 m-1 + a m-2 ×10 m-2 + ... + a 0 ×10 0 = a m-1 ×(1 + 999...9) + a m-2 ×(1 + 99...9) + ... + a 1 ×(1 + 9) + a 0 ×1 = (a m-1 + a m-2 + ... + a 0 ) + a m-1 ×(999...9) + a m-2 ×(99...9) + ... + a 1 ×9 ∴ nが3の倍数のとき、a m-1 + a m-2 + ... + a 0 は3の倍数 つまり1 + 2 + ... + mが3の倍数であったとすると、m桁のPandigital数の中に解は存在し得ないことが分かります。m = 8, 9のときがこの場合に該当するので、探索範囲を大きく減らせます。 Pandigital数 を作る際に数値を重複なく選ぶため、 Set::Object というCPANモジュールを使って簡単な集合演算を行っています。 #!/usr/bin/env perl; use strict; use warnings; use feature qw/say state/; use List::Util qw/sum/; use List::MoreUtils qw/none/; use Set::Object qw/set/; 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 .. ...

問題 原文 An irrational decimal fraction is created by concatenating the positive integers: 0.123456789101112131415161718192021... It can be seen that the 12 th digit of the fractional part is 1. If d n represents the n th digit of the fractional part, find the value of the following expression. d 1 × d 10 × d 100 × d 1000 × d 10000 × d 100000 × d 1000000 日本語訳 正の整数を順に連結して得られる以下の10進の無理数を考える: 0.123456789101112131415161718192021... 小数点第12位は1である. d n で小数点第n位の数を表す. d 1 × d 10 × d 100 × d 1000 × d 10000 × d 100000 × d 1000000 を求めよ. 解答 数列作って、繋げて、取り出して、掛け合わせる。おしまい。 #!/usr/bin/env perl use strict; use warnings; use feature qw/say/; use List::Util qw/reduce/; my $n = 0; my $str = ''; $str .= $n++ while length $str <= 1_000_000; our ($a, $b); say reduce { $a * $b } map { substr $str, 10 ** $_, 1 } 0 .. 6;

問題 原文 If p is the perimeter of a right angle triangle with integral length sides, {a,b,c}, there are exactly three solutions for p = 120. {20,48,52}, {24,45,51}, {30,40,50} For which value of p ≤ 1000, is the number of solutions maximised? 日本語訳 辺の長さが{a,b,c}と整数の3つ組である直角三角形を考え, その周囲の長さをpとする. p = 120のときには3つの解が存在する: {20,48,52}, {24,45,51}, {30,40,50} p < 1000 で解の数が最大になる p を求めよ. 解答 問題の前提からp = a + b + cです。 三平方の定理よりa 2 + b 2 = c 2 で、p = a + b + c ⇒ c = p - (a + b)なので、cを消去して： a 2 + b 2 = (p - (a + b)) 2 = p 2 - 2p(a + b) + a 2 + 2ab + b 2 よってp 2 - 2p(a + b) + 2ab = 0であり、a、bが解のときpは偶数であることが分かります。 またこれをbについて解くとb = (2ap - p 2 ) / 2(a - p)なので、aの値を定めればbの値は一意に決まることが分かります。 結局各pについてa > bとなるまでaを一通り試すだけで良いことになります。 実のところ答えの3つ組を計算する必要はなかったりしますが、答えを出力した上でその数を数える形にしています。 #!/usr/bin/perl use strict; use warnings; use feature qw/say/; use List::Util qw/reduce/; sub solutions($) { my $p = shift; return () unless $p % 2 == 0; my @solut...

問題 原文 What is the largest 1 to 9 pandigital 9-digit number that can be formed as the concatenated product of an integer with (1,2, ... , n) where n > 1? 日本語訳 整数と(1,2,...,n) (n > 1) との連結積として得られる9桁のPandigital数の中で最大のものを答えよ. 解答 乗数が1, 2, ..., n (n > 1)で桁数は9なので、被乗数mは1から9999の範囲です。 範囲が分かれば後は簡単で、m×1から順に積を連結していって、丁度9桁となったときにPandigital数であればいいわけです。 Pandigital数 を定義通り考えれば「1から9のすべての数字が1回以上現れる数」ですが、この問題では桁数の制約からいずれの数字も1回ずつしか現れないため、「同じ数字が重複して出現せず、0が現れない数」に読み替えることができます。Perlだとこちらの方が正規表現マッチングが高速でした。 #!/usr/bin/env perl use strict; use warnings; use feature qw/say/; use List::Util qw/max/; say max map { my $cat = ''; for (my $mul = 1; length $cat < 9; $cat .= $_ * $mul++) {} (length $cat == 9 and $cat !~ /0/ and $cat !~ /(\d).*\1/) ? $cat : () } 1 .. 9999;

問題 原文 Find the sum of the only eleven primes that are both truncatable from left to right and right to left. 日本語訳 右から切り詰めても左から切り詰めても素数になるような素数は11個しかない. 総和を求めよ. 解答 考え方は Problem 35 と同じで、切り詰めていくと途中で合成数になることが分かっている数を最初に除外しています。 0、4、6、8のいずれかの数字を含む場合は明らかに途中で偶数になりますが、2と5は少し特別で、数の一番上の桁にのみ現れた場合は除外できません。何故なら： 左から切り詰めたときは最初に取り除かれるので関係がない。 右から切り詰めていって最後の1桁になったとき、2と5は素数である。 からです。具体的には23と53がこのケースに該当するので、間違って除外すると処理が終わりません。 #!/usr/bin/env perl use strict; use warnings; use feature qw/say state/; use List::Util qw/sum/; 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 is_truncatable_prime($) { my $n = shift; return 0 if length $n == 1; return 0 if $n =~ /[0468]/; return 0 if $n =~ /.[25]/; return 0 unless is_prime $n; all { is_prime substr($n, $_) and...

問題 原文 Find the sum of all numbers, less than one million, which are palindromic in base 10 and base 2. 日本語訳 100万未満で10進でも2進でも回文数になるような数の総和を求めよ. 解答 nで割り切れる数はn進法で表すと下の桁が0になります(e.g. 100 10 、32=20 16 、8=1000 2 )。 このような数は反転させると(先頭の0は無視するので)桁数が変わってしまうため、回文数になりません。よってこのような数は最初に除外できます。 この問題の場合、2か10で割り切れる数は解にならないことが分かります。10で割り切れるときは当然2でも割り切れるので、実際には2で割り切れるか調べれば十分です。 #!/usr/bin/env perl use strict; use warnings; use feature qw/say/; use List::Util qw/sum/; sub is_palindromic($) { my $n = shift; $n eq reverse $n; } say sum grep { is_palindromic $_ and is_palindromic sprintf '%b', $_; } grep { $_ % 2 != 0 } 1 .. 1_000_000; 追記 値の範囲ですが、1,000,000まで探索する必要はありませんでした。 1から999まで探索して、それを反転させた数値と連結すれば偶数桁の回文数、その間に1つ数字を入れれば奇数桁の回文数が得られるので、探索範囲を絞った上に10進数の回文数判定も省けます。 少し長いですが、70倍ほど高速化できました。 use Scalar::Util qw/looks_like_number/; say sum grep { $_ <= 1_000_000 and is_palindromic sprintf '%b', $_; } map { my $half = $_; map { $half . $_ . reverse...

問題 原文 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 ...

問題 原文 Find the sum of all numbers which are equal to the sum of the factorial of their digits. 日本語訳 各桁の数の階乗の和が自分自身と一致するような数の総和を求めよ. 解答 Problem 30 とほぼ同じ問題なので、その時の解答を基にして考えます。 前回の問題と違うのは、0! = 1なので0を含む数字を含まない数字と同一視できない点です。 そこで正規化の際に0を省くのをやめて、例えば251と2501はそれぞれ125と0125として別に扱うことにします。 また0! = 1!なので、例えば110と100のように各桁の階乗の和が同じになる数が存在し、これを重複して数えないようにしなければなりません。 既に数えた値を連想配列で覚えておいてもいいのですが、 List::MoreUtils の uniq 関数で重複要素を前もって削除する方が高速でした。 #!/usr/bin/env perl; use strict; use warnings; use feature qw/say/; use List::Util qw/sum reduce/; use List::MoreUtils qw/uniq/; sub factorial($) { our ($a, $b); my $n = shift; return 1 if $n == 0; return reduce { $a * $b } 1 .. $n; } my @facts = map { factorial $_ } 0 .. 9; my $max_digits; for ($max_digits = 1; 10 ** $max_digits <= $max_digits * $facts[9]; $max_digits++) {} my @sum_dicts = ({}, { map { ($_ => $facts[$_]) } 0 .. 9 }); until ($#sum_dicts == $max_digits) { push @sum_dicts, { map { my $prev_key ...

問題 原文 The fraction 49/98 is a curious fraction, as an inexperienced mathematician in attempting to simplify it may incorrectly believe that 49/98 = 4/8, which is correct, is obtained by cancelling the 9s. We shall consider fractions like, 30/50 = 3/5, to be trivial examples. There are exactly four non-trivial examples of this type of fraction, less than one in value, and containing two digits in the numerator and denominator. If the product of these four fractions is given in its lowest common terms, find the value of the denominator. 日本語訳 49/98は面白い分数である. 「分子・分母の9をキャンセルしたので 49/98 = 4/8 が得られた」と経験を積んでいない数学者が誤って思い込んでしまうかもしれないからである. 我々は 30/50 = 3/5 のようなタイプは自明な例だとする. 1より小さく分子・分母がともに2桁の数になるような自明でない分数は 4個ある. その4個の分数の積が約分された形で与えられたとき, 分母の値を答えよ. 解答 どうも「自明でない分数」の基準がよく分かりませんが、「分子・分母に共通する数字を取り除いたとき、元の分数と同じ値になるような分数(ただし分子・分母が10の倍数である場合を除く)」みたいです。 分数を (numerator, denominator) というリストの形で扱うことにして、「共通する数字を取り除いた1桁/1桁の分数で、通分した結果が元の分数のそれと等しい」という長ったら...

問題 原文 Find the sum of all products whose multiplicand/multiplier/product identity can be written as a 1 through 9 pandigital. 日本語訳 掛けられる数/掛ける数/積に1から9の数が1回ずつ出現するような積の総和を求めよ. 解答 n桁×m桁の数の積はn+m-1桁かn+m桁になる(e.g. 10×10=100, 99×99=9,801)ので、桁数の合計が9になるとき、積の桁数は4桁であることが分かります。つまり、調べる積の範囲は1,000から9,999までとなります。 あとは数字が重複していないかどうかの判定ですが、積・乗数・被乗数を並べて数字列を作り、小さい順に並べ替えて123456789になれば重複していないことになります。 例えば4396=28×157の場合、並べて書くと439628157という数字列ができます。これを並べ替えると123456789になりますから、4396は答えの1つであることが分かります。 乗数の取り得る範囲は1から積の平方根の間ですが、1の時は積と被乗数が同じになるので明らかに答えではありません。従って2から開始すると少しだけ早くなります。 #!/usr/bin/env perl use strict; use warnings; use feature qw/say/; use List::Util qw/sum/; use List::MoreUtils qw/any/; say sum grep { my $n = $_; any { join('', sort split //, $n . $_ . $n / $_) eq '123456789'; } grep { $n % $_ == 0 } 2 .. sqrt $n; } 1000 .. 9999;

問題 原文 How many different ways can £2 be made using any number of coins? 日本語訳 いくらかの硬貨を使って2ポンドを作る方法はいくつあるでしょうか? 解答 ポンドとペンスを別々に扱うのは面倒と無駄以外の何者でもないので、単位をペンスに統一します。よって問題は合計が200ペンスとなるコインの組み合わせは何通りあるかです。 コインを昇順にC i (i = 0, 1, 2, ..., 7)と番号づけることにします。 合計nペンスとなるC k 以下のコインを使った組み合わせをcc(n, k)と表すと、次のようになります： cc(0, k) = 1 cc(n, 1) = 1 cc(n, k) = Σ(cc(n - iC k , k - 1))、ただしi ∈ { 0 , 1, 2, ..., floor(n / C k ) } 副問題は同じものが何度も出てくるのでメモ化しています。 #!/usr/bin/env perl use strict; use warnings; use feature qw/say state/; use List::Util qw/sum/; sub coin_comb($;$); { my @coins = (1, 2, 5, 10, 20, 50, 100, 200); sub coin_comb($;$) { state %memos; my ($currency, $coin_idx) = @_; $coin_idx //= $#coins; return $memos{$currency, $coin_idx} if exists $memos{$currency, $coin_idx}; return 1 if $currency == 0; return 1 if $coin_idx == 0; use integer; $memos{$currency, $coin_idx} = sum map { coin_comb($currency - $coins[$coin_idx] * $_, $coin_idx...

問題 原文 Find the sum of all the numbers that can be written as the sum of fifth powers of their digits. 日本語訳 各桁を5乗した和が元の数と一致するような数の総和を求めよ. 解答 まず探索範囲の上限を定める必要があります。n桁の最大の整数a n = 9 n-1 9 n-2 ...9 0 を考えると、その各桁の5乗の和はb n = 9 5 nと表せます。 a n+1 = 10a n + 9 b n+1 = b n + 9 5 ですから、桁数nが大きくなるにつれてaがbよりも急激に大きくなるのが分かります。ある桁数n max を超えると、常にa n max > b n max が成立するので、両者が等しくなることはなくなります。 実際に調べるとn max は6なので、探索範囲は高々0から999,999までとなります。 各桁の乗数の和は、桁の並びに関わらず各桁の数のみによって決まります。例えば2501、5012、(0)215のいずれも同じb n を持つので、これを別々に計算するのは時間の無駄です。 そこで、このような数をすべて同値と見なす正規化を考えます。手っ取り早く桁の並べ替えで良いでしょう。各桁を昇順に並べ替え、その上で先頭に1個以上0があったら取り除くという処理です。先ほどの例に挙げた数字をこの方法で正規化すると、いずれも125となります。 この正規化された数のみを走査すれば良いわけですから、（0を含まない）n桁の数1つにつき同じ値をn!通り計算していたところが、1通りで済むことになります。 処理の手順をまとめると次のようになります： 全ての正規化された数に対してb n を計算し、連想配列に格納しておく。 連想配列に格納された値を1つ取り出し、a n とする。 a n を正規化して連想配列から対応するb n を引く。 a n = b n であれば解に加える。 連想配列の値を全て走査するまで2.に戻って繰り返す。 下記のコードでは初期化の都合上、桁数ごとに連想配列を分けていますがアルゴリズム自体に違いはありません。 #!/usr/bin/env perl ...

こんばんはSekia the Liarです。更新頻度についての釈明はさておきえーとP.E. 29でしたね。はい、すいません。 問題 原文 Consider all integer combinations of a^(b) for 2 ≤ a ≤ 5 and 2 ≤ b ≤ 5: （引用者による省略） How many distinct terms are in the sequence generated by a b for 2 ≤ a ≤ 100 and 2 ≤ b ≤ 100? 日本語訳 2 ≤ a ≤ 5 と 2 ≤ b ≤ 5について, abを全て考えてみよう: （引用者による省略） 2 ≤ a ≤ 100, 2 ≤ b ≤ 100 で同じことをしたときいくつの異なる項が存在するか? 解答 値の重複を取り除くにはハッシュを使うのが定石です。 use strict; use warnings; use feature qw/say/; use Math::BigInt; my %pows; for my $n (2 .. 100) { for my $i (2 .. 100) { $pows{ Math::BigInt->new($n) ** $i } = 1; } } say scalar keys %pows; しかしPerlのメソッド解決オーバヘッドは結構でかいので、10,000個のMath::BigIntインスタンス生成は割と時間を食います。毎回Math::BigIntというのも芸がないし、少し頭を使って解いてみることにしました。 a b = (a n ) b/n であることに着目しましょう。これは中学だか高校だかで習った通りです。ただし問題の範囲は整数なので、指数は2 ≤ b/n ≤ 100なる整数でなければなりません。つまりnはbの約数（ただしb自身を除く）です。 この等号で結ばれたべき乗は同じ（つまり重複した）値を持ちます。 例えば2 12 = 4(=2 2 ) 6 = 8(=2 3 ) 4 = 16(=2 4 ) 3 = 64(=2 6 ) 2 = 4,096であり、他に4,096となるようなべき乗は整数の範囲ではなさそう...

問題 再開言っておきながら10日も開いてしまいました。今度こそ再開します。きっと。 原文 What is the sum of both diagonals in a 1001 by 1001 spiral formed in the same way? 日本語訳 1001・1001の螺旋を同じ方法で生成したとき, 対角線上の数字の合計はいくつだろうか? 解答 1周する毎に数字の間隔が2広がるわけですから、単純に書いて十分早く答えが出ます。 #!/usr/bin/perl use strict; use warnings; use feature qw/say/; my $sum = 1; for (my ($i, $step) = (1, 2); $i < 1001 * 1001; $step += 2) { $sum += $i += $step for 1 .. 4; } say $sum;

問題 しばらく止まってましたが今日から再開。 原文 Considering quadratics of the form: n 2 + 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|は絶対値): n 2 + 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以上の素数列を生成するならこれらは素数ですから、次のことがいえます： bは素数である a + b + 1は素数である b = 2のとき、aは偶数である それ以外のとき、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) ...

問題 原文 Find the value of d < 1000 for which 1/d contains the longest recurring cycle in its decimal fraction part. 日本語訳 d < 1000 なる 1/d の中で循環節が最も長くなるような d を求めよ。 解答 筆算の過程から類推できるように、この問題は同じ余りが出るまでの間隔を調べる問題に置き替えることができます。 #!/usr/bin/perl use strict; use warnings; use feature qw/say/; use List::Util qw/reduce/; sub rec_cycle_period($$) { my ($deno, $upper_lim) = @_; my %appeared_rems; my $remainder = 10; my $i = 0; do { return 0 if $remainder == 0; return -1 if $i >= $upper_lim; $appeared_rems{$remainder} = $i++; $remainder %= $deno; $remainder *= 10; } until exists $appeared_rems{$remainder}; return $i - $appeared_rems{$remainder}; } say map { $_->[0] } reduce { $a->[1] > $b->[1] ? $a : $b } map { [$_, rec_cycle_period($_, 1000)] } 1 .. 1000;

問題 原文 What is the first term in the Fibonacci sequence to contain 1000 digits? 日本語訳 1000桁になる最初の項の番号を答えよ. 解答 Gaucheのストリームライブラリを使ってみました。 (use util.stream) (define fibonacci-sequence (iterator->stream (lambda (yield end) (let loop ((a 1) (b 1)) (yield a) (loop b (+ a b)))))) (define (digits n) (define (digits-1 m acc) (if (< n m) acc (digits-1 (* m 10) (+ acc 1)))) (digits-1 1 0)) (define (solve) (+ 1 (stream-index (lambda (n) (= 1000 (digits n))) fibonacci-sequence))) (define (main argv) (display (solve)) (newline))

問題 原文 What is the millionth lexicographic permutation of the digits 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9? 日本語訳 0,1,2,3,4,5,6,7,8,9からなる順列を辞書式に並べたときの100万番目を答えよ 解答 n (> 0)桁目の数字が決まると残りの数字の順列は(n - 1)!通りですから、一般にn桁の順列の（0から数えて）m番目というとき、m = p n (n - 1)! + p n-1 (n - 2)! + ... + p 1 (0)! (0 <= p i < i)と表すと、p n , p n-1 , ..., p 1 の値は一意に定まります。 よってn桁目の数字を決めるとき、その時点で使える数字を昇順に並べた中からp n 番目の数字を選ぶという操作をn = 1まで繰り返すことで解が得られます。 (use srfi-1) (define (factorial n) (apply * (iota n 1))) (define (solve) (define (solve-1 n digits acc) (if (null? digits) (list->string (map integer->digit (reverse acc))) (let* ((fact (factorial (- (length digits) 1))) (mult (floor (/ n fact))) (digit (ref digits mult)) (rest (remove (cut = digit <>) digits))) (solve-1 (- n (* fact mult)) rest (cons digit acc))))) (solve-1 (- 1000000 1) (iota 10) '())) (define (main argv) (display (solve)) (newline))