DSPython  00.03.03 — 25 juin 2012
 Tout Classes Espaces de nommage Fichiers Fonctions Variables Pages
Fonctions | Variables
Référence de l'espace de nommage DSPython.factors

Facteurs premiers. Plus de détails...

Fonctions

def bef
 Pour s = (… (Pi, ei) …) où Pi est le ie nombre premier renvoie ∑i ei.2i - 1.
def coprime_is
 s et t sont premiers entre eux ?
def distance_dominici
 Distance de Dominici à partir des primaries.
def divisors_nb
 Nombre des diviseurs à partir des primaries (fonction ν)
def divisors_prod
 Produit des diviseurs à partir des primaries (fonction ϖ)
def divisors_sum
 Somme des diviseurs à partir des primaries (fonction σ)
def divisors_sum_even
 Somme des diviseurs pairs à partir des primaries.
def divisors_sum_odd
 Somme des diviseurs impairs à partir des primaries.
def divisors_sum_pow
 Somme des diviseurs à partir des primaries (fonction σk)
def feb_primaries
 Pour n = ∑i=0 bi.2i renvoie les primaries de ∏i=1 Pibi-1 où Pi est le ie nombre premier.
def gcd
 PGCD de s et t (Plus Grand Commun Diviseur/ Greatest Common Divisor)
def godelnumber
 Renvoie le "nombre de Gödel" de la séquence s : pour s == (a1, a2, a3, ….., ak), renvoie ∏i=1k Piai .
def godelnumber_to_list
  Pour n == ∏i=1k Piai, renvoie [a1, a2, a3, ….., ak]
def lcm
 PPCM de s et t (Plus Petit Commun Multiple/ Least Common Multiple)
def mobius
 Fonction de Möbius à partir des primaries (fonction μ)
def mul
 Produit de s et t.
