Misez p'tit Optimisez n°70 : les couples sexy

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

Gilles59
Fonctionne à 2400 bauds
Fonctionne à 2400 bauds
Messages : 1602
Enregistré le : 27 oct. 2010 20:46

Misez p'tit Optimisez n°70 : les couples sexy

Message par Gilles59 »

La definition d'un couple sexy est donnée dans La Gazette n°7 page 52 :
D'un point de vue mathématique, il s'agit des
couples de nombres premiers dont la différence
égale six, soit par exemple : (5,11) ;(7,13) ;
(11,17) ;(13,19)…(373,379) ;(383,389)…etc.
La touche sexy n'existant pas, la question reste
donc posée et nous invitons les membres du
forum du site Silicium.org à formuler un
programme en Basic ou autre langage pour
présenter ces couples dit « sexy »...
Votre défi consiste donc à écrire un pogramme qui affichera la succession des couples sexy sur votre micropoche préféré. Les machines qui disposent de fonctions natives pour manipuler les nombres premiers sont à l'évidence favorisées mais tout le monde peut essayer.

À vous de jouer !
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: Misez p'tit Optimisez n°70 : les couples sexy

Message par Gilles59 »

Une version pour HP49G HP49G+ et HP50G

Code : Tout sélectionner

1 DO
 NEXTPRIME DUP 6 + DUP ISPRIME? 
 { OVER SWAP R->C HALT SWAP }
 { DROP }
 IFTE
UNTIL 0 END
83.5 octets
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: Misez p'tit Optimisez n°70 : les couples sexy

Message par Gilles59 »

En bonus un programme pour tester si un couple est sexy ou pas :

Code : Tout sélectionner

DUP ISPRIME? πLIST SWAP ∆LIST EVAL ABS 6 == *
Usage :
{ 5 11 } Sexy?

Renvoie 1 si sexy ou 0 sinon.
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
zpalm
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 2919
Enregistré le : 03 mai 2008 15:33
Localisation : Grenoble

Re: Misez p'tit Optimisez n°70 : les couples sexy

Message par zpalm »

Sur WP 34s en 9 pas et 18 octets:

Code : Tout sélectionner

01 LBL A
02 CLx 
03 NEXTP
04 6
05 RCL+ Y
06 PRIME?
07 STOP
08 DROP
09 BACK 006
Avec YDON pour afficher les registres x et y, chaque paire trouvée est affichée, R/S permet de passer à la paire suivante.

Pour savoir si un couple est sexy en 18 pas et 36 octets :

Code : Tout sélectionner

01 LBL B
02 cENTER
03 PRIME?
04 CLx
05 Rdn
06 PRIME?
07 CLx
08 Rdn
09 -
10 ABS
11 6
12 -
13 +
14 +
15 x#0?
16 RCL/ X
17 NOT
18 END
Par exemple: 5 [ENTER] 11 donne 1, et 19 [ENTER] 25 donne 0
Gilles59
Fonctionne à 2400 bauds
Fonctionne à 2400 bauds
Messages : 1602
Enregistré le : 27 oct. 2010 20:46

Re: Misez p'tit Optimisez n°70 : les couples sexy

Message par Gilles59 »

Une version qui va à l'essentiel

Code : Tout sélectionner

1 DO
 NEXTPRIME DUP 6 + DUP ISPRIME?  { HALT  } IFT DROP  
UNTIL 0 END
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
zpalm
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 2919
Enregistré le : 03 mai 2008 15:33
Localisation : Grenoble

Re: Misez p'tit Optimisez n°70 : les couples sexy

Message par zpalm »

Une version un peu plus optimisée du programme WP 34s pour déterminer si un couple est sexy en 15 pas et 30 octets:

Code : Tout sélectionner

01 LBL B
02 cENTER
03 x#0?
04 PRIME?
05 x<>y	
06 PRIME?
07 CLx	
08 <> ZTXX
09 -
10 ABS
11 6
12 -
13 +
14 NOT
15 END
et une version encore plus courte en 12 pas et 24 octets, mais qui ne marche qu'avec des nombres différents de 0:

Code : Tout sélectionner

01 LBL B
02 PRIME?	
03 x<>y   
04 PRIME? 
05 SKIP 001
06 SKIP 004
07 -
08 ABS
09 6
10 -
11 NOT
12 END
Gilles59
Fonctionne à 2400 bauds
Fonctionne à 2400 bauds
Messages : 1602
Enregistré le : 27 oct. 2010 20:46

Re: Misez p'tit Optimisez n°70 : les couples sexy

Message par Gilles59 »

zpalm a écrit :Sur WP 34s en 9 pas et 18 octets:

Code : Tout sélectionner

