La question (très simple) du dimanche après-midi.

Ici, on fait dans le petit, le LCD qui déchire sa race, on y cause même calculatrices quand on est en manque !

Modérateur : Politburo

Avatar du membre
C.Ret
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 3400
Enregistré le : 31 mai 2008 23:43
Localisation : N 49°22 E 6°10

La question (très simple) du dimanche après-midi.

Message par C.Ret »

Je me suis installé sur la terrasse qui est maintenant à l'ombre pour finir mon dessert glacé et sa crème à la vanille.

Autour de moi on s'affère pour débarrasser, ranger et nettoyer la grille du BBQ.

Entre deux cuillères, je laisse fondre ma bouchée en observant la brise qui agite les branches des arbres sur l'autre rive de la pelouse.

Et je me pose une question très simple (bien que composée) les nombres 99875772649 et 99875772671 sont-ils premiers ?

Peut-être connaissez-vous la réponse. Moi pas. En tout cas pas pour l'instant.
J'en saurai certainement plus dimanche prochain (pas avant hein ! C'est une QDD ! ).

Mais c'est moins la réponse à ma question que de connaitre le ou les moyen(s) que vous mettrez en œuvre pour y répondre qui m'intéresse.

Pour le moment, je fini de savourer cette coupe en observant calmement l'agitation qui m'entoure et m'endort.
Modifié en dernier par C.Ret le 07 juin 2019 20:39, modifié 1 fois.
SHARP PC-1211 PC-1360 EL-5150 PC-E500 | Commodore C=128D | Texas Instruments Ti-57LCD Ti-74BASICalc Ti-92II Ti-58c Ti-95PROCalc Ti-30XPROMathPrint | Hewlett-Packard HP-28S HP-41C HP-15C HP-Prime HP-71B | CASIO fx-602p | NUMWORKS | Graphoplex Rietz Neperlog | PockEmul | Sommaire des M.P.O. | Ma...dov'il sapone.
Gilles59
Fonctionne à 2400 bauds
Fonctionne à 2400 bauds
Messages : 1602
Enregistré le : 27 oct. 2010 20:46

Re: La question (très simple) du dimanche après-midi.

Message par Gilles59 »

Voyons donc…

On constate "à l'oeil" que ces nombres ne sont pas divisibles par 2,3,5,...
Une calculatrice (gérant suffisamment de chiffres) permet de vérifier (ou pas) ce qu'il en est d'un éventuel carré parfait ou d'une division par 7.
Arrivé là, je suppose qu'il faut réfléchir un peu plus...
Le fait que les deux nombres soient proches n'est peut-être pas anodin. ou peut-être est-ce anodin lol...
Casio FX-502P /602P / 603P / FX180P+ / FX4000P / TI57 / TI66 / TI74 Basicalc / TI95 Procalc / HP12C / HP15C LE / DM41L / HP 30B / HP39GII / HP 48SX USA / 49G / 49g+ / 50G / 50G NewRPL / HP Prime / Oric 1 / Amstrad CPC 6128+ CM14 et MM12 / Alice 32
Avatar du membre
C.Ret
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 3400
Enregistré le : 31 mai 2008 23:43
Localisation : N 49°22 E 6°10

Re: La question (très simple) du lundi des déconvenues...

Message par C.Ret »

Gilles59 a écrit : 02 juin 2019 22:23 […](gérant suffisamment de chiffres) […] lol...
A zut, dans mon empressement du début d'après-midi, j'ai vérifié avec mon HP-28S. Je sens que Marge va m'en vouloir car sur son HP-15LE ou son HP-19C ça va être bien plus complicado complicado … Mais pas impossible pour Marge, qui lors du dernier QDD nous à démontré brillamment sa ténacité. Je m’inquiète pour tous les autres utilisateurs ; ceux des classiques HP, des solide-states TI, des corporatives SHARP et fléxives CASIO …


Je vais donc immédiatement poser une seconde question qui viendra compléter celle de dimanche.

Décidément, autant la journée d'hier était enchanteresse, autant c'est aujourd'hui le lundi de toutes les déconvenues…

Donc, pour tous ceux qui ont eu aujourd'hui un début de semaine difficile, et uniquement ces derniers, je pose une question du lundi dont nous pourrons donner les réponses dès vendredi soir. Une question de la semaine en quelque sorte.

Les nombres 9831013529 et 9831013559 sont-ils premiers ?

Etes-vous sûr à 100% de votre réponse ? Mais quelque soit votre degré de confiance , comment avez-vous fait pour arriver à ce résultat ?

