Enigme Nombres premiers d'addition 2/2 @ Prise2Tete

nodgim · #26

Scarta, c'est bon également, bravo à toi.

Si tu te sens inspiré par le second problème, avec les chiffres binaires, n'hésite pas...

scarta · #27

Si j'ai bien compris, tu veux pareil mais en changeant + par | (bitwise or) dans les deux lignes sums[...+...]
Je te donnerai le résultat demain quand j'aurai mon ordi sous la main mais d'instinct je dirais que le résultat doit être sensiblement plus grand

enigmatus · #28

nodgim #20 a écrit:
Avec combien de bits minimum peut on faire une liste de 1000 nombres binaires conformes à cette contrainte ?

En regardant ce qui se passe pour des petits nombres, j'aurais tendance à dire 999 bits.
Un des choix pour les 1000 nombres est alors : 0 et 999 nombres dont 1 seul bit vaut 1.

nodgim · #29

Salut Enigmatus,
J'ouvre un autre sujet spécifiquement à cette question. Elle le mérite largement.

nodgim · #30

Merci à tous les participants. Tous, vous avez trouvé le bon algorithme qui conduit au résultat. Cette énigme n'avait bien qu'une seule solution, puisque la contrainte invitait à tester les nombres dans l'ordre naturel. Et il semble peu probable qu'on puisse arriver à un meilleur résultat (moins que 13 millions et des... ) en s'y prenant autrement.

J'ai ouvert tantôt une autre discussion sur un sujet à peu près identique avec la "superposition de nombres binaires". Mais ce nouveau sujet est d'une toute autre dimension....

scarta · #31

Je viens de voir les temps d'execution de dhrm et enigmatus : pour info le code que j'ai posté donne la 1000ème réponse en moins d'une seconde.

nodgim · #32

Super, Scarta.
Tu ne peux plus nous laisser comme ça sans dévoiler comment est conçu ton programme....

scarta · #33

Ben le code est dans mon post précédent...

nodgim · #34

Ah oui, pardon.
Il est très performant, en effet !

dhrm77 · #35

@scarta: Sur quelle machine et quel compiler as tu utilisé pour faire ce programme?
Sur ma machine je n'ai pas de Booleen. Quand j'utilise des octets l'adaptation de ton programme prend 2.04 secondes et 3.576 secondes quand j'utilise des bits, au lieu de moins d'une seconde chez toi.

scarta · #36

Toutes les machines ont boolean, c'est juste une question de langage et de compilation.
Bref, c'est du C#, compilé pour Windows sur mon PC professionnel, un Dell je sais plus combien, modèle "spécial développeurs" 2015. Pas une bête de course, mais très rapide quand même.
J'imagine que c'est aussi compilable sur Mono

shadock · #37

Je suis toujours en train d'essayer de comprendre l'énoncé...

nodgim · #38

@shadok:
tu prends les nombres dans l'ordre et tu fais toutes les additions possibles de 2 de ces nombres:
0
1-----> 1+0=1
On essaye avec 2 : 2+0=2 et 2+1=3. Ces 2 sommes sont différentes des sommes déja calculées (ici 1 seulement). Donc 2 convient.
3 ne convient pas car 3+0=3 or 3 est déja une somme.
4+0=4 4+1=5 4+2=6
4 convient
5 et 6 ne conviennent pas.
etc....

dhrm77 · #39

@scarta:
Ma version de ton programme est écrit en C sur Linux, compilé avec GCC, qui ne semble pas optimiser aussi bien que certains autre compilateurs. J'arrive a 4.294.967.280 en un peu plus de 8 heures.

@shadock:
L'énoncé n'est pas tres compliqué. On construit une liste de nombres tels que la somme du nombre que l'on test (pour savoir si c'est le suivant) avec un autre nombre quelconque de la suite soit une somme que l'on ne sait pas deja faire avec 2 autres nombre de la suite.
Donc prenons la suite de l'énoncé: 0, 1, 2, 4, 7... Le prochain terme:
- n'est pas 8 parce que 8+0=7+1
- n'est pas 9 parce que 9+0 = 7+2
- n'est pas 10 parce que 10+1 = 7+4
- n'est pas 11 parce que 11+0 = 7+4
- est 12 parce que:
12+0 n'est pas faisable avec 0, 1, 2, 4 et 7.
12+1 n'est pas faisable avec 0, 1, 2, 4 et 7.
12+2 n'est pas faisable avec 0, 1, 2, 4 et 7.
12+4 n'est pas faisable avec 0, 1, 2, 4 et 7.
12+7 n'est pas faisable avec 0, 1, 2, 4 et 7.

Voila....

shadock · #40

Ah ok merci beaucoup !

scarta · #41

@dhrm: le gros soucis de mon algorithme, c'est qu'il n'est pas fait pour être fonctionnel pour des grandes valeurs. Il n'utilise pas une liste des sommes rencontrées mais un tableau de bits, 0 si la somme n'a pas été rencontrée et 1 sinon.
Ça permet de savoir si une somme est un doublon en temps constant, infiniment plus rapide que n'importe quelle liste / tableau / sorted list / hashmap...
Autrement dit, pour monter à 2^32, il faudrait un tableau de 2^33 bits, soit 8gigas de ram. Ça reste possible, sur une architecture 64 bits, et une bécane un peu gonflée, ceci dit mon ordi ne pourra pas monter aussi haut...

Forum dédié aux énigmes et à toutes formes de jeux de logique.	Déconnexion
Tu n'es pas identifié sur Prise2tete : s'identifier. Accueil Forum	[+]

#26 - 03-05-2016 17:43:07

nombres premiers d'additipn

#0 Pub

#27 - 04-05-2016 00:25:13

Nombres premiers d'addtion

#28 - 04-05-2016 07:22:09

Nombres prmiers d'addition

nodgim #20 a écrit:

#29 - 04-05-2016 07:52:02

Nombrres premiers d'addition

#30 - 04-05-2016 13:08:46

Nombres prremiers d'addition

#31 - 04-05-2016 16:21:14

Nombbres premiers d'addition

#32 - 04-05-2016 17:24:04

nombres przmiers d'addition

#33 - 04-05-2016 17:36:51

nombres premiers d'additoon

#34 - 04-05-2016 18:33:44

Nombres premiers dd'addition

#35 - 05-05-2016 03:34:05

Nombres premiers d'additiion

#36 - 05-05-2016 08:22:22

Nombbres premiers d'addition

#37 - 05-05-2016 14:06:10

Nombres premiers d'additon

#38 - 05-05-2016 18:42:19

nombres premiets d'addition

#39 - 05-05-2016 19:00:20

Nombres premiers d'dadition

#40 - 05-05-2016 22:03:46

Nombres premiers d'additon

#41 - 06-05-2016 00:45:01

Nmobres premiers d'addition

Réponse rapide

Sujets similaires

Mots clés des moteurs de recherche

Pied de page des forums