[Python] Fonction indicatrice d'Euler

Charmander · 20-10-2013 17:23:29

Bonjour, je cherche de l'aide pour programmer sur Python la fonction indicatrice d'Euler. J'y arrive par la méthode naïve en testant tous les nombres inférieurs à n mais je souhaite obtenir un programme qui marche pour les grands nombres.
Il m'est indiqué d'ailleurs d'utiliser la relation:
[tex]\sum_{d|n}^{} φ(d)=n[/tex] avec la somme portant sur les diviseurs positifs de n.
Comment calculer facilement φ(n) à l'aide de cette relation ? Merci d'avance !

yoshi · 20-10-2013 20:01:09

Salut,

Je savais que j'avais vu ça quelque part :
http://algos.pirmil.info/?p=79
La solution récursive ne me plaît qu'à moitié, car entraînant des problèmes de pile dans certains cas...

Question subsidiaire : tu veux obtenir [tex]\phi(n)[/tex] pour [tex]n \leqslant\; ...[/tex] ?

@+

J'oublais :
l'implémentation du calcul du PGCD est inutile à partir des versions 2.6 :

>>> from fractions import gcd

>>> gcd(12345789145789,3524875457)

1L

>>>

>>> gcd(12745789545888,143155248754176)

288L

Charmander · 20-10-2013 21:42:32

Le problème c'est que la solution sur le site n'utilise pas la relation imposée, alors que j'écris le programme dans le cadre d'un devoir à rendre... Mais bon c'est pas grave, merci quand même ! ^^

yoshi · 21-10-2013 09:11:46

Bonjour,

La nuit portant conseil, j'ai trouvé... !
[tex]d|n[/tex] d divise n
Donc, soit D l'ensemble des diviseurs de n : [tex]D(n) = \{1,d_1,d_2...\}[/tex]
Et tu cherches à calculer [tex]\sum_i \phi(d_i)[/tex] et montrer que ça redonne n.
Avec n = 8, [tex]D(8)=\{1,2,4,8\}[/tex]
[tex]\phi(1)+\phi(2)+\phi(4)+\phi(8)=8[/tex] en calculant :
[tex]\phi(1)=1\;;\;\phi(2)=1\;;\;\phi(4)=2\;;\;\phi(8)=4[/tex]
D'où [tex]\phi(1)+\phi(2)+\phi(4)+\phi(8) = 1+1+2+4 = 8[/tex]
* d'une fonction diviseurs qui prenne en entrée un seul argument d et qui retourne la liste des diviseurs de d --> def diviseurs(d):
Ta limite sera sera la racine de 12.
Si d est un carré alors [tex]\sqrt d[/tex] sera un diviseur, sinon non.
Par ex avec 12. Tu démarres avec 1 et 12, puis tu testes 2. Si 2 diviseur, alors 12/2 aussi, on stocke donc 2 et 6.
On passe à 3. 3 divise 12, donc 12/3 = 4 aussi. On stocke 3 et 4...
On passe à 4. Là intervient le test d'arrêt : 4 est supérieur à [tex]\sqrt{12}[/tex]
La fonction retourne la liste D =[1,12,2,6,3,4]. Si tu retournes non pas D, mais sorted(D) tu récupères la liste triée [1,2,3,4,6,12]
* D'une fonction qui calcule l'indicatrice d'Euler proprement et qui prend en entrée l'argument [tex]d \in D(n)[/tex], ici chaque diviseur de [1,2,3,4,6,12] ---> def indicatrice(d):
Tu pourrais faire l'économie de 1 et 2. Il est connu que [tex]\phi(1)=1[/tex] et [tex]\phi(2)=1[/tex].
A partir d'un d donné dans cette fonction tu vas stocker la liste P des premiers avec d. Et tu retourneras len(P)

Dans ton programme principal, une boucle permet de calculer phi (initialisé à 1 si on économise la recherche de [tex]\phi(1)[/tex])
en appelant la fonction indicatrice autant de fois qu'il y a de diviseurs dans D (moins une fois si on ne teste pas 1)
Et à chaque retour tu sommes dans phi, dans s (ce que tu veux) la valeur retournée.

@+

yoshi · 21-10-2013 13:58:42

Bonjour,

Voilà,

J'ai écrit le programme agrémenté de quelques sorties intermédiaires.
Voilà ce que ça donne sur deux exemples :

IDLE 2.6.4      
>>>================================ RESTART ================================
>>>

Liste des diviseurs de 144 :

D(144)=[1,2,3,4,6,8,9,12,16,18,24,36,48,72,144]

