「ループ・再帰・gotoを使わず1から100までの数値を印字する」Conner Davis 氏の回答の考察

2019年6月に以下の記事が投稿されました。

• ループ、再帰、gotoを使わずに1から100までを印字するC++プログラムは書けますか？に対するIchi Kanayaさんの回答 - Quora

英語版の記事「How to print 1 to 100 in C++ without a loop, goto or recursion - Quora」から興味深い回答を抜き出して、それにランク付けをしながら和訳してくださっている記事です。

初級や中級は「まぁあるよね（C++知らないけれど……）」という感じですが、 上級とされた「マイクロソフト社のデータサイエンティスト Conner Davis 氏」の回答が面白かった ので、ご紹介を兼ねてその発想の源泉を推測してみることにしました。

Conner Davis 氏の回答

以下に Conner Davis 氏の回答の和訳を引用します。

マイクロソフト社のデータサイエンティスト Conner Davis 氏は 「C++のことは全くわからないのだが」 と断りつつ想像の遥か斜め上を行く回答を書かれています．[9]

氏いわく
『まず $\frac{1}{1-x} = \sum_{n=0}^\infty x^n$ の両辺を微分して $(1-x)^{-2} = \sum_{n=1}^\infty nx^{n-1}$ を得ます.
次に $x = 1000^{-1}$ とし, 両辺を $1000$ で割ります. そうすると... $\frac{1000}{999^2} = 0.001002003004 \dots 098099100\dots$ 最初の300桁はこのように続きます.
つまりC++で任意精度演算を使って $999^{−2}$ を300桁まで計算し印字すれば1から100まで印字したことになります．』

とのこと。

確かに 0. があって 001 の次に 002 が来て…ってなっていますね。

実際にプログラムを書いてみる

私もC++は全くわからないけれど、各言語にある任意精度演算ライブラリを使えば行けるかなと、使い慣れている Perl で書いてみました。久々にコアモジュールの Math::BigFloat のお世話になります。

eccentric-sequence-davis.pl

#!/usr/bin/env perl

use strict;
use warnings;
use feature qw(say);
use Math::BigFloat;

Math::BigFloat->accuracy(300-2);
my $x = 1000 / Math::BigFloat->new(999**2);
my $str = $x->bstr();

say "--- $str";

$str =~ s/^0\.//;
say join " ", map { $_+0 } $str =~ /(\d\d\d)/g;

output

$ perl eccentric-sequence-davis.pl
--- 0.001002003004005006007008009010011012013014015016017018019020021022023024025026027028029030031032033034035036037038039040041042043044045046047048049050051052053054055056057058059060061062063064065066067068069070071072073074075076077078079080081082083084085086087088089090091092093094095096097098099100
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100

Ruby にも標準添付ライブラリ bigdecimal があるのでやってみます。

eccentric-sequence-davis.rb

#!/usr/bin/env ruby

require 'bigdecimal'

x = BigDecimal("1000").div(BigDecimal("999") ** 2, 300-1)
str = x.to_s("F")

puts "--- #{str}"

str.sub!(/^0\./, "")
puts str.scan(/\d\d\d/).map{ |s| s.to_i(10) }.join(" ")

output

$ ruby eccentric-sequence-davis.rb
--- 0.0010020030040050060070080090100110120130140150160170180190200210220230240250260270280290300310320330340350360370380390400410420430440450460470480490500510520530540550560570580590600610620630640650660670680690700710720730740750760770780790800810820830840850860870880890900910920930940950960970980991001
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100

着想の背景を想像する

和訳記事では 「想像の遥か斜め上」 と書かれていた Conner Davis 氏の回答ですが、その着想にどのような背景があるか、数学的視点と計算機科学的視点から想像してみます。

数学的な視点は母関数

数学には 母関数 という考え方があります。ざっくり言うと、 数列 $a_n$ を $x^n$ の係数として持たせて総和を取ることで、数列の情報をその総和である関数に持たせること です。

$n$ 番目の数列の値を $a_n$ と書いて、数列全体を $\{a_n\}$ などと書きますが、例えば今回のような数列 $a_n = n$ は

f(x) = \sum_{n=0}^\infty n x^n

または Conner Davis 氏が書いたように $n$ を $1$ から開始した

f(x) = \sum_{n=1}^\infty n x^{n-1}

という形式的冪級数（$x$ の多項式で特にべき乗の上限がないもの）になります。 $n$ を $0$ と $1$ どちらから始めるかは必要に応じて調整することにしましょう。