01 LBL A
02 CLx 
03 NEXTP
04 6
05 RCL+ Y
06 PRIME?
07 STOP
08 DROP
09 BACK 006
Excellent :D
Je me demandais si une syntaxe type Goto03 à la place du Back006 est possible ? Ce serait plus lisible.
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
zpalm
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 2919
Enregistré le : 03 mai 2008 15:33
Localisation : Grenoble

Re: Misez p'tit Optimisez n°70 : les couples sexy

Message par zpalm »

Gilles59 a écrit :Je me demandais si une syntaxe type Goto03 à la place du Back006 est possible ? Ce serait plus lisible.
Sur la WP 34S le GTO se fait sur un label, ce qui nécessite d'ajouter un pas de plus (2 octets).

Par contre ce qui est possible c'est d'utiliser l'assembleur WP 34S avec son préprocesseur qui supporte la pseudo-instruction JMP qui est traduite soit en SKIP/BACK si la cible est à portée, soit en GTO avec insertion du LBL correspondant si la cible est à plus de 255 pas. Ce qui donne :

Code : Tout sélectionner

         LBL A
         CLx 
 loop::  NEXTP
         6
         RCL+ Y
         PRIME?
         STOP
         DROP
         JMP loop //BACK 006 
Avatar du membre
dprtl
Fonctionne à 1200 bauds
Fonctionne à 1200 bauds
Messages : 463
Enregistré le : 27 janv. 2013 00:26
Localisation : Strasbourg
Contact :

Re: Misez p'tit Optimisez n°70 : les couples sexy

Message par dprtl »

Voici une version naïve (plus lisible ?) en Basic 1000D sur Atari ST :

Code : Tout sélectionner

x=1e15+1
y=x+2000
open "o",#1,"result-mpo70.txt"
while (x<y)
  if prtst(x)
    if prtst(x+6)
      print #1 x;",";x+6
    endif
  endif
  x=x+2
wend
close
Bien entendu, il est inutile de tester si les nombres pairs sont premiers. Pour info, derrière la fonction 'prtst' se cache le test probabiliste de Miller & Rabin, qui a éte codé en assembleur 68k dans l'interpréteur Basic de JJ Labarthe. C'est donc plutôt rapide.

Le résultat, stocké dans un fichier, donne l'impression que les couples sexy deviennent de plus en plus rares pour les grands nombres :

Code : Tout sélectionner

  1000000000000273,  1000000000000279
  1000000000001617,  1000000000001623
Avatar du membre
bernouilli92
Fonctionne à 14400 bauds
Fonctionne à 14400 bauds
Messages : 5230
Enregistré le : 21 nov. 2012 13:03
Localisation : Ile de France

Re: Misez p'tit Optimisez n°70 : les couples sexy

Message par bernouilli92 »

Effectivement, plus les nombres deviennent grands, plus les couples sexy deviennent rares. Mais je pense que, comme les nombres premiers jumeaux, il y a une infinité de nombres sexys.
HP, Casio, Sharp, Psion, quelques TI et divers autres
Gilles59
Fonctionne à 2400 bauds
Fonctionne à 2400 bauds
Messages : 1602
Enregistré le : 27 oct. 2010 20:46

Re: Misez p'tit Optimisez n°70 : les couples sexy

Message par Gilles59 »

En changeant 1 par la valeur de son choix dans le programme 49g au dessus on trouve le premier couple suivant. Par ex avec 10^16

Ex 10000000000002473 , 10000000000002479

Curieuse similitude avec les nombres de Dprtl.

Mais le suivant arrive vite et se termine par 3411 , 3417
Suit 10...3627
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
Marge
Fonctionne à 14400 bauds
Fonctionne à 14400 bauds
Messages : 6172
Enregistré le : 01 oct. 2008 14:39
Localisation : En bas, tout au fond à gauche.

Re: Misez p'tit Optimisez n°70 : les couples sexy

Message par Marge »

Il ne doit manquer grand-chose dans vos programmes pour trouver les trios super sexy...
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é.
Gilles59
Fonctionne à 2400 bauds
Fonctionne à 2400 bauds
Messages : 1602
Enregistré le : 27 oct. 2010 20:46

Re: Misez p'tit Optimisez n°70 : les couples sexy

Message par Gilles59 »

Marge a écrit :Il ne doit manquer grand-chose dans vos programmes pour trouver les trios super sexy...
Mais est-ce bien moral tout ça ? ;D

Code : Tout sélectionner

1 DO
 NEXTPRIME DUP {6 12} ADD DUP ISPRIME? πLIST { HALT  } IFT DROP  
UNTIL 0 END
5 11 17
...
1091 1097 1103
...
1000187 1000193 1000199

