chotto2/dstar-dev repository overview
Divisor Stars - 整数の約数を＊でプロットしたリスト
整数の約数が出現する規則性や傾向について、その全体像を観察できるようにした一覧リスト
概要
整数０から10000000までの値の持つ、約数をエラトステネスの篩を使って調べ上げて＊で表示する。
これは、先に公開した Prime Oasis の起源となったプログラムである。
当プログラム（以降、dstarと呼ぶ）のプロットする＊の模様から着想を得て Prime Oasis のコマンド群を作成した。
オブジェクト指向言語に例えるなら、スーパークラスまたは、親クラス的な位置づけである。
従って、dstar の出力する約数の模様を理解できないと、Prime OasisのREADMEを読んでも理解できない。
これが基礎中の基礎となっている。
結果としてのリストは、ファイルサイズが大きいためリポジトリには含めていない。
Releases から resultds.txt をダウンロードして是非とも眺めていって欲しい。
特徴
- 🐳 Docker対応 - 再現可能なビルド環境
- 📊 10000000までの約数 - 教育・研究目的に適したサイズ
必要環境
- Docker Desktop
- Git
結果ファイルの取得
結果ファイル（resultds.txt）はファイルサイズが大きいため、リポジトリには含めていない。
GitHubの Releases ページからダウンロードしてほしい。
# gh CLI を使用する場合
gh release download --pattern "resultds.txt"
ビルドと実行
ビルドと実行は、dstarコマンドをカスタマイズしたい場合に必要となる。 デファイン値 N_MAX を変更すれば、出力を増減させることができる。
注: ローカル環境でメモリ不足が発生する場合は、GitHub Codespaces 上での実行を推奨する。
# リポジトリのクローン
git clone https://github.com/chotto2/dstar-dev.git
cd dstar-dev
# Dockerイメージのビルド
docker build -t dstar-dev .
# Run (使用法の表示)
docker run -it dstar-dev dstar
USAGE: dstar { {-v | --version} | <n_max> [{-m | --memory}] [{-b | --benchmark}] }
-v, --version Show version number
n_max Upper limit for divisor computation (positive integer)
-m, --memory Show memory required for n_max and exit (no computation)
(takes precedence over -b if both are specified)
-b, --benchmark Show elapsed/user/sys time after computation
# Run (バージョン番号の表示)
docker run -it dstar-dev dstar -v
version: 2.0.0
# 実行（リスト出力あり）
docker run -it dstar-dev dstar 10000000
# 実行（リスト出力なし＋性能測定結果の表示）
docker run -it dstar-dev dstar 10000000 -b
real 2.602s user 2.351s sys 0.194s
# Run (リスト出力なし＋性能測定なし＋メモリー使用量の表示)
docker run -it dstar-dev dstar 10000000 -m
total memory = 810901468
パフォーマンス
real 2.654s
user 2.384s
sys 0.183s
※Codespace:2-Core
※'--benchmark'指定でリスト出力なし、性能測定結果を表示
※測定10回の平均値
※約数保持領域を動的に獲得(calloc)
出力例
dstar-devの出力結果を示す。
n: d(n):divisors2(n, 128)
0:10000000:******************************** ...
1: 1:*
2: 2:**
3: 2:* *
4: 3:** *
5: 2:* *
6: 4:*** *
7: 2:* *
8: 4:** * *
9: 3:* * *
10: 4:** * *
11: 2:* *
12: 6:**** * *
13: 2:* *
14: 4:** * *
15: 4:* * * *
...
最初の行は、１行のリストが ':' で区切られた３つのフィールドで構成されていることを示す。
第1フィールドの n は、対象とする整数値を示す。
第2フィールドの d(n) は、整数 n の約数の数を示す。
第3フィールドの divisors2(n, 128) は、約数の位置に＊をプロットすることを示す。
約数（＊）の位置は、第2フィールドに近いほうから、123... という昇順となっている。
divisors2(n, 128) は、約数の上限を 128 までに限定して約数を求める。その結果を＊で表示するようにしている。
例えば、整数 6 の場合はどういう出力になるか見ると、下記のようになっている。
6: 4:*** *
これは整数 6 は、約数が 4 個で、約数は{1,2,3,6}であることを示す。（4 と 5 の位置は空白）
※整数0は特殊なケースで、0でないすべての整数が約数となる（n × 0 = 0）
リストの見どころ
- 第2フィールドの値が２の箇所は、ｎが素数であることを示す。
- VOID域には約数はない。（n<divisor or n/2<divisor<n など）
n: d(n):divisors2(n, 128)
0:10000000:******************************** ...
1: 1:*
2: 2:**
3: 2:* *
4: 3:** *
5: 2:* *
6: 4:*** *
7: 2:* * (VOID)
8: 4:** * *
9: 3:* * *
10: 4:** * *
11: 2:* *
12: 6:**** * *
13: 2:* *
14: 4:** *(VOID)*
15: 4:* * * *
...
- 最初から＊が連続する箇所は素数砂漠を構成する。（n=12,60 など）
下記は素数砂漠の構造を示すため、関連する約数を＊から数値に変更している。
素数砂漠は傘をさしたような形状をしており、前後の整数の約数に影響する。
影響の範囲は、連続した約数の数の２倍＋１の範囲である。
但し、素数砂漠の中心点±1の約数は１なので素数になる可能性がある。
実際、この例でも±1の地点は素数となっている。
54: 8:*** 6 * * * *
55: 4:* 5 * *
56: 8:** 4 ** * * *
57: 4:* 3 * *
58: 4:*2 * *
59: 2:1 *
60: 12:123456 * * * * * *
61: 2:1 *
62: 4:*2 * *
63: 6:* 3 * * * *
64: 7:** 4 * * * *
65: 4:* 5 * *
66: 8:*** 6 * * * *
- 整数 n の約数パターンは、前後45度の角度で同一パターンが展開される。
n=6 の場合を見てみよう。
関連する約数を＊から数値に変更している。
n=6 の約数は、{1,2,3,6} である。
これを前後45度の角度で展開すると下記のようになる。
形式的な定理が存在するかどうかにかかわらず、このパターンは観察によって発見された。
約数の45度の鏡像予想とでもしておく。
n: d(n):divisors2(n, 128)
0:10000000:*****6************************** ...
1: 1:*
2: 2:**
3: 2:* 3
4: 3:*2 *
5: 2:1 *
6: 4:123 6
7: 2:1 *
8: 4:*2 * *
9: 3:* 3 *
10: 4:** * *
11: 2:* *
12: 6:**** 6 *
13: 2:* *
14: 4:** * *
15: 4:* * * *
...
技術詳細
- 言語: C
- ライブラリ: GMP (GNU Multiple Precision Arithmetic Library)
- ビルドシステム: CMake
- 約数の範囲: 0..10000000
注意事項
⚠️ 重要: このバージョンは教育・研究目的の実装です。整数 10000000 までの約数を扱うため、現代の暗号システム（RSA-4096など）には影響しません。
今後の予定
- 📝 arXivへの論文投稿予定
- 📚 アルゴリズムの詳細な理論的背景
ライセンス
MIT License
著者
N.Arai
引用
論文準備中。公開後、適切な引用方法を記載します。
関連リンク
- 論文: arXiv (準備中)
- リポジトリ: https://github.com/chotto2/dstar-dev
Tag summary
Content type
Image
Digest
sha256:3f078467c…
Size
546.5 MB
Last updated
5 months ago
docker pull chotto2/dstar-dev