この形式的冪級数が表す $f(x)$ は何かというと、Conner Davis 氏の言う通りの回答となります。

数学や理工学の専門課程で冪級数を扱っていれば、この形式的冪級数が表す関数は馴染みのあるものですし、たとえそうでなくても（氏の項別微分とは逆に）項別積分をして

\sum_{n=0}^\infty x^n

の形に持ち込めば、高校生3年生が習う等比級数の和の公式

\sum_{n=0}^\infty r^n = \frac{1}{1-r} \quad (|r|<1)

が適用できることがわかるでしょう。

形式的冪級数は「形式的」という通り、その収束性をあまり気にせず牧歌的に冪級数同士を項別計算して、形式的冪級数が表す母関数を求めることもしばしば行われるようです。収束性の議論を大切にする初等解析学の立場から見ると少々強引かつ不安にも思えますが、そういうものだと思っておくとよさそうです。

実際に $a_n = n$ の形式的冪級数の関数表示を、項別計算などを使って求めてみましょう。

f(x) = \sum_{n=1}^\infty n x^{n-1}

より

\begin{eqnarray}
f(x) - x f(x) &=& \sum_{n=1}^\infty n x^{n-1} - \sum_{n=1}^\infty n x^{n} \\
&=& 1 + \sum_{n=1}^\infty (n+1) x^{n} - \sum_{n=1}^\infty n x^{n} \\
&=& 1 + \sum_{n=1}^\infty x^{n} \\
&=& 1 + \frac{x}{1-x} \\
&=& \frac{1-x+x}{1-x} \\
&=& \frac{1}{1-x}
\end{eqnarray}

なので

(1-x)f(x) = \frac{1}{1-x}

つまり

f(x) = \frac{1}{(1-x)^2}

となります。

計算機科学的な視点は任意進数表現

先程の数学的視点で、今回表示したい数列 $a_n = n$ の母関数がわかりました。ただこの母関数から数列を表示しようと思った場合、そのままでは使いづらいです。

10進数ではない N 進数の話

計算機科学、IT技術領域は10進数以外の様々な進数が使われます

• コンピュータ内部は 0 か 1 だけのビットの世界：2進数
• 2進数は扱いづらいので、4桁ずつまとめて表示：16進数
• 各モードで8つの選択肢があるので、各モードを桁として各桁列挙：8進数（ファイルパーミッション表示など）

2進数が基本でありつつ、特に2進数だと冗長表現になるところで 2の冪乗進数、特に16進数が使われることが多いようです。

同じく、10進数が基本でありつつ、様々な理由で $10^n$ （10の冪乗）進数も使い所があります。

特に今回使用しようとしている任意精度数値ライブラリのようなものを自作しようとした場合も10の冪乗進数が考えやすいでしょう。32ビットの int であれば符号なしで最大40億少々しか格納できませんが、自分で配列を定義して、その各配列に格納された0〜9の数値が各桁だとして配列自体が整数だとすれば任意精度の数値を作ることができます。ただ、もともとの int が21億ほど格納できるのに、各配列の int に格納する数値が 0〜9 なのは効率的に問題があるので、各配列の数を 0 から m-1 まで広げて m 進数表現とするのは良さそうです。10進数に馴染みのある我々が直感的に分かりやすい実装は m を 10 の冪乗にすることです（私が学生時代に習ったのは10000進数を自作して円周率計算するというものでした）。

つまり、10の冪乗進数は我々が馴染みのある10進数に埋め込みやすい という意味でアドバンテージがあります。

100進数を10進数に埋め込む例

100進数があった場合、0〜99が一桁となります。別途90個の文字を用意するのも手間なので、数字2文字で1桁という約束として、位取りを _ 記号で行うことにすれば100進数を書くことができます。

この表記では、99までの数字は10進数と見分けが付きません（桁の約束が違いますが）。10進数で 100 は、この100進数では 1_00 です。10進数で 2525 は、この100進数では 25_25 です。たとえ10進数の25に対して100進数で別の文字が割り当てられていたとしても、位取りとして10進数との変換は些細なことです。これは2進数と16進数（$16 = 2^4$）でも同じことです。

$N$ 進数の小数点表記は後ほど扱いますが、上記の整数部分での「埋め込み」と同様のことが言えます。10進数の 25/99 は 0.25252525... という循環小数ですが、上記の100進数では 25/99 = 0.25_25_25_25_25... といった表記になります。

