Listes et fonction factor()

[ReziiaK]

Bonjour à tous,
j'aurais besoin d'un petit coup de main au sujet des listes sur Ti 89T.

Je souhaiterais réaliser un programme me permettant de déterminer si le nombre rentré est un nombre de Carmichael ou non. Un nombre de Carmichael est un nombre vérifiant le petit théorème de fermat en toute base, et n'étant pourtant pas premier. Après d'infructueuses tentatives, j'ai pensé à utiliser le critère de Korselt, qui dit:
"Un nombre N est un nombre de Carmichael ssi ce nombre est sans facteur premier carré, et que ses diviseurs premiers p_i vérifient la relation p_i -1 divise N-1"

Vous avez compris, je voudrais utiliser la décomposition en produit de facteurs premiers de N, stocker ces facteurs dans une liste puis voir s'ils vérifient les deux conditions énoncées ci-dessus. Et c'est là qu'un problème se pose, voir même plusieurs problèmes:

1) Il m'est venu à l'idée ( ) d'utiliser la fonction factor() native à la Ti89, afin de déterminer puis de stocker dans une liste les facteurs premiers de N. Le problème, c'est que je ne sais pas comment ''extraire'' les facteurs trouvés grâce à cette fonction. Ceux-ci sont-ils temporairement stockés dans une liste avant d'être "mis en forme'' et affichés à l'écran? Dans ce cas-là, est-il possible de les récupérer séparément?

2) Une autre solution envisageable est de créer un programme pour décomposer N en produit de facteurs premiers, puis stocker ces facteurs dans une liste, en sachant qu'il nous faudra déterminer si ces facteurs ont pour exposant 1 ou non.
Ici, un problème de dimension de liste me pose problème, je n'arrive pas à exécuter ceci:
x-> dim(list)
Faut-il que je déclare la liste auparavant comme cela? : { }-> list
Ou bien est-ce tout simplement impossible sur Ti89T et faut-il donc modifier l'écriture?
Si vous aviez des exemples de programmes intéressants utilisant des listes, je serais content de les voir pour comprendre leur fonctionnement et apprendre de nouvelles "astuces" de programmation...

Je préférerais directement utiliser une fonction native à la calto plutôt que d'avoir à créer un prgm de décomposition en produit de facteurs premiers, qui me semble assez difficile au vu de mes faibles connaissances en matière de programmation en Ti Basic 68k.

Merci d'avance pour votre aide, en ésperant ne pas vous avoir assommé sous mon flot de questions.

[Lionel Debroux]

Bonjour,

Merci d'avance pour votre aide, en espérant ne pas vous avoir assommé sous mon flot de questions.

Au moins, tu as fait un post détaillé, clair, écrit en bon français

1): je vois au moins trois solutions:
* (BASIC) convertir le résultat de factor() en chaîne de caractères, puis découper la chaîne selon '*', si ce caractère existe;
* (BASIC) utiliser part(), mais le manuel et les autres membres de ce forum seront de bien meilleures sources d'information que moi;
* (C/ASM) parcourir l'arbre RPN d'expressions produit par la routine qui implémente factor(). Je vois trois cas: ou bien le tag est entier (auquel cas le nombre n'a pas été factorisé), ou bien le tag est puissance (auquel cas le nombre est une puissance parfaite), ou bien le tag est produit, auquel cas il faut se balader dans les termes du produit (qui seront eux-mêmes des entiers ou des puissances) pour en extraire les termes.

2) en effet, en BASIC, tu peux utiliser {} -> list, puis ajouter des éléments (augment() et autres, si je me souviens bien). En C/ASM, c'est toi qui fais grandir la liste comme tu veux, si possible depuis la fin vers le début (sinon, on peut toujours inverser la liste à la fin, mais ça peut être moins efficace).

factor() est connue comme une implémentation assez futée, TI a mal fait un certain nombre de choses dans l'OS mais la factorisation d'entiers n'en fait pas partie. Ecrire un bon programme de décomposition en produit de facteurs premiers peut être un exercice d'apprentissage intéressant et utile, mais il faut s'embêter un peu (et écrire en C/ASM) pour que ça aille plus vite que factor()

[ReziiaK]

Merci pour cette réponse rapide et détaillée.
J'ai lu ce message et commencé à exploiter ces informations en feuilletant le manuel et en tâtonnant sur la Ti89T, et je dois avouer que cela m'a bien fait avancé.

1) J'ai commencé par essayer de segmenter la chaîne de caractère en fonction de "*", en vain... Ce symbole (à moins que je me trompe) ne semble pas être reconnu comme caractère, de plus pour des facteurs premiers nombreux cette démarche n'est pas trivial

J'ai me suis donc naturellement tourné vers la fonction part(), qui m'apparaît comme un outil très puissant bien qu'assez difficile à comprendre et à manipuler. Je n'ai malheureusement trouvé aucune information au sujet de cette fonction sur internet, et seul le manuel (bien que très concis) m'a offert quelques pistes non négligeables: j'ai ainsi réussi (par je ne sais quel bidouillage ) à "extraire" les trois facteurs premiers de 561, premier nombre de Carmichael.

Code: Tout sélectionner

561=3*11*17
part(factor(561),2)= 17
part(factor(561),1)=3*11

