数学 - Python - 代数学 - 整数 - 素数、素因数分解(整数部分、Gaussの記号、階乗、標準分解、素数のべき指数)

代数系入門

学習環境

• Surface 3 (4G LTE)、Surface 3 タイプ カバー、Surface ペン(端末)
• Windows 10 Pro (OS)
• Nebo(Windows アプリ)
• iPad Pro + Apple Pencil
• MyScript Nebo(iPad アプリ)
• 参考書籍
  • Pythonからはじめる数学入門
  • JavaScriptリファレンス 第6版
  • インタラクティブ・データビジュアライゼーション

代数系入門 (松坂 和夫(著)、岩波書店)の第1章(整数)、5(素数、素因数分解)、問題18.を取り組んでみる。

18. 
    

    1から n までの整数で、

    $p^i\left(i=1,2,\dots \; <!--\; horizontal\; ellipsis\; -->\right)$

    で割り切れて、

    $p^{i+1}$

    では割り切れない整数の個数を

    $n_i$

    とおく。

    このとき標準分解に現われる p のべき指数は

    $\begin{array}{}{n}_1+2n_2+3n_3+\dots \; <!--\; horizontal\; ellipsis\; -->\\ =\left(n_1+n_2+n_3+\dots \; <!--\; horizontal\; ellipsis\; -->\right)+\left(n_2+n_3+\dots \; <!--\; horizontal\; ellipsis\; -->\right)+\left(n_4+\dots \; <!--\; horizontal\; ellipsis\; -->\right)\end{array}$

    ここで、

    $n_1+n_2+n_3+\dots \; <!--\; horizontal\; ellipsis\; -->$

    は 1から n までの整数の p の倍数の個数、

    $n_2+n_3+\dots \; <!--\; horizontal\; ellipsis\; -->$

    は1から n までの整数の p の二乗の倍数の個数、

    $n_3+\dots \; <!--\; horizontal\; ellipsis\; -->$

    は1から n までの整数の p の三乗の倍数の個数である。

    同様に、

    $n_s+n_{s+1}+\dots \; <!--\; horizontal\; ellipsis\; -->$

    は1から n までの整数の p の s 乗の倍数の個数である。

    よって、 積 n の階乗の標準分解に現われるp のべき指数は、

    $\begin{array}{}\left(n_1+n_2+\dots \; <!--\; horizontal\; ellipsis\; -->\right)+\left(n_2+n_3+\dots \; <!--\; horizontal\; ellipsis\; -->\right)+\left(n_4+n_5+\dots \; <!--\; horizontal\; ellipsis\; -->\right)+\dots \; <!--\; horizontal\; ellipsis\; -->\\ =\left[\frac{n}{p}\right]+\left[\frac{n}{p^2}\right]+\left[\frac{n}{p^3}\right]+\dots \; <!--\; horizontal\; ellipsis\; -->\end{array}$

コード(Emacs)

Python 3

#!/usr/bin/env python3
from sympy import pprint, factorial, factorint, floor

for n in list(range(2, 10)) + list(range(50, 60)):
    a = factorial(n)
    ps = factorint(a)
    for t in [n, a, ps]:
        pprint(t)
    for p in ps:
        s = sum([floor(n / p ** i) for i in range(1, 20)])
        for t in [p, s, ps[p] == s]:
            print(t, end=' ')
        print()
    print()

入出力結果(Terminal, Jupyter(IPython))

$ ./sample18.py
2
2
{2: 1}
2 1 True 

3
6
{2: 1, 3: 1}
2 1 True 
3 1 True 

4
24
{2: 3, 3: 1}
2 3 True 
3 1 True 

5
120
{2: 3, 3: 1, 5: 1}
2 3 True 
3 1 True 
5 1 True 

6
720
{2: 4, 3: 2, 5: 1}
2 4 True 
3 2 True 
5 1 True 

7
5040
{2: 4, 3: 2, 5: 1, 7: 1}
2 4 True 
3 2 True 
5 1 True 
7 1 True 

8
40320
{2: 7, 3: 2, 5: 1, 7: 1}
2 7 True 
3 2 True 
5 1 True 
7 1 True 

9
362880
{2: 7, 3: 4, 5: 1, 7: 1}
2 7 True 
3 4 True 
5 1 True 
7 1 True 

50
30414093201713378043612608166064768844377641568960512000000000000
{2: 47, 3: 22, 5: 12, 7: 8, 11: 4, 13: 3, 17: 2, 19: 2, 23: 2, 29: 1, 31: 1, 3
7: 1, 41: 1, 43: 1, 47: 1}
2 47 True 
3 22 True 
5 12 True 
7 8 True 
11 4 True 
13 3 True 
17 2 True 
19 2 True 
23 2 True 
29 1 True 
31 1 True 
37 1 True 
41 1 True 
43 1 True 
47 1 True 