def nb_in_integers_4sqr
 Nombre de décompositions (en tenant compte de l'ordre) en somme de 4 carrés d'entiers (fonction GR)
def nfp
 Produit des facteurs non communs de s et t (Not common Factors Product)
def nontotient
 Nontotient à partir des primaries.
def ope_exp
  Pour s = ((p1, α1), (p2, α2), (p3, α3), …, (pk, αk)) et t = ((q1, β1), (q2, β2), (q3, β3), …, (ql, βl)),
renvoie [(r1, γ1), (r2, γ2), (r3, γ3), …, (rm, γm)]
tel que pour les pi = qj on ai rn = pi et γn = f(αi, βj).
Pour les pi ≠ qj on prend αi = 0 ou βj = 0. On s'arrête dès il n'y a plus de primary.
def primaries
 Liste des primaries de n,
c.-à-d. [(p1, α1), (p2, α2), (p3, α3), …, (pk, αk)] tel que n = ∏i=1k piαi avec pi premier, pi < pi + 1 et αi ≥ 1 .
def primaries_is
 Renvoie True si p est une séquence strictement ordonnée de primaries, False sinon.
def primaries_prime_is
 Renvoie True si s représente un nombre premier, False sinon.
def primaries_str
 String représentant les primaries.
def primaries_to_n
 Produit des primaries.
def primaries_to_primes
 Liste des primes à partir des primaries.
def primes
 Liste des primes de n.
def primes_is
 Renvoie True si p est une séquence ordonnée de primes, False sinon.
def primes_str
 String représentant les primes.
def primes_to_n
 Produit des primes.
def primes_to_primaries
 Liste des primaries à partir des primes.
def properdivisors_sum
 Somme des diviseurs à partir des primaries (fonction s)
def rad
 Produit des facteurs premiers distincts à partir des primaries (fonction radical)
def squarefree_is
 Renvoie True si p représente un nombre sans carré, False sinon.
def totient
 Totient à partir des primaries.

Variables

string VERSION = 'factors --- 2010 April 12'
 Date du dernier changement pour ce module.

Description détaillée

Facteurs premiers.


Documentation des fonctions

def DSPython.factors.bef (   s)

Pour s = (… (Pi, ei) …) où Pi est le ie nombre premier renvoie ∑i ei.2i - 1.

Pour s = [... (P_i, e_i) ...] où P_i est le ième nombre premier
renvoie Sum_i e_i * 2**(i - 1)
[OEIS A048675] (Binary Encoding of Factorizations)

Pre: s: séquence strictement ordonnée de primaries

Result: natural

O(s) = ...

Définition à la ligne 31 du fichier factors.py.

Références DSPython.factors.primaries_is().

Référencé par DSPython.factors.totient().

def DSPython.factors.coprime_is (   s,
  t 
)

s et t sont premiers entre eux ?

Renvoie True si s et t sont premiers entre eux,
  False sinon

Pre: s: séquence strictement ordonnée de primaries
     t: séquence strictement ordonnée de primaries

Result: boolean

O(s, t) = ...

Définition à la ligne 53 du fichier factors.py.

Références DSPython.factors.gcd(), et DSPython.factors.primaries_is().

Référencé par DSPython.factors.totient().

def DSPython.factors.distance_dominici (   s,
  t 
)

Distance de Dominici à partir des primaries.

(cf. An Arithmetic Metric, Diego Dominici, http://arxiv.org/abs/0906.0632/)

Renvoie la distance de Dominici entre les naturels
  ayant s et t pour liste de leurs primaries

Pre: s: séquence strictement ordonnée de primaries
     t: séquence strictement ordonnée de primaries

Result: naturel
O(s) = ...

Définition à la ligne 75 du fichier factors.py.

Références DSPython.factors.gcd(), DSPython.factors.lcm(), et DSPython.factors.primaries_is().

Référencé par DSPython.factors.totient().

def DSPython.factors.divisors_nb (   s)

Nombre des diviseurs à partir des primaries (fonction ν)

Renvoie le nombre des diviseurs du naturel
  ayant s pour liste des primaries
  == divisors_sum_pow(s, 0)

Pre: s: séquence strictement ordonnée de primaries

Result: naturel >= 1

O(s) = ...

Définition à la ligne 96 du fichier factors.py.

Références DSPython.factors.primaries_is().

Référencé par DSPython.factors.divisors_prod(), DSPython.factors.divisors_sum_pow(), et DSPython.factors.totient().

def DSPython.factors.divisors_prod (   s)

Produit des diviseurs à partir des primaries (fonction ϖ)

Renvoie le produit des diviseurs du naturel
  ayant s pour liste des primaries

Pre: s: séquence strictement ordonnée de primaries

Result: naturel >= 1

O(s) = ...

Définition à la ligne 115 du fichier factors.py.

Références DSPython.factors.divisors_nb(), DSPython.factors.primaries_is(), et DSPython.factors.primaries_to_n().

Référencé par DSPython.factors.totient().

def DSPython.factors.divisors_sum (   s)

Somme des diviseurs à partir des primaries (fonction σ)

Renvoie la somme des diviseurs du naturel
  ayant s pour liste des primaries
  == divisors_sum_pow(s, 1)

Pre: s: séquence strictement ordonnée de primaries

Result: naturel >= 1

O(s) = ...

Définition à la ligne 139 du fichier factors.py.

Références DSPython.factors.divisors_sum_odd(), et DSPython.factors.primaries_is().

Référencé par DSPython.factors.divisors_sum_pow(), et DSPython.factors.totient().

def DSPython.factors.divisors_sum_even (   s)

Somme des diviseurs pairs à partir des primaries.

Renvoie la somme des diviseurs pairs du naturel
  ayant s pour liste des primaries

Pre: s: séquence strictement ordonnée de primaries

Result: naturel >= 1

O(s) = ...

Définition à la ligne 157 du fichier factors.py.

Références DSPython.factors.primaries_is().

Référencé par DSPython.factors.totient().

def DSPython.factors.divisors_sum_odd (   s)

Somme des diviseurs impairs à partir des primaries.

Renvoie la somme des diviseurs pairs du naturel
  ayant s pour liste des primaries

Pre: s: séquence strictement ordonnée de primaries

Result: naturel >= 1

O(s) = ...

Définition à la ligne 178 du fichier factors.py.

Références DSPython.factors.primaries_is().

Référencé par DSPython.factors.divisors_sum(), DSPython.factors.nb_in_integers_4sqr(), et DSPython.factors.totient().

def DSPython.factors.divisors_sum_pow (   s,
  k 
)

Somme des diviseurs à partir des primaries (fonction σk)

Renvoie la somme des diviseurs ** k du naturel
  ayant s pour liste des primaries

Pre: s: séquence strictement ordonnée de primaries
     k: naturel

Result: naturel >= 1

O(s) = ...

Définition à la ligne 200 du fichier factors.py.

Références DSPython.factors.divisors_nb(), DSPython.factors.divisors_sum(), DSPython.natural_is(), et DSPython.factors.primaries_is().

Référencé par DSPython.factors.totient().

def DSPython.factors.feb_primaries (   n)

Pour n = ∑i=0 bi.2i renvoie les primaries de ∏i=1 Pibi-1 où Pi est le ie nombre premier.

Pour n = Sum_(i=0)^infini b_i * 2**i
renvoie les primaries de Prod_(i=1)^infini P_i**(b_(i-1))
où P_i est le ième nombre premier
[OEIS A019565]
bef(feb_primaries(n)) == n

Pre: n: natural

Result: séquence strictement ordonnée de primaries (naturel premier, 1)

O(n) = ...

Définition à la ligne 230 du fichier factors.py.

Références DSPython.natural_is().

Référencé par DSPython.factors.totient().

def DSPython.factors.gcd (   s,
  t 
)

PGCD de s et t (Plus Grand Commun Diviseur/ Greatest Common Divisor)

Renvoie le PGCD de s et t
  (Plus Grand Commun Diviseur/ Greatest Common Divisor)

Pre: s: séquence strictement ordonnée de primaries
     t: séquence strictement ordonnée de primaries

Result: séquence strictement ordonnée de primaries

O(s, t) = ...

Définition à la ligne 257 du fichier factors.py.

Références DSPython.factors.primaries_is().

Référencé par DSPython.factors.coprime_is(), DSPython.factors.distance_dominici(), et DSPython.factors.totient().

def DSPython.factors.godelnumber (   s)

Renvoie le "nombre de Gödel" de la séquence s : pour s == (a1, a2, a3, ….., ak), renvoie ∏i=1k Piai .

Renvoie le "nombre de Gödel" de la séquence s
Pour s == (a_1, a_2, a_3, ..., a_k), renvoie prod_i=1^k (P_i)^(a_i)
où P_i est le ième nombre premier

Pre: s: séquence de naturels

Result: naturel >= 1

O() = ...

Définition à la ligne 298 du fichier factors.py.

Références DSPython.natural_is().

Référencé par DSPython.factors.totient().

def DSPython.factors.godelnumber_to_list (   n)

Pour n == ∏i=1k Piai, renvoie [a1, a2, a3, ….., ak]

Pour n == prod_i=1^k (P_i)^(a_i) renvoie [a_1, a_2, a_3, ..., a_k]
Si n == 1 alors renvoie []

Pre: n: naturel >= 1

Result: [] ou list de naturels dont le dernier élément est != 0

O() = ...

Définition à la ligne 325 du fichier factors.py.

Références DSPython.numbernone.divmod(), et DSPython.natural_is().

Référencé par DSPython.factors.totient().

def DSPython.factors.lcm (   s,
  t 
)

PPCM de s et t (Plus Petit Commun Multiple/ Least Common Multiple)

Renvoie PPCM de s et t
  (Plus Petit Commun Multiple/ Least Common Multiple)

Pre: s: séquence strictement ordonnée de primaries
     t: séquence strictement ordonnée de primaries

Result: séquence strictement ordonnée de primaries

O(s, t) = ...

Définition à la ligne 357 du fichier factors.py.

Références DSPython.factors.primaries_is().

Référencé par DSPython.factors.distance_dominici(), et DSPython.factors.totient().

def DSPython.factors.mobius (   s)

Fonction de Möbius à partir des primaries (fonction μ)

Renvoie la fonction de Möbius du naturel
  ayant s pour liste des primaries

Pre: s: séquence strictement ordonnée de primaries

Result: -1, 0 ou 1

O(s) = ...

Définition à la ligne 396 du fichier factors.py.

Références DSPython.factors.primaries_is().

Référencé par DSPython.factors.totient().

def DSPython.factors.mul (   s,
  t 
)

Produit de s et t.

Renvoie le produit s et t

Pre: s: séquence strictement ordonnée de primaries
     t: séquence strictement ordonnée de primaries

Result: séquence strictement ordonnée de primaries

O(s, t) = ...

Définition à la ligne 417 du fichier factors.py.

Références DSPython.factors.primaries_is().

Référencé par DSPython.factors.totient().

def DSPython.factors.nb_in_integers_4sqr (   s)

Nombre de décompositions (en tenant compte de l'ordre) en somme de 4 carrés d'entiers (fonction GR)

Renvoie le nombre de décompositions (en tenant compte de l'ordre)
  en somme de 4 carrés d'entiers du naturel
  ayant s pour liste des primaries

Pre: s: séquence strictement ordonnée de primaries

Result: naturel multiple de 8

O(s) = ...

Définition à la ligne 460 du fichier factors.py.

Références DSPython.factors.divisors_sum_odd(), et DSPython.factors.primaries_is().

Référencé par DSPython.factors.totient().

def DSPython.factors.nfp (   s,
  t 
)

Produit des facteurs non communs de s et t (Not common Factors Product)

Renvoie le produit des facteurs non communs de s et t
  (Not common Factors Product)

Pre: s: séquence strictement ordonnée de primaries
     t: séquence strictement ordonnée de primaries

Result: séquence strictement ordonnée de primaries

O(s, t) = ...

Définition à la ligne 477 du fichier factors.py.

Références DSPython.factors.primaries_is().

Référencé par DSPython.factors.totient().

def DSPython.factors.nontotient (   s)

Nontotient à partir des primaries.

Renvoie le nombre de nontotatives du naturel
  ayant s pour liste des primaries
  (Si s == [] alors renvoie 0)

Pre: s: séquence strictement ordonnée de primaries

Result: naturel

O(n) = ...

Définition à la ligne 523 du fichier factors.py.

Références DSPython.factors.primaries_is(), DSPython.factors.primaries_to_n(), et DSPython.factors.totient().

Référencé par DSPython.factors.totient().

def DSPython.factors.ope_exp (   s,
  t,
  f 
)

Pour s = ((p1, α1), (p2, α2), (p3, α3), …, (pk, αk)) et t = ((q1, β1), (q2, β2), (q3, β3), …, (ql, βl)),
renvoie [(r1, γ1), (r2, γ2), (r3, γ3), …, (rm, γm)]
tel que pour les pi = qj on ai rn = pi et γn = f(αi, βj).
Pour les pi ≠ qj on prend αi = 0 ou βj = 0. On s'arrête dès il n'y a plus de primary.

Renvoie []

Pre: s: séquence strictement ordonnée de primaries
     t: séquence strictement ordonnée de primaries
     f: fonction : (naturel >= 1, naturel >= 1) -> naturel

Result: séquence strictement ordonnée de primaries

O(s, t) = ...

Définition à la ligne 553 du fichier factors.py.

Références DSPython.factors.primaries_is().

Référencé par DSPython.factors.totient().

def DSPython.factors.primaries (   n)

Liste des primaries de n,
c.-à-d. [(p1, α1), (p2, α2), (p3, α3), …, (pk, αk)] tel que n = ∏i=1k piαi avec pi premier, pi < pi + 1 et αi ≥ 1 .

Renvoie la liste des primaries (dans l'ordre strictement croissant) de n
  c.-à-d. les couples (facteur premier, exposant) décomposant n
  (Si n == 1 alors renvoie []).
Le nombre de primaries (la longueur de la liste renvoyée) correspond
  au nombre de facteurs premiers distincts de n
  (fonction omega)

Pre: n: naturel >= 1

Result: séquence strictement ordonnée (sur le premier élément) de couples
          (naturel premier, naturel >= 1)

O(n) = ...

Définition à la ligne 612 du fichier factors.py.

Références DSPython.numbernone.divmod(), et DSPython.natural_is().

Référencé par DSPython.factors.totient().

def DSPython.factors.primaries_is (   s)
def DSPython.factors.primaries_prime_is (   s)

Renvoie True si s représente un nombre premier, False sinon.

Renvoie True si s représente un nombre premier, False sinon

Pre: s: séquence strictement ordonnée de primaries

Result: boolean

Définition à la ligne 695 du fichier factors.py.

Références DSPython.factors.primaries_is().

Référencé par DSPython.factors.totient().

def DSPython.factors.primaries_str (   s,
  times = '.',
  exp = '^' 
)

String représentant les primaries.

Renvoie un string représentant les primaries
  (Si s est vide alors renvoie '1')

Pre: s: séquence strictement ordonnée de primaries
     times: string représentant l'opérateur de multiplication
     exp: string représentant l'opérateur d'exponentiation

Result: string

O(s) = ...

Définition à la ligne 707 du fichier factors.py.

Références DSPython.factors.primaries_is().

Référencé par DSPython.factors.totient().

def DSPython.factors.primaries_to_n (   s)

Produit des primaries.

Renvoie le naturel ayant s pour liste des primaries
  (Si s est vide alors renvoie 1)

Pre: s: séquence strictement ordonnée de primaries

Result: naturel >= 1

O(s) = ...

Définition à la ligne 731 du fichier factors.py.

Références DSPython.factors.primaries_is().

Référencé par DSPython.factors.divisors_prod(), DSPython.factors.nontotient(), et DSPython.factors.totient().

def DSPython.factors.primaries_to_primes (   s)

Liste des primes à partir des primaries.

Renvoie la liste des primes à partir de la liste des primaries
  (Si s est vide alors renvoie [])

Pre: s: séquence strictement ordonnée de primaries

Result: séquence ordonnée de primes

O(s) = ...

Définition à la ligne 749 du fichier factors.py.

Références DSPython.factors.primaries_is().

Référencé par DSPython.factors.totient().

def DSPython.factors.primes (   n)

Liste des primes de n.

Renvoie la liste des primes (dans l'ordre croissant) de n
  c.-à-d. les facteurs premiers de n
  (Si n == 1 alors renvoie []).
Le nombre de primes (la longueur de la liste renvoyée) correspond
  au nombre de facteurs premiers (non nécessairement distincts) de n
  (fonction Omega)

Pre: n: naturel >= 1

Result: séquence ordonnée de naturels premiers

O(n) = ...

Définition à la ligne 767 du fichier factors.py.

Références DSPython.numbernone.divmod(), et DSPython.natural_is().

Référencé par DSPython.factors.totient().

def DSPython.factors.primes_is (   s)

Renvoie True si p est une séquence ordonnée de primes, False sinon.

Renvoie True si p est une séquence ordonnée de primes,
False sinon

Pre: s: quelconque

Result: boolean

Définition à la ligne 823 du fichier factors.py.

Références DSPython.natural_is().

Référencé par DSPython.factors.primes_str(), DSPython.factors.primes_to_n(), DSPython.factors.primes_to_primaries(), et DSPython.factors.totient().

def DSPython.factors.primes_str (   s,
  times = '.' 
)

String représentant les primes.

Renvoie un string représentant les primes
  (Si s est vide alors renvoie '1')

Pre: s: séquence ordonnée de primes
     times: string représentant l'opérateur de multiplication

Result: string

O(s) = ...

Définition à la ligne 842 du fichier factors.py.

Références DSPython.factors.primes_is().

Référencé par DSPython.factors.totient().

def DSPython.factors.primes_to_n (   s)

Produit des primes.

Renvoie le naturel ayant s pour liste des primes
  (Si s est vide alors renvoie 1)

Pre: s: séquence ordonnée de primes

Result: naturel >= 1

O(s) = ...

Définition à la ligne 864 du fichier factors.py.

Références DSPython.factors.primes_is().

Référencé par DSPython.factors.totient().

def DSPython.factors.primes_to_primaries (   s)

Liste des primaries à partir des primes.

Renvoie la liste des primaries à partir de la liste des primes
  (Si s est vide alors renvoie [])

Pre: s: séquence ordonnée de primes

Result: séquence strictement ordonnée de primaries

O(s) = ...

Définition à la ligne 882 du fichier factors.py.

Références DSPython.factors.primes_is().

Référencé par DSPython.factors.totient().

def DSPython.factors.properdivisors_sum (   s)

Somme des diviseurs à partir des primaries (fonction s)

Renvoie la somme des diviseurs propres du naturel
  ayant s pour liste des primaries
  == divisors_sum(s) - primaries_to_n(s)

Pre: s: séquence strictement ordonnée de primaries

Result: naturel >= 1

O(s) = ...

Définition à la ligne 912 du fichier factors.py.

Références DSPython.factors.primaries_is().

Référencé par DSPython.factors.totient().

def DSPython.factors.rad (   s)

Produit des facteurs premiers distincts à partir des primaries (fonction radical)

Pour s = [... (P_i, e_i) ...] où P_i est le ième nombre premier
renvoie [... (P_i, 1) ...]
Renvoie le produit des facteurs premiers distincts
  du naturel ayant s pour liste des primaries
[OEIS A007947] Largest square-free number dividing n (the square-free kernel of n)

Pre: s: séquence strictement ordonnée de primaries

Result: séquence strictement ordonnée de primaries (naturel premier, 1)

O(s) = ...

Définition à la ligne 934 du fichier factors.py.

Références DSPython.factors.primaries_is().

Référencé par DSPython.factors.totient().

def DSPython.factors.squarefree_is (   s)

Renvoie True si p représente un nombre sans carré, False sinon.

Renvoie True si p représente un nombre sans carré [OEIS A005117],
False sinon

Pre: s: séquence strictement ordonnée de primaries

Result: boolean

Définition à la ligne 955 du fichier factors.py.

Références DSPython.factors.primaries_is().

Référencé par DSPython.factors.totient().

def DSPython.factors.totient (   s)