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

学習環境

Surface 3 (4G LTE)、Surface 3 タイプカバー、Surface ペン(端末)
Windows 10 Pro (OS)
Nebo(Windows アプリ)
iPad Pro + Apple Pencil
MyScript Nebo(iPad アプリ)
参考書籍

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

1から n までの整数で、

$p^{i} (i = 1, 2, \dots)$

で割り切れて、

$p^{i + 1}$

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

$n_{i}$

とおく。

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

$\begin{array}{l} n_{1} + 2 n_{2} + 3 n_{3} + \dots \\ = (n_{1} + n_{2} + n_{3} + \dots) + (n_{2} + n_{3} + \dots) + (n_{4} + \dots) \end{array}$

ここで、

$n_{1} + n_{2} + n_{3} + \dots$

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

$n_{2} + n_{3} + \dots$

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

$n_{3} + \dots$

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

同様に、

$n_{s} + n_{s + 1} + \dots$

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

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

$\begin{array}{l} (n_{1} + n_{2} + \dots) + (n_{2} + n_{3} + \dots) + (n_{4} + n_{5} + \dots) + \dots \\ = [\frac{n}{p}] + [\frac{n}{p^{2}}] + [\frac{n}{p^{3}}] + \dots \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 

$

Kamimura's blog

2017年12月22日金曜日

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

0 コメント:

コメントを投稿