51
1551118753287382280224243016469303211063259720016986112000000000000
{2: 47, 3: 23, 5: 12, 7: 8, 11: 4, 13: 3, 17: 3, 19: 2, 23: 2, 29: 1, 31: 1, 3
7: 1, 41: 1, 43: 1, 47: 1}
2 47 True 
3 23 True 
5 12 True 
7 8 True 
11 4 True 
13 3 True 
17 3 True 
19 2 True 
23 2 True 
29 1 True 
31 1 True 
37 1 True 
41 1 True 
43 1 True 
47 1 True 

52
80658175170943878571660636856403766975289505440883277824000000000000
{2: 49, 3: 23, 5: 12, 7: 8, 11: 4, 13: 4, 17: 3, 19: 2, 23: 2, 29: 1, 31: 1, 3
7: 1, 41: 1, 43: 1, 47: 1}
2 49 True 
3 23 True 
5 12 True 
7 8 True 
11 4 True 
13 4 True 
17 3 True 
19 2 True 
23 2 True 
29 1 True 
31 1 True 
37 1 True 
41 1 True 
43 1 True 
47 1 True 

53
4274883284060025564298013753389399649690343788366813724672000000000000
{2: 49, 3: 23, 5: 12, 7: 8, 11: 4, 13: 4, 17: 3, 19: 2, 23: 2, 29: 1, 31: 1, 3
7: 1, 41: 1, 43: 1, 47: 1, 53: 1}
2 49 True 
3 23 True 
5 12 True 
7 8 True 
11 4 True 
13 4 True 
17 3 True 
19 2 True 
23 2 True 
29 1 True 
31 1 True 
37 1 True 
41 1 True 
43 1 True 
47 1 True 
53 1 True 

54
230843697339241380472092742683027581083278564571807941132288000000000000
{2: 50, 3: 26, 5: 12, 7: 8, 11: 4, 13: 4, 17: 3, 19: 2, 23: 2, 29: 1, 31: 1, 3
7: 1, 41: 1, 43: 1, 47: 1, 53: 1}
2 50 True 
3 26 True 
5 12 True 
7 8 True 
11 4 True 
13 4 True 
17 3 True 
19 2 True 
23 2 True 
29 1 True 
31 1 True 
37 1 True 
41 1 True 
43 1 True 
47 1 True 
53 1 True 

55
12696403353658275925965100847566516959580321051449436762275840000000000000
{2: 50, 3: 26, 5: 13, 7: 8, 11: 5, 13: 4, 17: 3, 19: 2, 23: 2, 29: 1, 31: 1, 3
7: 1, 41: 1, 43: 1, 47: 1, 53: 1}
2 50 True 
3 26 True 
5 13 True 
7 8 True 
11 5 True 
13 4 True 
17 3 True 
19 2 True 
23 2 True 
29 1 True 
31 1 True 
37 1 True 
41 1 True 
43 1 True 
47 1 True 
53 1 True 

56
710998587804863451854045647463724949736497978881168458687447040000000000000
{2: 53, 3: 26, 5: 13, 7: 9, 11: 5, 13: 4, 17: 3, 19: 2, 23: 2, 29: 1, 31: 1, 3
7: 1, 41: 1, 43: 1, 47: 1, 53: 1}
2 53 True 
3 26 True 
5 13 True 
7 9 True 
11 5 True 
13 4 True 
17 3 True 
19 2 True 
23 2 True 
29 1 True 
31 1 True 
37 1 True 
41 1 True 
43 1 True 
47 1 True 
53 1 True 

57
40526919504877216755680601905432322134980384796226602145184481280000000000000
{2: 53, 3: 27, 5: 13, 7: 9, 11: 5, 13: 4, 17: 3, 19: 3, 23: 2, 29: 1, 31: 1, 3
7: 1, 41: 1, 43: 1, 47: 1, 53: 1}
2 53 True 
3 27 True 
5 13 True 
7 9 True 
11 5 True 
13 4 True 
17 3 True 
19 3 True 
23 2 True 
29 1 True 
31 1 True 
37 1 True 
41 1 True 
43 1 True 
47 1 True 
53 1 True 

58
235056133128287857182947491051507468382886231818114292442069991424000000000000
0
{2: 54, 3: 27, 5: 13, 7: 9, 11: 5, 13: 4, 17: 3, 19: 3, 23: 2, 29: 2, 31: 1, 3
7: 1, 41: 1, 43: 1, 47: 1, 53: 1}
2 54 True 
3 27 True 
5 13 True 
7 9 True 
11 5 True 
13 4 True 
17 3 True 
19 3 True 
23 2 True 
29 2 True 
31 1 True 
37 1 True 
41 1 True 
43 1 True 
47 1 True 
53 1 True 

59
138683118545689835737939019720389406345902876772687432540821294940160000000000
000
{2: 54, 3: 27, 5: 13, 7: 9, 11: 5, 13: 4, 17: 3, 19: 3, 23: 2, 29: 2, 31: 1, 3
7: 1, 41: 1, 43: 1, 47: 1, 53: 1, 59: 1}
2 54 True 
3 27 True 
5 13 True 
7 9 True 
11 5 True 
13 4 True 
17 3 True 
19 3 True 
23 2 True 
29 2 True 
31 1 True 
37 1 True 
41 1 True 
43 1 True 
47 1 True 
53 1 True 
59 1 True 

$