phi(1)= 1

phi(2)= 1

phi(3)= 2

phi(4)= 2

phi(6)= 2

phi(8)= 4

phi(9)= 6

phi(12)= 4

phi(16)= 8

phi(18)= 6

phi(24)= 8

phi(36)= 12

phi(48)= 16

phi(72)= 24

phi(144)= 48

Somme de tous les phi(d|144)= 144

>>> ================================ RESTART ================================

>>> 

Liste des diviseurs de 420 :

D(420) = [1, 2, 3, 4, 5, 6, 7, 10, 12, 14, 15, 20, 21, 28, 30, 35, 42, 60, 70, 84, 105, 140, 210, 420]

phi(1)= 1

phi(2)= 1

phi(3)= 2

phi(4)= 2

phi(5)= 4

phi(6)= 2

phi(7)= 6

phi(10)= 4

phi(12)= 4

phi(14)= 6

phi(15)= 8

phi(20)= 8

phi(21)= 12

phi(28)= 12

phi(30)= 8

phi(35)= 24

phi(42)= 12

phi(60)= 16

phi(70)= 24

phi(84)= 24

phi(105)= 48

phi(140)= 48

phi(210)= 48

phi(420)= 96

Somme de tous les phi(d|420)= 420

>>>

C'est bien ce que tu attends ?
Je n'ai fait que mettre en application la méthode décrite au post précédent.
Soit en pseudocode :

import de racine carrée du module maths
import du pgcd depuis le module fractions

Définition fonction diviseurs(n)
initialiser lise des Diviseurs avec 1 et n
calcul partie entière de racine(n)
initialisation fin de boucle à racine+1
Pour i de 2 à findeboucle:
Si reste de division de n par d est nul
Stockage de d dans D
si d est différent de n//d
Stockage de n//d
Tri de D
return D

Définition fonction indicatrice(d)
Initialisation d'une liste de Premiers avec d vide
Initialisation d'une liste de nombres inférieurs ou égaux à d (en partant de 1)
Pour i dans la liste ci-dessus
si i est premier avec n (soit si gcd(i,n)==1)
Stockage de i dans ilste de Premiers
Retourne le nombre d'éléments de cette liste (le phi(d))

initialisation de n.
Affichage de n
Appel de Diviseurs de n avec recup dans une liste
initialisation de la somme des phi partiels à 0
Pour i dans D:
appel de indicatrice de d, avec incrémentation de phi par le résultat

Affichage du phi total final

Allez, lance-toi, écris les fonctions l'une après l'autre et assure-toi que chacune fonctionne.
Tu peux constater que j'ai deux fonctions séparées pas imbriquées.

Ce n'est pas parfait : je peux encore peaufiner, mais bon, c'est déjà suffisant pour ce qu'on te demande.
Je vais d'ailleurs le faire et appeler indicatrice depuis diviseurs pour chacun d'entre eux : ce serait mieux et probablement plus rapide.

@+

Dernière modification par yoshi (21-10-2013 14:46:49)

yoshi · 22-10-2013 13:01:24

Re,

Ça ne t'intéresse plus ?

@+

yoshi · 23-10-2013 17:01:06

Bonjour,

Je crois que je vois ce qu'on te demande réellement de faire avec cette relation
Prenons [tex]\phi(42)[/tex]...
D(42) = [1, 2, 3, 6, 7, 14, 21, 42]
[tex]\phi(1)+\phi(2)+\phi(3)+\phi(6)+\phi(7)+\phi(14)+\phi(21)+\phi(42)=42[/tex]
Donc:
[tex]\phi(42)=42-\phi(21)-\phi(14)-\phi(7)-\phi(6)-\phi(3)-\phi(2)-\phi(1)[/tex]
De la même façon :
---> [tex]\phi(21)=21-\phi(7)-\phi(3)-\phi(1)[/tex]
D'où :
[tex]\phi(42) = 42-21+\phi(7)+\phi(3)+\phi(1)-\phi(14)-\phi(7)-\phi(6)-\phi(3)-\phi(2)-\phi(1)[/tex]
[tex]\phi(42) = 42-21-\phi(14)-\phi(6)-\phi(2)[/tex]
On recommence :
--->[tex]ϕ(14)=14−ϕ(7)−ϕ(2)−ϕ(1)[/tex]
Maintenant :
[tex]\phi(42) = 42-21-14+ϕ(7)+ϕ(2)+ϕ(1)-\phi(6)-\phi(2)=42-21-14+\phi(7)-\phi(6)+\phi(1)[/tex]
--->[tex]\phi(7) = 7-\phi(1)[/tex]
Alors
[tex]\phi(42) = 42-21-14+7-\phi(1)-\phi(6)+\phi(1) = 42-21-14+7-\phi(6)[/tex]