任意進数の数を10進数に変換する

任意進数を求める時は以下のようにします。

$N$進数の数の $n$ 桁目を $d_n$（ただし $0 \leq d_n \lt N$） と定義します。なお、最初の桁の添字は 0、つまり最初の桁は $d_0$ とします。その $N$ 進数での数 $d = \dots d_2 d_1 d_0$ （隣接する各 $d_i$ は積ではなく位取りを表しています）を10進数に変換するには以下のようにします。

\sum_{n=0} d_{n} N^{n} \qquad (0 \leq d_{n} \lt N)

2進数で 1110 は 14 ですが、この式に当てはめると $N=2$ で $(d_3,d_2,d_1,d_0) = (1,1,1,0)$ なので

\begin{eqnarray}
\sum_{n=0}^4 2^{n} d_n &=& 2^3 \cdot 1 + 2^2 \cdot 1 + 2^1 \cdot 1 + 2^0 \cdot 0 \\
&=& 8 + 4 + 2 \\
&=& 14
\end{eqnarray}

となります。

埋め込みやすいという意味で10の冪乗進数を採用すればいい、そして今回は「1から100」までと10進数3桁までの表示を求められているということであれば 1000進数を使うと良さそうだ という発想になるでしょう。

今までは整数の話でしたが、整数ではなく小数点がある場合に N 進数を表す際、上記での総和の $N$ の冪乗部分が負になっていきます。

N進数の小数点表記

N進数の数 $d$ が小数点表記を持つ場合を考えます。整数部の桁を小さい方から $d_0, d_1, d_2, \ldots$ とします。小数点第 $n$ 位を負の添字 $-n$ を使って $d_{-n}$ とすると

d = \cdots d_2 \, d_1 \, d_0 \,.\, d_{-1} \, d_{-2} \, d_{-3} \ldots

と表され、10進数での値は

d = \sum_{n} d_{n} N^{n}

と表されます。添字 $n$ は、存在する桁の正負の添字全てに渡るものとします。

例えば 10進数で 0.5 は 2進数では 0.1 です。$ 0.5 = 2^{-1} \times 1$ より。

なお、10進数では有限小数展開の値も、別のN進数で表すと無限小数展開になる場合があります。

10進数の 0.1 が 2進数では無限小数展開 $0.000\dot{1}10\dot{0}$（頭ドットは循環小数の表記法）になることは

0.1 = 2^{-4} + 2^{-5} + 2^{-8} + 2^{-9} + \cdots

という無限和で表せることから導くことができます。

実際、上記右辺の和 $S$ を計算すると

\begin{eqnarray}
S &=& 2^{-4} + 2^{-5} + 2^{-8} + 2^{-9} + \cdots \\
    &=& \sum_{n=1}^\infty \left( 2^{-4n} + 2^{-4n-1} \right) \\
    &=& \sum_{n=1}^\infty \frac{3}{2^{4n+1}} \\
    &=& \frac{3}{2} \sum_{n=1}^\infty \left( \frac{1}{16}\right)^{n} \\
    &=& \frac{3}{2} \frac{  \frac{1}{16} }{ 1 - \frac{1}{16}} \\
    &=& \frac{3}{2} \cdot \frac{1}{16} \cdot \frac{16}{15} \\
    &=& \frac{1}{10} \\
    &=& 0.1
\end{eqnarray}

となります。ここでも等比級数の無限和の公式

\sum_{k=1}^\infty r^k = \frac{r}{1-r} \quad (|r|<1)

を使用しました。

母関数と任意進数を組み合わせる

数学的発想の母関数は、数列 $\{a_n\}$ に対し

\sum_{n=0}^\infty a_n x^n

でした。

計算機科学的発想の$N$進数の10進数への計算は、$N$進数 $d = \dots d_2 d_1 d_0 $ に対し

\sum_{n} d_{n} N^{n}

でした。

記号や添字の違いはありますが、 見かけはだいぶ似ています。

1000進数だということで $N=1000$ としてしまうと、$\sum d_n N^n$ は

1 + 2 \cdot 1000  + 3 \cdot 1000^2 + 4 \cdot 1000^3 + \cdots \to \infty

となってしまい素直に発散してしまいますが、$N=1000^{-1}$ とすると1未満の数となり、小数点以下に上述のような桁の約束が生まれることになります。これは「$\frac{1}{1000}$ 進数」ということではなく、$1000$ 進数の1未満の正の数の無限小数展開となっています。