L'air de rien avec cette seconde question, je donne comme un indice ...
Modifié en dernier par C.Ret le 03 juin 2019 20:07, modifié 1 fois.
SHARP PC-1211 PC-1360 EL-5150 PC-E500 | Commodore C=128D | Texas Instruments Ti-57LCD Ti-74BASICalc Ti-92II Ti-58c Ti-95PROCalc Ti-30XPROMathPrint | Hewlett-Packard HP-28S HP-41C HP-15C HP-Prime HP-71B | CASIO fx-602p | NUMWORKS | Graphoplex Rietz Neperlog | PockEmul | Sommaire des M.P.O. | Ma...dov'il sapone.
Avatar du membre
gege
Fonctionne à 14400 bauds
Fonctionne à 14400 bauds
Messages : 7141
Enregistré le : 31 janv. 2008 14:24
Localisation : Banlieue Paârisienne
Contact :

Re: La question (très simple) du dimanche après-midi.

Message par gege »

Bonjour,
La HP Prime fait tout ça aisément, mais sans cela je ne vois pas trop de machine qui en soit capable ?
4000 boucles c'est long !
G.E.
Avatar du membre
Marge
Fonctionne à 14400 bauds
Fonctionne à 14400 bauds
Messages : 6167
Enregistré le : 01 oct. 2008 14:39
Localisation : En bas, tout au fond à gauche.

Re: La question (très simple) du dimanche après-midi.

Message par Marge »

Bonsoir,

Je crois que même le problème initial devrait être à la portée d'une machine gérant seulement 10 chiffres à l'affichage, il s'agit de multiples opérations sur de grands nombres et ces petites bêbêtes en sont bien capables, à mon avis. Ça risque d'être très long, en revanche.

Pour ma part ce sera difficile que je relève ce défi, j'en suis désolé, C.Ret, car je dois vraiment avancer sur mon programme de jeu de cartes et sur l'article qui en découlera. Je promets de ne pas me laisser divulgâcher vos méthodes et de tenter quelque chose après.... plus tard... là-bas... :wink:
3 hommes, 3 demis, un 3a... Magnéto, Serge !

Quelques-uns de mes petits programmes pour machines Hewlett-Packard :
15C : Knight's Tour ;
29C : (k-)Permutations, Combinations, Linear Regression and Pseudo-random number ;
34C : Hanoi Towers - Automatic & Manual resolutions ;
67
__: A L I E N .

« Boris », c'était juste Maurice enrhumé.
Avatar du membre
gege
Fonctionne à 14400 bauds
Fonctionne à 14400 bauds
Messages : 7141
Enregistré le : 31 janv. 2008 14:24
Localisation : Banlieue Paârisienne
Contact :

Re: La question (très simple) du dimanche après-midi.

Message par gege »

Bonjour,
Le test par le petit théorème de Fermat fonctionne bien, mais ne donne pas de diviseurs.
Il est certain seulement quand il affirme qu'un nombre n'est pas premier.
Ça tourne en 8 secondes sur TI89.
G.E.
Gilles59
Fonctionne à 2400 bauds
Fonctionne à 2400 bauds
Messages : 1602
Enregistré le : 27 oct. 2010 20:46

Re: La question (très simple) du dimanche après-midi.

Message par Gilles59 »

Sur les machine puissantes c’est « natif ». Je vais essayer sur 603p mais il falloir ruser sur les chiffres significatifs. Si j’ai fini mon article avant. Et si je laisse un peu de côté le newRPL qui m’amuse beaucoup en ce moment avec sa gestion de fichier sur la carte SD.
Casio FX-502P /602P / 603P / FX180P+ / FX4000P / TI57 / TI66 / TI74 Basicalc / TI95 Procalc / HP12C / HP15C LE / DM41L / HP 30B / HP39GII / HP 48SX USA / 49G / 49g+ / 50G / 50G NewRPL / HP Prime / Oric 1 / Amstrad CPC 6128+ CM14 et MM12 / Alice 32
Gilles59
Fonctionne à 2400 bauds
Fonctionne à 2400 bauds
Messages : 1602
Enregistré le : 27 oct. 2010 20:46

Re: La question (très simple) du dimanche après-midi.

Message par Gilles59 »

gege a écrit : 03 juin 2019 19:55 Bonjour,
La HP Prime fait tout ça aisément, mais sans cela je ne vois pas trop de machine qui en soit capable ?
4000 boucles c'est long !
G.E.

