<a href="https://colab.research.google.com/github/kalz2q/mycolabnotebooks/blob/master/sympy_ntheory.ipynb" target="_parent"></a>


```python

```



# sympy.ntheory に脇道


https://docs.sympy.org/latest/modules/ntheory.html#module-sympy.ntheory.modular


```python
# エラトステネスの篩
from sympy import sieve
sieve._reset()
display(25 in sieve) # 25 は素数表 sieve にあるか => False
display(sieve) # 単純な素数表ではないのだ!!!!
display(type(sieve))
display(type(sieve._list))
display(sieve._list)
display(sieve[3])
display([i for i in sieve._list])
```


    False



    <prime sieve (9): 2, 3, 5, ... 19, 23
    totient sieve (6): 0, 1, 1, ... 2, 4
    mobius sieve (6): 0, 1, -1, ... 0, -1>



    sympy.ntheory.generate.Sieve



    array.array



    array('l', [2, 3, 5, 7, 11, 13, 17, 19, 23])



    5



    [2, 3, 5, 7, 11, 13, 17, 19, 23]



```python
# same as 30 in sieve without return
from sympy import sieve
sieve._reset()
sieve.extend(30)
display(sieve[3]==5)
display(sieve._list)
```


    True



    array('l', [2, 3, 5, 7, 11, 13, 17, 19, 23, 29])



```python
# nth prime
from sympy import sieve, prime
sieve._reset()
n=20
sieve.extend_to_no(n)
display(sieve[n])
display(prime(n))
display(sieve._list)
```


    71



    71



    array('l', [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89])



```python
# isprime
from sympy import sieve,prime,isprime
sieve._reset()
display(isprime(1299709))
display(sieve._list)
display(sieve[10])
display(sieve._list)
```


    True



    array('l', [2, 3, 5, 7, 11, 13])



    29



    array('l', [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31])



```python
# mobiusrange(a,b) # b is outside of range
# 下の例では 7,8,9,10,11,12,13,14,15,16,17 についてメビウス関数の値を示す
# メビウス関数は素因数分解して中に平方を含んでいれば 0 => 8,9,12,16
# 因子が奇数個の場合は -1 => 7,11,13,17
# 因子が偶数個の場合は 1 => 10,14,15
# 従って素数とは関係ない
from sympy import sieve
print([i for i in sieve.mobiusrange(7, 18)])

```

    [-1, 0, 0, 1, -1, 0, -1, 1, 1, 0, -1]



```python
# primerange
from sympy import sieve
print([i for i in sieve.primerange(7, 18)])
```

    [7, 11, 13, 17]



```python
# primerange と同じものを書いてみる
from sympy import sieve
n=30
sieve.extend_to_no(n)
display([i for i in sieve._list if (i >= 7) & (i < 18)])
```


    [7, 11, 13, 17]



```python
# search 与えられた値の上下の素数を tuple で返す
from sympy import sieve
n = 8
display(sieve.search(n))
a, b = sieve.search(n)
display(sieve[a], sieve[b])
```


    (4, 5)



    7



    11


totient

オイラーのトーシェント関数とは、正の整数 $n$ に対して、 $n$ と互いに素である 1 以上 $n$ 以下の自然数の個数 $\varphi (n)$ を与える数論的関数 $\varphi$ である



```python
# totientrange range について totient 数を返す
# 素数の場合 n-1 個になる
from sympy import sieve
print([i for i in sieve.totientrange(7, 18)])
```

    [6, 4, 6, 4, 10, 4, 12, 6, 8, 8, 16]



```python
# nth prime n番目の素数
from sympy import prime
display(prime(10))
display(prime(1))
display(prime(100000))

```


    29



    31



    1299709



```python
#primepi n を含み n より小さい素数の数 primepi(10) => 2,3,5,7 => 4 個
from sympy import *
n = 10
primepi(n)
```




$\displaystyle 4$




```python
# 対数積分 logarithmic integral function オイラーの対数積分
from sympy import *
n = 10
print(li(n))
li(n).evalf()
```

    li(10)





$\displaystyle 6.1655995047873$




```python
# nextprime
from sympy import nextprime
[(i,nextprime(i)) for i in range (10,15)]
```




    [(10, 11), (11, 13), (12, 13), (13, 17), (14, 17)]




```python
# prevprime
from sympy import prevprime
[(i,prevprime(i)) for i in range (10,15)]
```




    [(10, 7), (11, 7), (12, 11), (13, 11), (14, 13)]