En changeant la liste {6 12} par ce que voulez vous aurez les quatuor, quintet ou tout plus si ça vous plaît. Le sextet doit être pas mal mais ma 49g+ le cherche encore : il n'y en a pas car forcément un des nombres est un multiple de 5. Idem pour le quintet.
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 : 3405
Enregistré le : 31 mai 2008 23:43
Localisation : N 49°22 E 6°10

Re: Misez p'tit Optimisez n°70 : les couples sexy

Message par C.Ret »

Gilles59 a écrit :La definition d'un couple sexy est donnée dans La Gazette n°7 page 52 :

[ ...]

Les machines qui disposent de fonctions natives pour manipuler les nombres premiers sont à l'évidence favorisées mais tout le monde peut essayer.

À vous de jouer !

Voici, une version en 159 octets pour SHARP PC-1211 qui :
- n'est pas favorisé par la présence d'une fonction ISPRIME? native ou statistique, ni d'ailleurs d'une instruction NEXTPRIME,
- n'est pas avantagé par sa vitesse de croisière qui rend chaque test de primalité fort lent.

L'idée pour gagner un peu de temps est de mémoriser les nombres premiers au fur et à mesure de leur découverte.
Mais aussi de générer un maximum de nombres premiers par ruse; à l'aide, par exemple, de l'astuce des pas de +2,+4, +2,+4,+2,+4,... ce qui permet de générer des nombres n presque tous premiers, sauf de temps en temps les multiples de 5, 7, 11 etc...

Ce qui fait, qu'il faut tester à chaque génération si le nombre n généré est effectivement premier. Mais qu'il suffira de tester qu'à partir des facteurs premiers f = 5 et suivants. Comme on peut s'arrêter à la racine de n , on limite considérablement le nombre de tests et l'on va donc créer la liste des nombres premiers plus vite que l'on ne la parcours.

Par ailleurs +2+4 fait +6, on avance donc justement d'un pas de 6 ce qui fait que pour tester un couple sexy (x,z), il suffit en fait de se souvenir du résultat du test de primalité de x au moment où l'on a déterminé la primalité de z. Entre temps on aura déterminé si y est premier ce qui servira pour le cycle suivant.
C'est à cela que servent les indicateurs a et b qui mémorisent les résultats du test de primalité p des deux précédents nombres générés.

Le kilooctets de mémoire du SHARP PC-1211 est donc utilisé de la façon suivante:

Code : Tout sélectionner

Registres  Variables    Lignes         Désignations / Commentaires
--- ------ ------------ -------------- -------------------------------------------------------------
  1 A      a            1: 1-2         Indicateur primalité dernier nombre généré.
  2 B      b            2: 2-4         Indicateur primalité avant-dernier nombre généré.
  3 C      c            1: 4-4         Compteur de couples sexy.
  4 D      s            1: 2-2         Incrément 2s=+2 ou +4 pour génération nombres pseudo-premier n
  5 E      n            1: 1-4         Nombre généré (pseudo-premier)
  6 F      f 10 à 185   1: 3-4         Indice du dernier nombre premier mémorisé dans F()
  7 G      p            1: 2-4         Indicateur de primalité (p=1) pour n.
  8 H      q=n/F(i)     3: 3-4         Rapport pour test de primalité
  9 I      i            2: 3-4         Indice du facteur premier pour test primalité. i varie de 10 à f
 10 J=A(10)
... ...    F()          1: 3-4         Tableau mémorisant les facteurs premiers 5 7 11 ... 1061
184 A(184)   
On peut en théorie aller jusqu'aux couples de valeur 1061² = 1125721, mais je dois avoué que je n'ai pas eut la patience de tester.!

Le code est le suivant:

Code : Tout sélectionner

1:A=1,C=0,D=1,E=5,F=10,G=1,J=E                                            o21
2:B=A,A=G,G=0,E=E+2D,D=1+(D=1),I=9                                        o35
3:I=I+1,H=E/A(I):IF H>A(I) IF H<>INT H GOTO 3                             o43
4:IF H<A(I) LET G=1,F=F+(F<184),A(F)=E:IF B LET C=C+1:PRINT E-6;E;" #";C  o55
5:GOTO 2                                                                  oo5
                                                                   Total: 159 octets
P.S.: Pour ceux qui auraient la patience infinie de tester au-delà des n millionnaires, la dernière ligne peut être remplacée par un test d'arrêt du style n<1061² évitant au PC-1211 d'afficher de faux couples sexy.
Par exemple
5:IF H<1061 GOTO 2
tout en veillant à ne pas dépasser 160 octets au risque de perdre un registre et de ne plus pouvoir mémoriser 1061 !!
Mais bon, comme il faut plusieurs jours pour arriver à ces millions, cela n'a pas d'intérêt pratique.
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: Misez p'tit Optimisez n°70 : les couples sexy

Message par Gilles59 »

@c.ret: il manque le smiley "clap clap clap". Ou en un mot : Bravo !
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 »