[Mini-Challenge Basic #6] : Nombres parfaits

→ **MyCalcs** profile · de **davidElmaleh** » 06 Juil 2014, 18:20

Le but de ce défi est de créer une fonction isperfect(n) qui prend un compte un entier n et qui renvoie true s'il est parfait et false sinon.

La fonction sera de la forme:

Code: Tout sélectionner: Define isperfect(n)= Func votreCode EndFunc

Vous serez noté sur la rapidité d’exécution du programme en fonction de la grandeur du nombre en entrée.

→ **MyCalcs** profile · de **Bisam** » 06 Juil 2014, 18:33

Euh, si le critère est la taille, il existe des fonctions... super non optimales au niveau du temps d'exécution !
Et puis, il y a déjà eu un concours sur les nombre premiers palindromes il y a peu de temps...

→ **MyCalcs** profile · de **davidElmaleh** » 06 Juil 2014, 18:41

Je voulais faire le même concours mais pour les nombres parfait. Tu crois que je dois changer?

EDIT: et dans ce cas, le critère serait la rapidité et non la taille

→ **MyCalcs** profile · de **Adriweb** » 06 Juil 2014, 19:00

(réponse d'avant l'édit du sujet)

Pour isprime2() : en théorie, Return mod(n!,n^(2))=n*(n-1) marche et est possiblement le plus court (?), mais forcément, il va pas aller bien loin.....

(source : formule de Gary Detlefs, sur oeis)

Pas encore réfléchi pour les nombres parfaits.

→ **MyCalcs** profile · de **davidElmaleh** » 06 Juil 2014, 19:06

D'ou le but de créer l'algo le plus rapide et non le plus court

EDIT : J'ai cru que tu parlais des nombres parfaits

→ **MyCalcs** profile · de **Adriweb** » 06 Juil 2014, 19:20

Pour les nombres parfaits, voici ma proposition :

Return ∑(i*int(n/i),i,1,n-2)=1+∑(i*int((n-1)/i),i,1,n-1)

C'est une formule montrée par Ruiz (cf. mathworld)

→ **MyCalcs** profile · de **davidElmaleh** » 06 Juil 2014, 19:52

J'ai une solution plus rapide et beaucoup plus simple

→ **MyCalcs** profile · de **davidElmaleh** » 06 Juil 2014, 20:04

(Dsl pour le double post)

Voila les statistiques pour l'instant pour les participations actuelles
Adriweb : isperfect(10^6) = false en 9 sec. 34 /
davidElmaleh : isperfect(10^6) = false en moins de 100 ms / isperfect(10^9) = false en 1 sec. 57 / isperfect(137438691328) = true en 25 sec.

→ **MyCalcs** profile · de **Adriweb** » 06 Juil 2014, 20:11

Ah mais j'ai pas cherché la rapidité, juste une formule "plutôt courte".
Je pense pas que la vérification triviale soit plus court,e mais je n'ai même pas essayé...

Après, il y a sans doute mieux, c'est sur ^^

→ **MyCalcs** profile · de **Adriweb** » 06 Juil 2014, 20:58

Bon ben la solution triviale est plus courte (et plus rapide) que la formule de ma proposition d'avant ^^

Return n=sum(seq(when(mod(n,i)=0,i,_),i,1,n-1))

(j'ai utilisé _ au lieu de 0 car c'est un poil plus rapide

(un test avec 1 million de fois montre une différence de 0.1 seconde, d'après le timer du Lua)

Edit : et puisque que c'est sur la rapidité qu'on est évalué :
Return when(mod(n,2)≠0,false,n=sum(seq(when(mod(n,i)=0,i,_),i,1,n-1)))