part(factor(3*11),1)=3
part(factor(3*11),2)=11


Reste plus qu'à essayer avec d'autres nombres pour affiner le processus.
Ensuite, je pensais stocker ces facteurs dans une liste et utiliser le théorème de Wilson pour déterminer s'ils sont premiers ou non: en effet, prenons l'exemple de N=12.
N=2^2*3
Donc en séparant ces facteurs premiers avec la fonction part(), on obtiendra 2^2 et 3.
Or, 2^2=4 qui n'est pas premier, ce qui prouve bien que N n'est pas sans facteurs carrés, donc ne peut pas être un nombre de Carmichael (cf. critère de Korselt).

Finalement, après avoir passé (de façon positive) ce premier test, les facteurs premiers p_i de N seront tour à tour analysés pour déterminer si p_i divise bien N-1.
Ici, j'imagine qu'on regardera si partDéc((N-1)/(list[i]-1))=0 (avec "list" la liste contenant les facteurs premiers et i une variable incrémentée dans une boucle For, et dépendant du nombre de facteurs premiers de N).

[ReziiaK]

2) Même si les fonctions natives de ma calculatrice me permettent de passer outre certaines étapes de programmation (touchant notamment au calcul formel), je souhaiterais néanmoins (en plus du projet cité ci-dessus) créer un programme facilement adaptable aux possibilités et au language z80 propres à la Ti82, la calto la plus répandue en classe de TS, afin de pouvoir partager mon programme avec les autres élèves de spé Maths.

Qu'elle méthode faut-il préconiser (en BASIC) pour créer un prgm de décomposition d'un nombre en produits de facteurs premiers qui soit rapide et efficace?

Merci d'avance de prendre le temps d'éclairer ma lanterne (et désolé pour le double post mais j'ai tendance à beaucoup écrire)

[Lionel Debroux]

Qu'elle méthode faut-il préconiser (en BASIC) pour créer un prgm de décomposition d'un nombre en produits de facteurs premiers qui soit rapide et efficace?

"en BASIC" et "rapide et efficace" ne vont pas du tout ensemble
Sur TI-Z80, des gens ont déjà essayé de faire des programmes en BASIC pour factoriser des entiers; ils doivent pour la plupart être basés sur la division par essais (Trial Factoring). Peut-être Fermat ou Rho de Pollard, mais on est très vite limité par la lenteur d'exécution du langage.

Pour les TI-Z80, si les nombres qu'on te demande de factoriser ne dépassent pas quelques milliers (valeurs < 16 bits), ne t'embête pas, utilise l'algo naïf de divisions par essais, qui fera au pire 2^8 itérations pour trouver un éventuel facteur.
Au-delà... mieux vaut s'y prendre autrement, soit en utilisant un langage mieux adapté (sur TI-Z80, l'ASM est la seule vraie solution, car le processeur n'est pas fait pour le C et la performance du C en souffre), soit en utilisant une calculatrice plus évoluée

[Bisam]

Reprenons un petit peu les réponses initiales de Lionel pour la syntaxe en BASIC.

Tout d'abord, pour l'utilisation des listes.
Tu peux ajouter des éléments à une liste avec la fonction "augment"... mais ce n'est pas la seule manière.
Tu peux aussi le faire en affectant la valeur située après la dernière position, cela fera automatiquement grandir la liste.
Par exemple :

Code: Tout sélectionner

liste:={}
for i,1 10
   liste[i]:=i^2+1
endfor

A priori, la liste est créée avec 0 éléments... mais on augmente sa taille au fur et à mesure.
Tu peux bien sûr utiliser la dimension de ta liste si tu ne la connais (ou ne souhaite pas la stocker)

Code: Tout sélectionner

liste[dim(liste)+1]:=42

Ensuite, à propos de ta factorisation et de la récupération des facteurs. Je te déconseille vivement d'utiliser la fonction "part" dans ce cas... En effet, les simplifications automatiques de la calculette font que si ton résultat comporte 3 facteurs ou plus, la calculette te dira qu'il y a 2 facteurs, dont l'un est un produit... mais si tu veux réappliquer la fonction "part" à ce produit, tu es obligé de le re-factoriser, sinon la calculette te dira qu'il n'y a qu'un seul morceau, un nombre. Cela peut prendre un temps fou d'utiliser cette méthode si le nombre de facteurs est grand !

La "bonne" méthode, ici, est d'utiliser une chaîne de caractères, comme te le suggérait Lionel au départ.
Tu convertis directement le résultat de "factor" en chaîne de caractères, et tu segmentes ta chaîne en recherchant le caractère "*". Voici un code qui fonctionne :

Code: Tout sélectionner

chaine:=string(factor(nombre))
liste:={}
n:=0
p:=instring(chaine,"*")
while p>0
  n:=n+1
  list[n]:=expr(left(chaine,p-1))
  chaine:=mid(chaine,p+1)
  p:=instring(chaine,"*")
endwhile
return list

[Lionel Debroux]

Pour une TI-68k, dans les exemples de code donnés par Bisam, il faut remplacer les formes "a := b" (gérées seulement par les Nspire) par des formes "b -> a"

[Bisam]

Bon sang ! Je me suis forcé à mettre des := auxquels je suis moins habitué que les "sto" ... et j'ai zappé qu'on parlait d'une TI89 !