前出の通り、$N$進数の小数点表示については整数部分よりも若干の考察が必要ですが、10進数の小数点表示についての基本的な知識はそのまま10の冪乗進数に適用することができます。

この辺りの前提知識が、Conner Davis 氏の発想の源泉なのかなと想像しています。

1000進数の小数点展開で1から100を出す

では、改めて Conner Davis 氏の答えをなぞるように、母関数と1000進数の小数点展開を使った回答を作ってみることにしましょう。

数列 $\{a_n\}$ の一般項が $a_n = n$ の時、母関数

f(x) = \sum_{n=0}^\infty a_n x^n = \sum_{n=0}^\infty n x^n

は、 $|x| \lt 1$ の範囲で等比級数の公式

\sum_{n=0}^\infty x^n = \frac{1}{1-x}

が成り立つので、項別微分して

\sum_{n=1}^\infty n x^{n-1} = \frac{1}{(1-x)^2}

が言える（項別微分の妥当性は省略。また収束半径は上記同様 $|x| \lt 1$ ）。

両辺に $x$ をかけると、

\sum_{n=0}^\infty n x^n = \frac{x}{(1-x)^2}

となる。ここで、 $n＝0$ での $nx^n$ は $x$ の値に関係なく $0$ になるので、見やすさのため総和記号の添字を $0$ から開始するよう変更している。

この表示は節冒頭の母関数 $f(x)$ そのものであり、

f(x) = \sum_{n=0}^\infty n x^n = \frac{x}{(1-x)^2}

が言える。

ここで $x = \frac{1}{1000}$ を代入すると、

f\left(\frac{1}{1000}\right) = \sum_{n=0}^\infty \frac{n}{1000^n} = \frac{1000}{999^2}

となり、級数の総和を

\sum_{n=-1}^{-\infty} (-n)\cdot 1000^n

と見れば、 $d_n$ を

\begin{eqnarray}
d_n
 =
  \begin{cases}
    0 & ( n \geqq 0 ) \\
    -n & ( n \lt 0 )
  \end{cases}
\end{eqnarray}

と定義し、かつ $N = 1000$ とすると、少なくとも $n \geq -100$ では $|d_n| \lt N$ であり、1未満の小数点展開

\sum_{n=-1}^{-\infty} d_n N^n 

となっている。

この1000進数の小数展開は、少なくとも $n \geq -100$ の範囲においては10進数のそれへの自然な対応となっており、

\begin{eqnarray}
f\left(\frac{1}{1000}\right) &=& \frac{1000}{999^2}  \\
 &=& \frac{1}{1000} + \frac{2}{1000^2} + \frac{3}{1000^3} + \cdots \\
 &=& 0.001\,002\,003\,004 \cdots 097\,098\,099\,100 \cdots

\end{eqnarray}

という10進数の小数点展開を得る。

議論の細部に対する疑問

今まで考察した母関数や1000進数の議論の中で、いくつか省かれた細部に対する疑問があると思います。

こちらについては、疑問があれば見出しを追加、解説を追加した場合はストックした方へ通知を送ります（いいねと合わせてストックして頂けると嬉しいです）。

収束性や項別演算の妥当性について

（未執筆）

1000以上の項が1000進数を乱さないか

（未執筆）

一般化の考察

（未執筆）

当初の問題に他にも回答があるか

C++ は置いといて、多くのプログラミング言語にはループを内包している表現がいくつもあります。

• 範囲データ（Perl や Ruby の .. など）
• 正規表現のグローバルマッチ

1.upto(100) { |i| puts i }

print join " ", 1..100;

もちろん任意精度の数値ライブラリや、それこそプログラミング言語の根底の実装がループを内包しているので、 今回の問題はいかにループという構文に直接触れず、間接的にそれを使うかという頭の体操 のような印象を持ちました。

参考

• 私の回答 :print 1..100 without loop, recursive, goto by Perl (not C++)

ループ・再帰・goto ナシ縛りで1から100までの数を書く問題、上級とされている Conner Davis 氏の回答を Perl で書いてみた。任意精度の浮動小数点計算には Math::BigFloat が便利。https://t.co/Hw0tOzk971https://t.co/HgNHYvVIWy

— OGATA Tetsuji (@xtetsuji) 2019年6月20日