---> [tex]\phi(6)=6-\phi(3)-\phi(2)-\phi(1)[/tex]
d'où :
[tex]\phi(42) = 42-21-14+7-\phi(6) = 42-21-14+7-6+\phi(3)+\phi(2)+\phi(1)[/tex]

Et enfin
[tex]\phi(42) = 42-21-14+7-\phi(6) = 42-21-14+7-6+3-\phi(1)+2-\phi(1)+\phi(1) = 42-21-14+7-6+3+2-1 = 12[/tex]
[tex]\phi(42) = 42-21-14+7-6+3+2-1 = 12[/tex]

Maintenant, il faut arriver à formelliser ça pour arriver directement à 42-21-14+7-6+3+2-1...

Yaka ! ^_^

@+

yoshi · 24-10-2013 15:33:56

Bonjour,

J'ai abandonné - provisoirement- cette idée mais cela m'a mis sur la voie, d'autant qu'il s'agit de programmation...
Un bref historique.
1. J'ai d'abord cru qu'il fallait vérifier la relation, alors, j'avais abouti à ce code :

#!/usr/bin/env python
# -*- coding: cp1252 -*-

from math import sqrt

from fractions import gcd

def diviseurs(n):

    D,racine=[1,n],int(sqrt(n))

    fin=racine+1

    for d in range(2,fin):

        if n%d==0 :

            D.extend([d,n//d])

    D=sorted(set(D))

    print "Liste des diviseurs de",n,":"

    print "D("+str(n)+") =",D

    print

    return D

def somme_indicatrices(n):

    D=diviseurs(n)

    S_phi=0

    for d in D:

        Nb_inf,p=range(1,d+1),0

        for i in Nb_inf:

            p+=(gcd(i,d)==1)

        print "phi("+str(i)+")=",p

        S_phi+=p

    print

    print "Somme de tous les phi(d|"+str(n)+")=", S_phi

    return

n=144

somme_indicatrices(n)

qui donne les copies de sortie des posts précédents

2. Puis en relisant, je me suis dit que j'allais calculer tous les [tex]\phi(d),\;d<n[/tex]

#!/usr/bin/env python
# -*- coding: cp1252 -*-

from math import sqrt

from fractions import gcd

def diviseurs(n):

    D,racine=[1],int(sqrt(n))

    fin=racine+1

    for d in range(2,fin):

        if n%d==0 :

            D.extend([d,n//d])

    D=sorted(set(D))

    print "Liste des diviseurs de",n,":"

    print "D("+str(n)+") =",D

    print

    return D

def somme_indicatrices(n):

    D=diviseurs(n)

    S_phi=0

    for d in D:

        Nb_inf,p=range(1,d+1),0

        for i in Nb_inf:

            p+=(gcd(i,d)==1)

        print "phi("+str(i)+")=",p

        S_phi+=p

    print

    print "Somme de tous les phi(d|"+str(n)+") -sauf", str(n)+"- =", S_phi

    print "                D'où"

    print "            phi("+str(n)+") =",n-S_phi

    return

n=144

somme_indicatrices(n)

Sortie pour n=144

Liste des diviseurs de 144 :
D(144) = [1, 2, 3, 4, 6, 8, 9, 12, 16, 18, 24, 36, 48, 72]
phi(1)= 1
phi(2)= 1
phi(3)= 2
phi(4)= 2
phi(6)= 2
phi(8)= 4
phi(9)= 6
phi(12)= 4
phi(16)= 8
phi(18)= 6
phi(24)= 8
phi(36)= 12
phi(48)= 16
phi(72)= 24
Somme de tous les phi(d|144) -sauf 144- = 96
D'où
phi(144) = 48

3. Puis, j'ai relu encore et la lumière est enfin venue.
Prenons n=144
J'établis la liste D des diviseurs inférieurs à 144...
Je crée alors une liste Phi de même longueur que la précédente, ne comprenant que des 0, sauf Phi[0] qui est à 1.
Phi[0]est l'indicatrice du 1er nombre de la liste des diviseurs D, soit 1 qui occupe la même position dans Phi que 1 dans D, la position 0.

Je reprends ensuite tous les diviseurs d de 144 un par un avec un traitement spécial pour d=1
Je cherche ensuite l'ensemble D_i des diviseurs du d précédent, d en moins.
Pour un diviseur div de D_i :
je cherche la somme q des [tex]\phi[/tex] antérieurs déjà calculés, j'obtiens \phi(i)=p par p = div-q.
Pour 2 : p = 2-q = 2 - 1 = 1, je stocke alors ce p dans la liste Phi...
Pour 3 : p = 2-q = 3 - 1 = 2, je stocke alors ce p dans la liste Phi...
Pour 4 : [tex]p = 4-\phi(2)-\phi(1) = 4-1-1 = 2[/tex], je stocke alors ce p dans la liste Phi...
Et je remonte de proche en proche jusqu'à obtenir et stocker [tex]\phi(72)[/tex] dans la liste Phi
Les valeurs de [tex]\phi(2)[/tex] et [tex]\phi(1)[/tex], se trouvent dans liste Phi aux indices 0 et 1...

Il faut impérativement procéder par ordre croissant.
C'est un premier jet si d'aventure notre ami, avare d'explications et de visites n(on doit être trop nuls pour lui), passait par lkà.
Maintenant, je vais me pencher sur la vitesse et la concision.

#!/usr/bin/env python
# -*- coding: cp1252 -*-

from math import sqrt

def diviseurs(n):

    D,racine=[1],int(sqrt(n))

    fin=racine+1

    for d in range(2,fin):

        if n%d==0 :

            D.extend([d,n//d])

    D=sorted(set(D))

    return D

print "           ******************************************************"

print "           *  Calcul de l'indicatrice d'Euler par différences  *"

print "           ******************************************************"

print

n=144

D=diviseurs(n)

Phi,somme=[1],"1"

for i,div in enumerate(D):

    print "Phi("+str(div)+") =",

    ch=str(div)

    if div==1:

        print"1"

    else:

        D_i,q=diviseurs(D[i]),0

        for d in D_i:

            q+=Phi[D.index(d)]

        ch+="-"+str(q)

        p=div-q

        Phi.append(p)

        somme+="+"+str(p)

        print str(div)+"-Somme des Phi des diviseurs<"+str(div)+" =",ch,"=",div-q

    ch=""

print

print "Somme :",somme,

print "=",sum(Phi)

print "          Phi("+str(n)+") =",str(n)+" - "+str(sum(Phi)),"=", n-sum(Phi)

Sortie pour n=144 :
*******************************************************
* Calcul de l'indicatrice d'Euler par différences *
*******************************************************
Phi(1) = 1
Phi(2) = 2-Somme des Phi des diviseurs<2 = 2-1 = 1
Phi(3) = 3-Somme des Phi des diviseurs<3 = 3-1 = 2
Phi(4) = 4-Somme des Phi des diviseurs<4 = 4-2 = 2
Phi(6) = 6-Somme des Phi des diviseurs<6 = 6-4 = 2
Phi(8) = 8-Somme des Phi des diviseurs<8 = 8-4 = 4
Phi(9) = 9-Somme des Phi des diviseurs<9 = 9-3 = 6
Phi(12) = 12-Somme des Phi des diviseurs<12 = 12-8 = 4
Phi(16) = 16-Somme des Phi des diviseurs<16 = 16-8 = 8
Phi(18) = 18-Somme des Phi des diviseurs<18 = 18-12 = 6
Phi(24) = 24-Somme des Phi des diviseurs<24 = 24-16 = 8
Phi(36) = 36-Somme des Phi des diviseurs<36 = 36-24 = 12
Phi(48) = 48-Somme des Phi des diviseurs<48 = 48-32 = 16
Phi(72) = 72-Somme des Phi des diviseurs<72 = 72-48 = 24
Somme : 1+1+2+2+2+4+6+4+8+6+8+12+16+24 = 96
Phi(144) = 144 - 96 = 48

Amha, je pense que si Charmander n'a pas eu d'autres explications que celles fournies, c'était mission impossible pour un débutant...

@+

Charmander · 24-10-2013 19:06:46

Bonjour,

Woauh, c'est compliqué tout ça ! Je crois que ça dépasse un peu ce qu'on me demande ^^'
Finalement, j'ai trouvé quelque chose qui utilise un peu près l'idée que t'as donné, en définissant la fonction par récursivité : tant que le diviseur d de n n'est pas égal à 1(auquel cas phi(1)=1), on réapplique la fonction sur d... Ca marche plus ou moins, la fonction peut calculer jusqu'à 10*8 sans grande difficulté :)

Merci quand même pour ton aide :)

yoshi · 24-10-2013 20:18:22

Salut,

on réapplique la fonction sur d.

Tu peux donner ton bout de code ?

Non, je n'ai rien fait de compliqué, j'ai au contraire essayé de rester basique et clair.
J'ai raffiné un peu...
J'ai notamment pensé qu'accéder à la fonction pour chercher les diviseurs d'un nombre div lui-même diviseur du n de départ était un gâchis.
J'ai donc établi la liste D_i des diviseurs en cherchant parmi la liste D globale des diviseurs de n (sauf n) : ils y sont forcément.
J'économise donc du temps de calcul...

Oh, certes, j'ai employé ce qu'on appelle une "list comprehension" :
[d for d in D if div%d==0 and d<div]
qui peut se traduire par liste des nombres d tels que d soit dans D, que d divise le diviseur div (di%d==0) et que d soit inférieur à div : c'est à dire la liste des diviseurs de div, présents dans D et inférieurs à div...

Peut-être for i,div in enumerate(D) te gêne-t-il ?
C'est le moyen le plus rapide de parcourir la liste des éléments d'un ensemble (ici D) en disposant à la fois de l'élément et de sa position dans D...

sum(liste) permet d'obtenir directement la somme des nombres composant une liste.

L'affichage te gêne ? On peut supprimer tous les print sauf les deux derniers et tous les "ch =" sans problème : j'ai utilisé des conversions en chaîne de caractères --> str() pour gagner de la place, étant donné qu'après print 2, (par exemple) la virgule génère un espace après...
On peut aussi virer toutes les références à la chaîne somme.
C'est moins démonstratif, mais tient moins de place à l'écran.

Pourquoi sqrt(n) ? je déduis l'autre moitié des diviseurs par division. Exemple [tex]\sqrt{144}=12[/tex]
Dès que je suis arrivé à 12, je m'arrête :
1, 2, 3, 4, 6, 8, 9, 12 et je déduis alors à chaque fois (144), 72, 48, 36, 24, 18, 16, 12
Comme je les stocke deux par deux, ici, j'ai un doublon set(D) m'élimine tous les doublons et comme j'ai besoin de l'ordre croissant, je trie la nouvelle liste, d'où le sorted(set(D))...

D.extend()... Pourquoi pas D.append() ?
append() rajoute un élément et un seul à la suite des autres, extend me permet d'ajouter la liste [d,D//d] en une seule instruction. Je devrais appliquer append() deux fois sinon.

#!/usr/bin/env python
# -*- coding: cp1252 -*-

from math import sqrt

def diviseurs(n):

    D,racine=[1],int(sqrt(n))

    fin=racine+1

    for d in range(2,fin):

        if n%d==0 :

            D.extend([d,n//d])

    D=sorted(set(D))

    return D

print "           *****************************************************"

print "           *  Calcul de l'indicatrice d'Euler par différences  *"

print "           *****************************************************"

print

n=144457825

D=diviseurs(n)

print "D("+str(n)+") =",D

print

Phi,somme=[1],"1"

for i,div in enumerate(D):

    print "Phi("+str(div)+") =",

    ch=str(div)

    if div==1:

        print"1"

    else:

        D_i,q=[d for d in D if div%d==0 and d<div],0

        for d in D_i:

            q+=Phi[D.index(d)]

        ch+="-"+str(q)

        p=div-q

        Phi.append(p)

        somme+="+"+str(p)

        print str(div)+"-Somme des Phi des diviseurs<"+str(div)+" =",ch,"=",div-q

    ch=""

print

print "Somme :",somme,

print "=",sum(Phi)

print "          Phi("+str(n)+") =",str(n)+" - "+str(sum(Phi)),"=", n-sum(Phi)

Sortie n°1
*****************************************************
* Calcul de l'indicatrice d'Euler par différences *
*****************************************************
D(144457825) = [1, 5, 23, 25, 115, 575, 251231, 1256155, 5778313, 6280775, 28891565]
Phi(1) = 1
Phi(5) = 5-Somme des Phi des diviseurs<5 = 5-1 = 4
Phi(23) = 23-Somme des Phi des diviseurs<23 = 23-1 = 22
Phi(25) = 25-Somme des Phi des diviseurs<25 = 25-5 = 20
Phi(115) = 115-Somme des Phi des diviseurs<115 = 115-27 = 88
Phi(575) = 575-Somme des Phi des diviseurs<575 = 575-135 = 440
Phi(251231) = 251231-Somme des Phi des diviseurs<251231 = 251231-1 = 251230
Phi(1256155) = 1256155-Somme des Phi des diviseurs<1256155 = 1256155-251235 = 1004920
Phi(5778313) = 5778313-Somme des Phi des diviseurs<5778313 = 5778313-251253 = 5527060
Phi(6280775) = 6280775-Somme des Phi des diviseurs<6280775 = 6280775-1256175 = 5024600
Phi(28891565) = 28891565-Somme des Phi des diviseurs<28891565 = 28891565-6783325 = 22108240
Somme : 1+4+22+20+88+440+251230+1004920+5527060+5024600+22108240 = 33916625
Phi(144457825) = 144457825 - 33916625 = 110541200

Je me suis dit que tu as testé jusqu'à 10⁸, alors j'ai voulu tester au delà, 24 445 782 575 m'a paru assez grand pour être convaincant :

Sortie n°2
*****************************************************
* Calcul de l'indicatrice d'Euler par différences *
*****************************************************
D(24445782575) = [1, 5, 25, 1559, 7795, 38975, 627217L, 3136085L, 15680425L, 977831303L, 4889156515L]
Phi(1) = 1
Phi(5) = 5-Somme des Phi des diviseurs<5 = 5-1 = 4
Phi(25) = 25-Somme des Phi des diviseurs<25 = 25-5 = 20
Phi(1559) = 1559-Somme des Phi des diviseurs<1559 = 1559-1 = 1558
Phi(7795) = 7795-Somme des Phi des diviseurs<7795 = 7795-1563 = 6232
Phi(38975) = 38975-Somme des Phi des diviseurs<38975 = 38975-7815 = 31160
Phi(627217) = 627217-Somme des Phi des diviseurs<627217 = 627217-1 = 627216
Phi(3136085) = 3136085-Somme des Phi des diviseurs<3136085 = 3136085-627221 = 2508864
Phi(15680425) = 15680425-Somme des Phi des diviseurs<15680425 = 15680425-3136105 = 12544320
Phi(977831303) = 977831303-Somme des Phi des diviseurs<977831303 = 977831303-628775 = 977202528
Phi(4889156515) = 4889156515-Somme des Phi des diviseurs<4889156515 = 4889156515-980346403 = 3908810112
Somme : 1+4+20+1558+6232+31160+627216+2508864+12544320+977202528+3908810112 = 4901732015
Phi(24445782575) = 24445782575 - 4901732015 = 19544050560

Je précise que l'affichage pour ce dernier test est quasi instantané : entre le clic sur Run, il y a un très léger délai perceptible, je dirais probablement inférieur à la demi-seconde...
Avec 2 chiffres de plus : n = 2 444 578 257 595, j'ai un délai légèrement inférieur à la seconde. Mais aucun problème !...

Et toi qu'entends-tu par
* "marche plus ou moins" ?
Ça marche ou ça ne marche pas !
* "La fonction peut calculer jusqu'à 10⁸ sans grande difficulté"
Sans grande difficulté ? Il arrive qu'il y ait des difficultés ?
Pour un "débutant" (?), se lancer dans la récursivité... chapeau !

@+

EttoreB · 02-11-2015 22:41:20

Ceci est un peu plus simple:

def phi(n):
x = 0
i = n-1
while i > 1:
if i % 2 == 0:
i = i>>1
x += 1
else:
i = n-i
S = n % x
F = n-S
return F

Forum de mathématiques - Bibm@th.net

#1 20-10-2013 17:23:29

[Python] Fonction indicatrice d'Euler

#2 20-10-2013 20:01:09

Re : [Python] Fonction indicatrice d'Euler

#3 20-10-2013 21:42:32

Re : [Python] Fonction indicatrice d'Euler

#4 21-10-2013 09:11:46

Re : [Python] Fonction indicatrice d'Euler

#5 21-10-2013 13:58:42

Re : [Python] Fonction indicatrice d'Euler

#6 22-10-2013 13:01:24

Re : [Python] Fonction indicatrice d'Euler

#7 23-10-2013 17:01:06

Re : [Python] Fonction indicatrice d'Euler

#8 24-10-2013 15:33:56

Re : [Python] Fonction indicatrice d'Euler

#9 24-10-2013 19:06:46

Re : [Python] Fonction indicatrice d'Euler

#10 24-10-2013 20:18:22

Re : [Python] Fonction indicatrice d'Euler

#11 02-11-2015 22:41:20

Re : [Python] Fonction indicatrice d'Euler

Pied de page des forums