@butchi/integer-sequences

整数列・整数集合を、操作ごとに適したアルゴリズムで扱う TypeScript ライブラリです。MVP ではフィボナッチ数、素数、平方数を number / bigint 名前空間から利用できます。実行時依存はありません。

インストール

pnpm add @butchi/integer-sequences

基本的な使い方

import { bigint, number, range } from "@butchi/integer-sequences";

number.fibonacci.term(10); // 55
number.fibonacci.take(10); // [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]
number.fibonacci.has(55); // true
number.fibonacci.next(55); // 89
number.fibonacci.upTo(100); // [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89]

bigint.fibonacci.term(100); // 354224848179261915075n
bigint.fibonacci.has(55n); // true

number.prime.term(0); // 2
number.prime.take(10); // [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
number.prime.has(97); // true
number.prime.next(100); // 101
number.prime.upTo(20); // [2, 3, 5, 7, 11, 13, 17, 19]

range(5); // [0, 1, 2, 3, 4]
range(2, 5); // [2, 3, 4]

各概念は callable 関数ではなく、term、take、has などを持つ通常のオブジェクトです。公開添字はすべて 0 始まりで、BigInt 版の term(index) も添字には number を使います。

関数はコールバックとしても利用できます。Number 版フィボナッチで正確に返せる添字は 0 から 78 までなので、安全な合成例は次のとおりです。

const fibonacci = number.fibonacci.term;
const isPrime = number.prime.has;

const fibonacciPrimes = range(79)
  .map(fibonacci)
  .filter(isPrime);

当初の API 例として示されることがある次のコードは、F(79) で Number の安全整数範囲を超えるため、意図どおり RangeError になります。近似値を返すために安全性を緩めることはありません。

const fibonacci = number.fibonacci.term;
const isPrime = number.prime.has;

const fibonacciPrimes = range(100)
  .map(fibonacci)
  .filter(isPrime);

Number と BigInt

number と bigint は明示的に分離されています。入力や結果に応じた自動切り替えは行いません。

• Number API の数値入力は安全整数に限定されます。
• Number API が整数を返すときは、結果も必ず安全整数です。正確に表現できなければ IntegerOverflowError（RangeError のサブクラス）を投げます。
• 判定 API も安全整数でない Number 入力を拒否します。
• BigInt API の値は bigint ですが、添字と take の件数は非負の安全な number です。
• bigint.prime は MVP では has と next だけを公開します。存在しない term などは TypeScript の型上も利用できません。

たとえば number.fibonacci.term(78) は正確な 8944394323791464 を返しますが、number.fibonacci.term(79) は例外になります。後者が必要なら bigint.fibonacci.term(79) を利用してください。

操作

• term(index): 0 始まりの第 index 項。
• iterate(): 先頭から順に値を生成する iterator。
• take(count): 先頭から count 項。項数を指定します。
• has(value): 値が概念に属するかを判定します。
• next(value): value より厳密に大きい最小の該当値。
• upTo(limit): limit 以下の全項。上限値を含みます。

take(10) は「10 項」、upTo(10) は「値が 10 以下」という違いがあります。フィボナッチ数は 1 を 2 回含む非減少列なので、upTo(1) は [0, 1, 1] です。

操作ごとのアルゴリズム

すべての操作を term の反復から作る設計ではありません。現在の既定実装は次のとおりです。

| 概念 | 操作 | 実装方針 | | --- | --- | --- | | Fibonacci | term | fast doubling | | Fibonacci | iterate / next / upTo | 直前 2 項を使う逐次漸化式 | | Fibonacci | has | 5n² ± 4 の完全平方判定 | | Prime (Number) | term / take / upTo | エラトステネスの篩 | | Prime | iterate / has / next | 決定的試し割り | | Square | term | 二乗による直接計算 | | Square | iterate / upTo | 奇数差分による逐次生成 | | Square | has / next | 正確な整数平方根 |

BigInt の素数判定も確率的判定ではなく、最後まで因数を調べる決定的試し割りです。結果は正確ですが、非常に大きな入力には実用的でない場合があります。

実装情報は各概念の operations から参照できます。

number.fibonacci.operations.term;
// {
//   source: "native",
//   implementationId: "fibonacci-number-term-fast-doubling-v1",
//   algorithmId: "fibonacci-fast-doubling"
// }

number.fibonacci.operations.take;
// { source: "derived", derivedFrom: "iterate" }

algorithmId は採用中の計算法を説明するための algorithmRegistry への参照 ID です。利用者が実行時にアルゴリズムを選ぶ命令ではありません。

概念の定義とフォールバック

implementation で関数と実装メタ情報をまとめ、defineIntegerConcept に登録できます。

import {
  defineIntegerConcept,
  implementation,
} from "@butchi/integer-sequences";

const example = defineIntegerConcept({
  meta: {
    id: "example",
    slug: "example",
    name: { ja: "例", en: "Example" },
    order: "strictly-increasing",
    finite: false,
    indexing: { publicOffset: 0 },
  },
  number: {
    term: implementation((index: number) => index * 2, {
      implementationId: "example-term-v1",
    }),
  },
});

example.number.take(4); // [0, 2, 4, 6]

専用実装がない場合のフォールバックは限定されています。

1. take: 専用 take → iterate → term
2. iterate: 専用 iterate → term
3. upTo: 単調な列で iterator が利用できる場合だけ iterator から導出
4. next: 狭義単調増加列で iterator が利用できる場合だけ iterator から導出
5. has: 専用実装がある場合だけ公開
6. term: 専用実装がある場合だけ公開

開発

pnpm install
pnpm check

ソースの責務は次のように分かれています。

• src/core: 型、安全整数ポリシー、実装ヘルパー、フォールバック
• src/algorithms: 説明用アルゴリズムレジストリ
• src/concepts: 各概念のメタ情報と Number / BigInt 実装
• src/namespaces: 公開名前空間の組み立て
• src/utilities: range などの独立ユーティリティ

新しい概念は src/concepts に実装と定義を追加し、src/namespaces で公開します。新しい説明用アルゴリズム ID は src/algorithms/registry.ts に追加します。共通の導出規則を変える場合だけ src/core/defineIntegerConcept.ts を変更してください。

MVP の制約

• BigInt 添字には対応しません。
• BigInt 素数の term、take、iterate、upTo は提供しません。
• Number / BigInt の自動切り替えと、複数アルゴリズムの実行時選択は行いません。
• 篩や大量列挙は出力件数に応じたメモリを必要とします。
• BigInt 素数判定は正確ですが、大きな入力では試し割りに長い時間がかかります。
• OEIS ID はメタ情報として保持するだけで、自動取得は行いません。