何かを書き留める何か

数学や読んだ本について書く何かです。最近は社会人として生き残りの術を学ぶ日々です。

オンライン整数列大辞典に掲載されている数列をPythonで生成したい #1

それ、Pythonで簡単にできるよ?と言いたかった。

6月は仕事が忙しくて怪文書ブログエントリを書くことができなかった。 7月もなぜか忙しく、このままだと離れてしまうので最近思いついたことを書いてみる。

オンライン整数列大辞典(On-Line Encyclopedia of Integer Sequences, OEIS)とは整数列のデータベースである。 掲載数は30万を超える。 例えば、データベースの1番目A000001は位数 nの群の個数の列である。

各数列の項目の中には、MathematicaMaple、PARI、MAGMA、Sage Mathによる生成方法も掲載されている(すべての項目に掲載されているかどうかは不明)。 とはいえ、これらの専門家向けツールを使わずともPythonやSymPyがあればある程度は作れるのではないだろうか。

そこで、オンライン整数列大辞典のリスト - Wikipediaにあるぐらいの数列をPythonやSymPyで書いてみよう、というのがこのエントリの趣旨である。

A000005: 約数の個数

約数の個数を数えるにはSymPyのdivisor_countを使えば簡単にできる。 内部の実装では素因数分解を利用しているため、大きい整数を与えるとかなり時間がかかると思われる。

from sympy import divisor_count

divisors = [divisor_count(n) for n in range(1, 201)]
divisors[:20]
[1, 2, 2, 3, 2, 4, 2, 4, 3, 4, 2, 6, 2, 4, 4, 5, 2, 6, 2, 6]

A000010: Eulerのトーシェント函数

Eulerのトーシェント函数 \phi(n)とは1から nまでの整数の中で nと互いに素である数(トーシェントと呼ぶ)の総数である。 素数ならば、 \phi(p) = p-1であり、 n素因数分解が与えられていれば簡単に計算できる。 SymPyには函数totientが用意されているので、これを使えば簡単にできる。 内部の実装ではやはり素因数分解を利用しているため、大きい整数を与えるとかなり時間がかかると思われる。

from sympy.ntheory import totient

num_of_totients = [totient(n) for n in range(1, 201)]
num_of_totients[:20]
[1, 1, 2, 2, 4, 2, 6, 4, 6, 4, 10, 4, 12, 6, 8, 8, 16, 6, 18, 8]