```python
# primerange, sieve
from sympy import primerange, sieve
print([i for i in primerange(1,30)])
print([i for i in sieve.primerange(1,30)])
print(list(sieve.primerange(1,30)))

```

    [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
    [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
    [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]



```python
# randprime, isprime
from sympy import randprime, isprime
print(randprime(1,30))
print(isprime(randprime(1,30)))
```

    17
    True



```python
from sympy.ntheory.generate import primorial, primerange
from sympy import factorint, Mul, primefactors, sqrt
print(primorial(4)) # the first 4 primes are 2, 3, 5, 7
print(primorial(4, nth=False)) # primes <= 4 are 2 and 3
print(primorial(1))
print(primorial(1, nth=False))
print(sqrt(101).evalf())
print(primorial(sqrt(101), nth=False))
print(factorint(primorial(4) + 1))
print(factorint(210))
print(factorint(primorial(4) - 1))
p = list(primerange(10, 20)) # generate all primes in a given range
print(p)
print(sorted(set(primefactors(Mul(*p) + 1)).difference(set(p))))

```

    210
    6
    2
    1
    10.0498756211209
    210
    {211: 1}
    {2: 1, 3: 1, 5: 1, 7: 1}
    {11: 1, 19: 1}
    [11, 13, 17, 19]
    [2, 5, 31, 149]



```python
from sympy.ntheory.generate import cycle_length
func = lambda i: (i**2 + 1) % 51
print(next(cycle_length(func, 4)))
n = cycle_length(func, 4, values=True)
print(list(ni for ni in n))
print(next(cycle_length(func,4,nmax=4)))
print([ni for ni in cycle_length(func,4,nmax=4,values=True)])
```

    (6, 2)
    [17, 35, 2, 5, 26, 14, 44, 50, 2, 5, 26, 14]
    (4, None)
    [17, 35, 2, 5]



```python
from sympy import composite
print(composite(36))
print(composite(1))
print(composite(17737))

```

    52
    4
    20000



```python
from sympy import compositepi
print(compositepi(25))
print(compositepi(1))
print(compositepi(1000))
```

    15
    0
    831



```python
from sympy.ntheory.factor_  import smoothness
print(smoothness(2**7*3**2))
print(smoothness(2**4*13))
print(smoothness(2))
```

    (3, 128)
    (13, 16)
    (2, 2)



```python
from sympy.ntheory.factor_  import smoothness_p
print(smoothness_p(10431, m=1))
print(smoothness_p(10431))
print(smoothness_p(10431,power=1))
print(smoothness_p(21477639576571, visual=1))
```

    (1, [(3, (2, 2, 4)), (19, (1, 5, 5)), (61, (1, 31, 31))])
    (-1, [(3, (2, 2, 2)), (19, (1, 3, 9)), (61, (1, 5, 5))])
    (-1, [(3, (2, 2, 2)), (61, (1, 5, 5)), (19, (1, 3, 9))])
    p**i=4410317**1 has p-1 B=1787, B-pow=1787
    p**i=4869863**1 has p-1 B=2434931, B-pow=2434931



```python
print(factorint(17*9))
print(smoothness_p(factorint(17*9)))
print(smoothness_p(smoothness_p(factorint(17*9))))
```

    {3: 2, 17: 1}
    p**i=3**2 has p-1 B=2, B-pow=2
    p**i=17**1 has p-1 B=2, B-pow=16
    {3: 2, 17: 1}



```python
from sympy import trailing
print(trailing(128))
print(trailing(63))

```

    7
    0



```python
from sympy.ntheory import multiplicity
from sympy.core.numbers import Rational as R
print([multiplicity(5, n) for n in [8, 5, 25, 125, 250]])
print(multiplicity(3, R(1, 9)))

```

    [0, 1, 2, 3, 3]
    -2


https://docs.sympy.org/latest/modules/ntheory.html#module-sympy.ntheory.modular

73a34b2bf30bda824da8b26eb46b0e96b0b0e549
ipynb
Jupyter Notebook
sympy_ntheory.ipynb
kalz2q/-yjupyternotebooks
ba37ac7822543b830fe8602b3f611bb617943463
MIT
2021-09-16T03:45:19.000Z
2021-09-16T03:45:19.000Z
sympy_ntheory.ipynb
kalz2q/-yjupyternotebooks
ba37ac7822543b830fe8602b3f611bb617943463
MIT
sympy_ntheory.ipynb
kalz2q/-yjupyternotebooks
ba37ac7822543b830fe8602b3f611bb617943463
MIT
Qwen/Qwen-72B
1. YES
2. YES