Python kann von Haus aus mit großen Ganzzahlen (die mehr als 64-Bit haben) umgehen.
x = 900000000000000000000000000010000000000000000000000001
y = 99985555444433332222111199988866665554444333322221111
x*y
89986999899989998999900079990979854553444233312220111999874222099977775555333411098866665554444333322221111
x % y
130001000100010000999200110200010010001000100010002
Das Submodul sympy.ntheory (engl. "number theory") beinhaltet zahlentheoretiche Funktionen.
from sympy.ntheory import isprime, nextprime
isprime(20150407)
False
nextprime(20150407)
20150411
Struktur der Primzahlen bis 2000:
from __future__ import print_function
zeilen, spalten = 25, 80
for z in range(zeilen):
for s in range(spalten):
n = (s + 1) + spalten * (z)
print("o" if isprime(n) else " ", end="")
print()
oo o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o
Das Ergebnis ist ein dict
, wobei die Schlüssel die Primzahlen und die Werte die Vielfachheit sind.
from sympy.ntheory import factorint
factorint(1116130609622197)
{13: 1, 1051: 1, 4339: 3}
fc2 = factorint(1116130609622197)
fc2
{13: 1, 1051: 1, 4339: 3}
Check
z = 1
for primzahl, vielfachheit in fc2.items():
z *= primzahl**vielfachheit
z
1116130609622197
from sympy.ntheory.modular import crt
crt([2, 3, 13], [1, 2, 7])
(59, 78)
[59 % m for m in [2, 3, 13]]
[1, 2, 7]
from sympy.ntheory import npartitions
for i in range(0, 2001, 100):
np = npartitions(i)
print("P(%5d) = %d" % (i, np))
P( 0) = 1 P( 100) = 190569292 P( 200) = 3972999029388 P( 300) = 9253082936723602 P( 400) = 6727090051741041926 P( 500) = 2300165032574323995027 P( 600) = 458004788008144308553622 P( 700) = 60378285202834474611028659 P( 800) = 5733052172321422504456911979 P( 900) = 415873681190459054784114365430 P( 1000) = 24061467864032622473692149727991 P( 1100) = 1147240591519695580043346988281283 P( 1200) = 46240102378152881298913555099661657 P( 1300) = 1607818855017534550841511230454411672 P( 1400) = 49032194652550394774839040691532998261 P( 1500) = 1329461690763193888825263136701886891117 P( 1600) = 32417690376154241824102577250721959572183 P( 1700) = 717802041964941442478681516751205185010007 P( 1800) = 14552716211005418005132948684850541312590849 P( 1900) = 272089289788583262011466359201428623427767364 P( 2000) = 4720819175619413888601432406799959512200344166
from sympy.ntheory.residue_ntheory import legendre_symbol
legendre_symbol(49, 997)
1
legendre_symbol(7, 997)
-1
from sympy.ntheory import mobius
mobius(11111222227777)
1
factorint(11111222227777)
{7: 1, 19: 1, 23: 1, 103: 1, 1753: 1, 20117: 1}
mobius(11111222227779)
0
factorint(11111222227779)
{3: 6, 167: 1, 91267853: 1}
Welche Punkte in $\mathbb{F}_7 \times \mathbb{F}_7$ liegen am Einheitskreis, also erfüllen $x^2 + y^2 = 1$?
from itertools import product
F7 = range(7)
for x, y in product(F7, F7):
if (x**2 + y**2) % 7 == 1:
print("%d:%d" % (x, y))
0:1 0:6 1:0 2:2 2:5 5:2 5:5 6:0
Bemerkung: Das ist natürlich nicht wirklich $\mathbb{F}_7$, denn wir brauchen die Modulo-Operation. Eine gute Aufgabe wäre, eine Klasse für $\mathbb{F}_p$ zu implementieren, dessen Elemente (also, man braucht auch eine Klasse für die Elemente) die Basisoperationen beherrschen.