Répondre à la discussion
Page 1 sur 6 12 3 4 5 DernièreDernière
Affichage des résultats 1 à 30 sur 166

Nombre premier sans "calcul"

  1. #1
    SPH

    Nombre premier sans "calcul"

    Je crois que j'ai fais une tres grosse trouvaille mathematique :
    Je sais tester un nombre pour voir s'il est premier sans me soucier des NP precedents !

    Cela existe t'il deja ?

    Les calculs sont tres rapides (peut etre 1000 fois plus rapide que ceux actuels). DITES MOI TOUT.

    Merci

    -----


  2. Publicité
  3. #2
    GuYem

    Re : Nombre premier sans "calcul"

    Cela n'existe pas à ma connaissance.
    Tu comprendras cependant mon scepticisme sachant que des millions de mathématiciens se cassent la tête depuis des lustres à essayer de décoincer ce problème des nombres premiers.
    Cependant aprés tout si tu as bien trouvé une idée originale alors grosse félicitations à toi!
    Bravo jolie Ln, tu as trouvé : l'armée de l'air c'est là où on peut te tenir par la main.

  4. #3
    DanielH

    Re : Nombre premier sans "calcul"

    SPH:
    Je sais tester un nombre pour voir s'il est premier sans me soucier des NP precedents !

    Cela existe t'il deja ?
    Comment crois-tu que les grand nombre premiers sont prouvés. La connaissance des nombres premiers précédants n'est pas indispensable, on s'en serre que pour réduire le nombre de candidats.

  5. #4
    SPH

    Re : Nombre premier sans "calcul"

    Bon, guyem et daniel ne sont pas daccord; ca commence bien. Mais je pense que c'est guyem qui a raison.
    Martini bird ??

  6. #5
    GuYem

    Re : Nombre premier sans "calcul"

    Attention je suis une quiche en arith!
    Je pense plutôt que c'est Daniel qui a raison.
    Bravo jolie Ln, tu as trouvé : l'armée de l'air c'est là où on peut te tenir par la main.

  7. #6
    Le_boulet

    Re : Nombre premier sans "calcul"

    Citation Envoyé par SPH
    Je crois que j'ai fais une tres grosse trouvaille mathematique :
    Je sais tester un nombre pour voir s'il est premier sans me soucier des NP precedents !

    Cela existe t'il deja ?

    Les calculs sont tres rapides (peut etre 1000 fois plus rapide que ceux actuels). DITES MOI TOUT.

    Merci
    Bien sûr que ça existe. Il suffit de tester la divisibilité de n'importe quel nombre impair n, par 3, puis par pas de 6 par p, jusqu'a racine(n)+1, par les valeurs 6p+1, et 6p+5.

    Par contre, je ne suis pas certain que ça soit le plus rapide. Mais si tu ne précises pas ton algo, on ne pourra pas vraiment avoir un esprit critique dessus

  8. #7
    SPH

    Re : Nombre premier sans "calcul"

    Citation Envoyé par Le_boulet
    Bien sûr que ça existe. Il suffit de tester la divisibilité de n'importe quel nombre impair n, par 3, puis par pas de 6 par p, jusqu'a racine(n)+1, par les valeurs 6p+1, et 6p+5.

    Par contre, je ne suis pas certain que ça soit le plus rapide. Mais si tu ne précises pas ton algo, on ne pourra pas vraiment avoir un esprit critique dessus
    Mon algo est en cours d"étude. J'ai encore quelques trouvailles a pauffiner...
    PS : je pense que mon algo réduit le nombre d'opération de 90% !

  9. #8
    Prokofiev

    Re : Nombre premier sans "calcul"

    Il existe de nombreux tests de primalité de tous types (déterministes ou probabilistes).
    Aucun ne requiert de connaître les nombres premiers inférieurs.
    Jete un oeil à ceci :
    http://mathworld.wolfram.com/PrimalityTest.html

  10. #9
    GuYem

    Re : Nombre premier sans "calcul"

    Citation Envoyé par SPH
    Mon algo est en cours d"étude. J'ai encore quelques trouvailles a pauffiner...
    PS : je pense que mon algo réduit le nombre d'opération de 90% !
    Il réduit le nombre d'opération de 90% par rapport à quelle technique?
    Bravo jolie Ln, tu as trouvé : l'armée de l'air c'est là où on peut te tenir par la main.

  11. #10
    SPH

    Re : Nombre premier sans "calcul"

    Citation Envoyé par GuYem
    Il réduit le nombre d'opération de 90% par rapport à quelle technique?
    par rapport au criblage de mersenne

  12. #11
    Pole

    Re : Nombre premier sans "calcul"

    Tu peux dire ton algo sans les améliorations. Dis aussi le plus grand P que tu as trouvé.
    Pour comprendre la récursivité croisée, il faut comprendre les arbres d'appels. Et vice versa.

  13. #12
    evariste_galois

    Re : Nombre premier sans "calcul"

    Citation Envoyé par Pole
    Tu peux dire ton algo sans les améliorations. Dis aussi le plus grand P que tu as trouvé.
    Il va sûrement pas dévoiler son algo sur un forum, il faut faire une annonce officielle, pour ne pas que quelqu'un lui pique son idée.
    Après, direction un des amphis du MIT où une centaine de chercheurs, parmi les plus reconnus du monde, l'attendront comme le messie, et où il révélera sa trouvaille. J'ai tout juste SPH?
    "Au train où vont les choses, les choses où vont les trains ne seront plus des gares."

  14. #13
    SPH

    Re : Nombre premier sans "calcul"

    Citation Envoyé par evariste_galois
    Il va sûrement pas dévoiler son algo sur un forum, il faut faire une annonce officielle, pour ne pas que quelqu'un lui pique son idée.
    Après, direction un des amphis du MIT où une centaine de chercheurs, parmi les plus reconnus du monde, l'attendront comme le messie, et où il révélera sa trouvaille. J'ai tout juste SPH?
    oui

    mais ca ne m'empechera pas de mettre un programme a votre disposition.
    ps : pour l'instant, ma routine est limité a 2 milliard car c'est tjr pareil en informatique. Mais ca peux s'ettendre a bocou plus.
    Ha oui, j'allais oublier : ma routine trie les NP qui n'ont aucune incidence pour un crible de mersenne, et les NP qui ont une influence en crible.
    ex:
    40009 : Premier et Cribleur de Mersenne 'strange'
    40013 : Premier
    40031 : Premier et Cribleur de Mersenne
    40037 : Premier
    40039 : Premier et Cribleur de Mersenne
    40063 : Premier et Cribleur de Mersenne
    40087 : Premier et Cribleur de Mersenne
    40093 : Premier
    40099 : Premier
    40111 : Premier et Cribleur de Mersenne
    40123 : Premier
    40127 : Premier et Cribleur de Mersenne
    40129 : Premier
    40151 : Premier et Cribleur de Mersenne 'strange'
    40153 : Premier et Cribleur de Mersenne 'strange'
    40163 : Premier
    40169 : Premier et Cribleur de Mersenne 'strange'
    40177 : Premier
    40189 : Premier
    40193 : Premier
    40213 : Premier
    40231 : Premier et Cribleur de Mersenne
    40237 : Premier
    40241 : Premier et Cribleur de Mersenne 'strange'
    40253 : Premier
    40277 : Premier
    40283 : Premier
    40289 : Premier
    40343 : Premier et Cribleur de Mersenne
    40351 : Premier et Cribleur de Mersenne 'strange'
    40357 : Premier
    40361 : Premier et Cribleur de Mersenne 'strange'
    40387 : Premier
    40423 : Premier et Cribleur de Mersenne
    40427 : Premier
    40429 : Premier
    40433 : Premier et Cribleur de Mersenne 'strange'
    40459 : Premier
    40471 : Premier et Cribleur de Mersenne 'strange'
    40483 : Premier
    40487 : Premier et Cribleur de Mersenne
    40493 : Premier
    40499 : Premier
    40507 : Premier
    40519 : Premier et Cribleur de Mersenne
    40529 : Premier
    40531 : Premier
    40543 : Premier et Cribleur de Mersenne
    40559 : Premier et Cribleur de Mersenne
    40577 : Premier
    40583 : Premier et Cribleur de Mersenne
    40591 : Premier et Cribleur de Mersenne 'strange'
    Dernière modification par SPH ; 08/09/2005 à 19h04.

  15. #14
    Le_boulet

    Re : Nombre premier sans "calcul"

    Citation Envoyé par evariste_galois
    Il va sûrement pas dévoiler son algo sur un forum, il faut faire une annonce officielle, pour ne pas que quelqu'un lui pique son idée.
    Après, direction un des amphis du MIT où une centaine de chercheurs, parmi les plus reconnus du monde, l'attendront comme le messie, et où il révélera sa trouvaille. J'ai tout juste SPH?
    Vous vous rendez compte ! On est peut-être en train de discuter avec un futur Médaille Field ...

  16. #15
    Moma

    Re : Nombre premier sans "calcul"

    Salut,

    êtes-vous aller jeter un oeil au lien proposé ? Les méthodes qui ne s'occupent que du nmbre à tester sont légions, et pas toutes déterministes. Voire par exemple la page de François Morain pour un test efficace qui prouve la primalité de nombres ayant environ 300 chiffres (pour les nmbres quelconque, mais certains nmobres ayant une forme particulière et possédant un bon millier de chiffre ont été prouvé premier par ce test) : http://www.lix.polytechnique.fr/Labo/Francois.Morain/

    Pour être franc (et après avoir lu plusieurs discussions sur ce même forum), je suis un peu sceptique... M'enfin, je peux me tromper évidement

    Amicalement
    Moma

  17. #16
    tigli

    Re : Nombre premier sans "calcul"

    bonjours tous,
    sph ,
    pour les nombres de Mersenne on utilise le test de Lucas-Lehmer pour determiner si ils sont premiers ou pas .C'est tres rapide.
    je serais curieux de savoir ce que vous avez trouvé ...

  18. #17
    Pole

    Re : Nombre premier sans "calcul"

    Regarde au "nombre de Mersenne" et "Sécurité de l'état..etc"(assez loin).
    Pour comprendre la récursivité croisée, il faut comprendre les arbres d'appels. Et vice versa.

  19. #18
    SPH

    Re : Nombre premier sans "calcul"

    Mes methodes determinent avec une certitude totale si un nomnre est premier. Actuellement, comme tjr en informatique, je me creuse la cervelle pour contourner cette fichue limite 32 bits. C'est ca le plus dur.

  20. #19
    SPH

    Re : Nombre premier sans "calcul"

    Moi, j'affirme que ce n'est pas la peine de tester tous les nombres premiers pour savoir si un nombre de mersenne est premier. Il n'y a que 40% des NP qui ont une incidence dans le criblage d'un nombre de mersenne. Tiens, par exemple, j'AFFIRME que les np 3; 5 et 11 pour ne citer qu'eux ne pourront JAMAIS cribler un mersenne. Et c'est comme ca pour 60% des NP

  21. #20
    Moma

    Re : Nombre premier sans "calcul"

    Salut,

    même si tu élimine 60% des nombres, un crible restera trop lent. Tu devra quand même testé un nombre de nombre premier de l'ordre de , ce qui n'est pas du tout polynomial en , tu me l'accorderas. Ainsi, même ton crible amélioré va très vite faiblir quand les nombres vont commencer à grossir un peu...


    Amicalement
    Moma

  22. #21
    leg

    Re : Nombre premier sans "calcul"

    cela veux tous implement dire, que peut être ta méthode passant par l'utilisation de nombre premier pour tester un Mersenne sera inutilisable car trop lente ou alors l'obilgation de créer une banque de donnée qui dépasse les capacités d'un pc,
    Même un programe qui ne ferait pas appel a des Premier, il ferra appel à une méthode similaire ou les nombre sont remplacé par des . ou des , ou des 0 ou encore des signes, mais il t'en faudras une telle quantité pour atteindre ta cible, que le résultat revien au même. ce que je ne comprend pas cest pourquoi tu ne teste pas un nombre de 33 chiffre qui rentre dans n'importe quel programme et tu nous donne le résultat ou une comparaison avec un autre test...
    A+

  23. #22
    leg

    Re : Nombre premier sans "calcul"

    SPH, j'AFFIRME que les np 3; 5 et 11 pour ne citer qu'eux ne pourront JAMAIS cribler un mersenne. Et c'est comme ca pour 60% des NP : faux,
    ce n'est pas par ce que 3 ne divise pas directement Mersenne qu'il ne le crible pas d'une autre manière,de plus 3 divise tous les mersennes sous cette forme: (Mq - 1)/2. ce qui donne des idées

    __________________
    11*2+1, crible 2^11-1;
    23*2 + 1crible 2^23 -1
    (3+113)*2 +1 crible 2^29 -1
    (37*3)*2 +1 crible 2^37 - 1

    (Mq - 1)/ 2 a des facteur P qui permettent de retrouver le plus petit facteur P divisant Mq tel que ce facteur p est la différence entre A - B de sorte que A² - B² = Mq composé! est: le grand facteur P ou composé / 2 est un nombre N ,qui se situe entre A et B, donnant par exemple A - N = (petit facteur P) /2; qui se trouve grace aux facteurs Premiers de (Mq - 1)/ 2. alors, tu vac me demander pourquoi?
    pour l'instant je te dirai : parce que N, divise aussi (Mq - 1)/ 2 et le quotien = (petit facteur P) /2...... curieusement pour l'instant on utilise 3 et l'exposant ou un des petits facteurs P, obtenus par les carrés de (Mq - 1)/ 2. ex pour 2^29 -1 = (U² -V²)/2
    V est toujours = 2
    U=32768 V=2, u'=16385, et v'=16383,
    16383/5/29/113
    16383/3/43/127

    113 = a et (43*127) = b qui me permettent de remonter et trouver A et B tel que A² - B² = 2^29 -1.

  24. #23
    SPH

    Re : Nombre premier sans "calcul"

    Leg, tu te bases sur des calculs qui ne sont pas a toi. Quand a moi, j'affirme que "3" ne peux pas cribler un potentiel mersenne.

    Prend cette liste et continue la si ca te dit d'essayer de prouver ce que tu dis et tu verras :

    Nombre de mersenne premier ou non (4x+3) :
    7
    31
    127
    511
    2047
    8191
    32767
    131071
    524287
    2097151
    8388607
    33554431
    134217727

    Le np 3 et son crible (9; 15; 21; 27,...) ne condamneront jamais un mersenne

  25. #24
    tigli

    Re : Nombre premier sans "calcul"

    bonjour,
    sph,
    3 ne crible effectivement pas les nombres de mersenne a exposant premier
    3 divise 2²-1, donc il divise tous les 2^2a-1 c'est a dire les exposants pairs , il en est de meme pour la liste de nombres premiers que vous avez fournie sur un autre fil.
    la remarque precedente sur la rapidité d''un tel crible est exacte sph .
    bon courage jeune homme

  26. #25
    SPH

    Re : Nombre premier sans "calcul"

    Citation Envoyé par Moma
    Salut,

    même si tu élimine 60% des nombres, un crible restera trop lent. Tu devra quand même testé un nombre de nombre premier de l'ordre de , ce qui n'est pas du tout polynomial en , tu me l'accorderas.
    Je dirais plutot que je devrais tester seulement 40% de . Est-ce polynomial en maintenant ?

  27. #26
    Pole

    Re : Nombre premier sans "calcul"

    non
    Pour que ça soit polynomial, il faut que la complexité soit du type a^b avec a qui change (et qui est égal au nombres de chiffres de ton nombre) et b constant.
    Et toi (pour x), c'est 2/5*sqrt(x) et pour le nombre de chiffres (en base 10): 2/5*sqrt(10^x)=2/5*10^(x/2)~=10^(x/2). Comme x (en exposant) varie, ton algo n'est pas polynomial.
    Pour comprendre la récursivité croisée, il faut comprendre les arbres d'appels. Et vice versa.

  28. #27
    leg

    Re : Nombre premier sans "calcul"

    sph il ne faut pas être aussi tétu,
    l'exemple que je t'ai donné ce sont bien mes calcul tu n'a qu'a relire le fil mersenne en plus c'est une question que tu m'as posé .
    ceci dit, tu ne fais pas attention a ce que l'on te dis ...
    un nombre de mersenne est congrue 1 ou 7 modulo 30 donc il ne peut être multiple de 3 , j'ai mis les modulo en fonction de l'exposant mais tu regardes la ou bon te semble
    regarde ce que 3 divise c'est un nombre de Mersenne - 1 et divisé par 2..
    ce que j'ai mis pour les exposant 11,23,29,37, c'est une constatation si tu regarde le facteur P = 164511353 qui divise Mq exposant 41,ce qui te donne 13367
    (Mq - 1)/2 que divise a nouveau P tu obtiens 6683.5 .
    en connaissant les facteurs P de (Mq - 1)/2 j'essais de remonter afin de trouver deux carrés A et B ou de retrouver une approche de 6683,5 .

  29. #28
    SPH

    Re : Nombre premier sans "calcul"

    Citation Envoyé par leg
    SPH, j'AFFIRME que les np 3; 5 et 11 pour ne citer qu'eux ne pourront JAMAIS cribler un mersenne. Et c'est comme ca pour 60% des NP : faux
    A question claire, réponse claire
    Pourtant, ma question est VRAI et ta reponse est FAUSSE

    PS : je tiens compte de ce qu'on me dit mais pas de ce que tu dis car je ne comprend jamais rien a ce que tu racontes. J'ai beau lire et relire tes posts, j'ai toujours l'impression que tu sautes du coq a l'ane a chaque instant. Par contre, je fais confiance a pole et a martini par exemple... Et pour moi, c'est pole qui a 57 ans, et toi, tu dois en avoir 12... (vous voyez, on reste dans les nombres !! )

  30. #29
    Moma

    Re : Nombre premier sans "calcul"

    Salutations,


    J'avoue que je comprends pas tout de que vous dizez (SPH particulierement, mais leg toi aussi parfois.........).

    Mais pour reprendre ta question, et pour préciser ma pensée sur les algorithme polynomiaux, je vais définir et expliuer calmement.

    Un algorithme "arithmétique" est dit polynomial si sa complexité (en gros le temps qu'il met à donner la réponse par rapport à la taille des données) est un polynome en où n est le nombre donné. C'est à dire que c'est un polynome en le nombre de bit necessaires pour écrire le nombre en mémoire.

    Comme l'a très bien rxlpiqué Pole, un algorithme en n'est pas polynomial mais "exponentiel". C'est à dire que c'est l'exposant qui varie. On considère généralement que ce sont les algos polynomiaux qui sont efficaces (et c'est vrai en pratique, les tests étant plus que nombreux et les contres-exemples inexistant ).

    C'est une des raisons qui font que les criles ne sont pas utilisés saèf pour les "petits" nombres. Les recherches dans ce sens sont presques inutiles, vu qu'un "bon" progres ne serait utile que pour des nombres plutôt raisonnables. L'augmentation de la taille serait fatale.

    Garde ben en mémoire que l'unité de masure est le nombre de chiffres (proportionnel à ).


    En espérant t'avoir éclairé etmis sur la bonne voie
    Amicalement,
    Moma

  31. #30
    Pole

    Re : Nombre premier sans "calcul"

    leg : (Mq-1)/2=Mq-1
    Pour comprendre la récursivité croisée, il faut comprendre les arbres d'appels. Et vice versa.

Page 1 sur 6 12 3 4 5 DernièreDernière

Discussions similaires

  1. Actu - En images : Genesis 2, premier "casino" de l'espace, est lancé !
    Par RSSBot dans le forum Commentez les actus, dossiers et définitions
    Réponses: 8
    Dernier message: 03/07/2007, 19h58
  2. calcul d'écart "relatif", "type" ?
    Par audioslave227 dans le forum Mathématiques du supérieur
    Réponses: 17
    Dernier message: 29/08/2006, 12h54