4000 boucles c’est déjà très optimisé! A vrai dire je me suis fort avancé pour un prog 603p. 4000 boucles ça irait mais il faut un algorithme pointu ... même en supprimant les boucles de 2 de 3 de 5 , de 7 il en reste beaucoup! Plutôt 40000 que 4000.
Casio FX-502P /602P / 603P / FX180P+ / FX4000P / TI57 / TI66 / TI74 Basicalc / TI95 Procalc / HP12C / HP15C LE / DM41L / HP 30B / HP39GII / HP 48SX USA / 49G / 49g+ / 50G / 50G NewRPL / HP Prime / Oric 1 / Amstrad CPC 6128+ CM14 et MM12 / Alice 32
Avatar du membre
C.Ret
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 3400
Enregistré le : 31 mai 2008 23:43
Localisation : N 49°22 E 6°10

Re: La question (très simple) du dimanche après-midi.

Message par C.Ret »

Ha! ha !

C'est justement ce qui a motivé ma (mes) question(s) !

Je trouve aussi que c'est beaucoup, beaucoup trop si l'on veut être sûr à 100%. Mais je ne connais que les méthodes rigoureuses.

Il doit exister des méthodes heuristiques qui garantissent d'avoir un diagnostique moins certain, mais dans un temps raisonnableou tout au moins maitrisé.

Car la méthode rigoureuse que j'utilise est très consommatrices de temps; précieux temps perdu en boucles plus ou moins affinées (mon pauvre HP-28S met plus de 6h pour me confirmer le diagnostique dans certains des cas - dans d'autre il ne met à peine plus d'une minute).

Pourquoi une aussi grande différence alors que les deux nombres sont si proches ?
SHARP PC-1211 PC-1360 EL-5150 PC-E500 | Commodore C=128D | Texas Instruments Ti-57LCD Ti-74BASICalc Ti-92II Ti-58c Ti-95PROCalc Ti-30XPROMathPrint | Hewlett-Packard HP-28S HP-41C HP-15C HP-Prime HP-71B | CASIO fx-602p | NUMWORKS | Graphoplex Rietz Neperlog | PockEmul | Sommaire des M.P.O. | Ma...dov'il sapone.
Avatar du membre
dprtl
Fonctionne à 1200 bauds
Fonctionne à 1200 bauds
Messages : 463
Enregistré le : 27 janv. 2013 00:26
Localisation : Strasbourg
Contact :

Re: La question (très simple) du dimanche après-midi.

Message par dprtl »

C.Ret a écrit : 04 juin 2019 19:48 Car la méthode rigoureuse que j'utilise est très consommatrices de temps; précieux temps perdu en boucles plus ou moins affinées (mon pauvre HP-28S met plus de 6h pour me confirmer le diagnostique dans certains des cas - dans d'autre il ne met à peine plus d'une minute).

