階乗進数

1. プログラムの概要

factrep - 指定された桁数の階乗進数で表せる数の一覧を表示する

n桁の階乗進数で表せる最大の数は

\begin{equation} n!n + (n - 1)!(n - 1) + ... + 3!3 + 2!2 + 1!1 = (n + 1)! - 1 \end{equation}

となります。これは数学的帰納法を使って証明できます。

\(n = 1\)のとき、

\begin{align*} 左辺 &= 1!1 = 1 \\ 右辺 &= (1 + 1)! - 1 \\ &= 2! - 1 \\ &= 1 \\ \end{align*}

となり、成り立ちます。

\(n = m\)のとき成り立つと仮定して、\(n = m + 1\)のときを調べます。

\begin{align*} 左辺 &= (m + 1)!(m + 1) + \{m!m + (m - 1)!(m - 1) + ... + 3!3 + 2!2 + 1!1\} \\ &= (m + 1)!(m + 1) + \{(m + 1)! - 1\} \\ &= (m + 1)!(m + 2) - 1 \\ &= (m + 2)! - 1 \end{align*}

これにより、\(n = m + 1\)のときも成り立つことが分かります。よって、(1)は任意のnに対して成り立ちます。

2. C

/*
 * オリジナルの出典「C言語による最新アルゴリズム事典」奥村晴彦著 - P19
 * インデントは変更してあります。
 * 他にも、メッセージや変数名や処理を変更している場合があります。
 */

#include <stdio.h>

#define N 3

int main()
{
    int i, k;
    int c[N + 2];

    for (k = 1; k <= N + 1; k++)
    {
        c[k] = 0;
    }

    i = 0;
    do
    {
        printf("%3d:", i);
        i++;
        for (k = N; k >= 1; k--)
        {
            printf(" %d", c[k]);
        }
        printf("\n");

        k = 1;
        while (c[k] == k)
        {
            c[k] = 0;
            k++;
        }
        c[k]++;
    } while (k <= N);
}

3. Emacs Lisp

(defun factrep-initial-list (n init-value)
  (if (<= n 0)
      nil
    (cons init-value (factrep-initial-list (1- n) init-value))))

(defun factrep-print-next (x n-digits factrep)
  (let (i)
    (princ (format "%3d:" x))
    (mapc (lambda (x) (princ (format "%d " x)))
          (cdr (butlast (reverse factrep))))
    (princ "\n")

    (setq i 1)
    (while (= (nth i factrep) i)
      (setcar (nthcdr i factrep) 0)
      (setq i (1+ i)))

    (setcar (nthcdr i factrep) (1+ (nth i factrep)))

    (when (<= i n-digits)
      (factrep-print-next (1+ x) n-digits factrep))))

(defun factrep-print (n)
  (let ((max-lisp-eval-depth 10000)
        (max-specpdl-size 10000))
    (factrep-print-next 1 n (factrep-initial-list (+ n 2) 0))))

(with-output-to-temp-buffer "*factrep*" (factrep-print 3))

max-lisp-evel-depth と max-specpdl-size を指定しないと、n=4までしか処理できません。 10000を指定してもn=5までです。 Emacs Lispには末尾呼出し最適化 (TCO; Tail Call Optimization)がないため、あまり深い再帰はできません。素直にループで処理した方が良かったです。

4. Bash

#!/bin/bash

N=3

factrep=()
for i in $(seq $(($N + 2)))
do
    factrep+=(0)
done

i=0
while
    printf "%3d:" $i
    ((i++))

    for k in $(seq $N -1 1)
    do
        printf " %d" ${factrep[$k]}
    done
    printf "\n"

    j=1

    while [ ${factrep[$j]} -eq $j ]
    do
        factrep[$j]=0
        ((j++))
    done

    ((factrep[$j]++))

    [ $j -le $N ]
do true; done

5. Fish

#!/usr/bin/fish

set N 3

for i in (seq 1 (math $N + 1))
    set -a factrep 0
end

echo $factrep

set i 0
while true
    printf "%3d:" $i
    set i (math $i + 1)

    for k in (seq $N -1 1)
        printf " %d" $factrep[$k]
    end

    printf "\n"

    set j 1
    while test $factrep[$j] -eq $j
        set factrep[$j] 0
        set j (math $j + 1)
    end
    set factrep[$j] (math $factrep[$j] + 1)

    if test $j -gt $N
        break
    end
end