Pourquoi une aussi grande différence alors que les deux nombres sont si proches ?
Sur les nombres à dix chiffres, un programme naïf, avec essais de division successifs (comme celui que j'ai publié sur mon blog pour plusieurs machines) fonctionne bien (sauf sur TI-57 où on ne peut afficher que 8 chiffres significatifs). Par exemple, sur 9831013529 le premier diviseur supérieur à 1 est trouvé rapidement en un peu plus de 1100 itérations. C'est évidemment plus long pour prouver que 9831013559 est premier.

Par contre, la précision de nombreuses calculettes programmables est insuffisante pour travailler sur les nombres à 11 chiffres comme 99875772649 ou 99875772671. Dans ce cas, on aura besoin de développer des routines de calcul en multiprécision ; probablement en assembleur.

Sinon, depuis 2002 il existe le fameux test de primalité AKS. Une implémentation serait-elle envisageable sur calculette ?
Modifié en dernier par dprtl le 06 juin 2019 19:54, modifié 1 fois.
Gilles59
Fonctionne à 2400 bauds
Fonctionne à 2400 bauds
Messages : 1602
Enregistré le : 27 oct. 2010 20:46

Re: La question (très simple) du dimanche après-midi.

Message par Gilles59 »

dprtl a écrit : 06 juin 2019 16:27 Sinon, depuis 2002 il existe le fameux test de primalité AKS. Une implémentation serait-elle envisageable sur calculette ?
Je n'ai pas étudié AKS mais j'ai regardé l'algorithme de Miller-Rabin. Tout à fait faisable sur les machine type Prime ou en RPL... Ca ne semble pas hors de portée de calculettes plus simples mais avec une difficulté peut-être majeure sur un point précis, mais je n'en dis pas plus.
Casio FX-502P /602P / 603P / FX180P+ / FX4000P / TI57 / TI66 / TI74 Basicalc / TI95 Procalc / HP12C / HP15C LE / DM41L / HP 30B / HP39GII / HP 48SX USA / 49G / 49g+ / 50G / 50G NewRPL / HP Prime / Oric 1 / Amstrad CPC 6128+ CM14 et MM12 / Alice 32
Avatar du membre
dprtl
Fonctionne à 1200 bauds
Fonctionne à 1200 bauds
Messages : 463
Enregistré le : 27 janv. 2013 00:26
Localisation : Strasbourg
Contact :

Re: La question (très simple) du dimanche après-midi.

Message par dprtl »

Une implémentation de Miller-Rabin dans le Basic 1000D de l'Atari ST lui permet de répondre à cette question du dimanche rapidement, avec le programme suivant :

Code : Tout sélectionner

clear timer
print prtst(99875772649);mtimer
clear timer
print prfact(99875772649);mtimer
clear timer
print prtst(99875772671);mtimer
Les résultats sont affichés respectivement en 85 ms, 530 ms (pour la factorisation) et 2325 ms.
Gilles59
Fonctionne à 2400 bauds
Fonctionne à 2400 bauds
Messages : 1602
Enregistré le : 27 oct. 2010 20:46

Re: La question (très simple) du dimanche après-midi.

Message par Gilles59 »

dprtl a écrit : 06 juin 2019 20:29
Les résultats sont affichés respectivement en 85 ms, 530 ms (pour la factorisation) et 2325 ms.
La question est avec quelle probabilité ;D
Sur ma HP50g en newRPL :

99875772649 en 13ms
99875772671 en 21ms

(les temps de réponse peuvent légèrement varier aléatoirement , le 2 vient de tourner en 11ms puis en 32ms)

Mon programme ne fonctionne pas en RPL classique car il manque la commande EXIT. Je vais faire une variante. J'ai une version Prime aussi je vais tester la vitesse sur la calc.

Si je trouve un peu de temps j'essaie sur 602/603 mais il manque une fonction essentielle native en RPL et PRIME (non non ce n'est pas ISPRIME? lol)
Modifié en dernier par Gilles59 le 06 juin 2019 23:37, modifié 3 fois.
Casio FX-502P /602P / 603P / FX180P+ / FX4000P / TI57 / TI66 / TI74 Basicalc / TI95 Procalc / HP12C / HP15C LE / DM41L / HP 30B / HP39GII / HP 48SX USA / 49G / 49g+ / 50G / 50G NewRPL / HP Prime / Oric 1 / Amstrad CPC 6128+ CM14 et MM12 / Alice 32
Avatar du membre
gege
Fonctionne à 14400 bauds
Fonctionne à 14400 bauds
Messages : 7141
Enregistré le : 31 janv. 2008 14:24
Localisation : Banlieue Paârisienne
Contact :

Re: La question (très simple) du dimanche après-midi.

Message par gege »

Bonjour,
Il y a un Rabin-Miller page 40 de la Gazette N°2...
G.E.
Gilles59
Fonctionne à 2400 bauds
Fonctionne à 2400 bauds
Messages : 1602
Enregistré le : 27 oct. 2010 20:46

Re: La question (très simple) du dimanche après-midi.

Message par Gilles59 »

gege a écrit : 06 juin 2019 23:29 Bonjour,
Il y a un Rabin-Miller page 40 de la Gazette N°2...
G.E.
Vais voir çà , merci !

EDIT : cool j'ai trouvé le bout de code (enfin l'algorithme) qui me manquait pour la 602/603 ;D

EDIT 2 : il y a une différence entre le programme de la Gazette et le mien. J'utilise des nombres aléatoires pour l'élévation à la puissance (algo trouvé sur le net), alors que les valeurs dans le prog PB700 sont fixes (3,5,7,17). Ca explique que les temps de réponse peuvent un peu varier avec mon programme. Mais je suis bien incapable de dire si utiliser des nombres aléatoires est mieux ou pas.
Modifié en dernier par Gilles59 le 09 juin 2019 13:35, modifié 1 fois.
Casio FX-502P /602P / 603P / FX180P+ / FX4000P / TI57 / TI66 / TI74 Basicalc / TI95 Procalc / HP12C / HP15C LE / DM41L / HP 30B / HP39GII / HP 48SX USA / 49G / 49g+ / 50G / 50G NewRPL / HP Prime / Oric 1 / Amstrad CPC 6128+ CM14 et MM12 / Alice 32
Répondre

Retourner vers « Tous les Pockets »