Enigme Multiple de 7 parfait 2/2 @ Prise2Tete

MthS-MlndN · #26

J'en ai une version en train de tourner... Seigneur, ça va vite ^^ Pourtant, j'ai codé ça comme un cochon...

Apparemment, mon programme renvoie les mêmes résultats que celui de Bamby. Nickel.

Quelques dépassements de capacité plus tard, on redéfinit les entiers longs, et on y retourne

Résultats dans quelques minutes/heures

Yanyan · #27

SAigneur Mathias ne pourrais-tu pas faire mes produits avec tes machines rutilantes ?
Merci.

nodgim · #28

scarta a écrit:
Pour la division par 7 (et pour quasiment tous les nombres que j'ai donné sauf cas particuliers), la méthode est la même: écrire une liste des petits multiples de 7, essayer ensuite d'en composer un certain nombre avec des chiffres tous différents.

Pour la "question++", j'ai trouvé un résultat par analyse avec un PC pour aider quand même (ne serait-ce que pour avoir une liste de premiers); mais j'ai quand même utilisé un PC ensuite pour vérifier que ce résultat était le plus petit possible.
L'idée était la suivante: si j'ai un premier avec un nombre important de 1 successifs (par rapport à la taille du nombre), j'ai de fortes chances pour que ses multiples aient des chiffres similaires (à condition qu'il y ait plus de 1 successifs que de chiffres dans le nombre avec lequel je multiplie).
Des premiers avec que des 1 dans la limite qui nous intéresse, il n'y a que 11 (le suivant est 1111111111111111111; trop long)
Du coup, je cherchais les nombres Z de la forme "1Nfois puis X" tels que N soit supérieur ou égal au nombre de chiffres de 987654321/Z. J'ai donc pu voir que N devait valoir au moins 5. Comme on cherche le plus petit, j'ai démarré avec N=5; et j'ai trouvé un nombre premier qui marche : 111119
J'ai ensuite vérifié par ordinateur que c'était bien une bonne solution et qu'elle était bien la plus petite.

Excellent!

Yanyan · #29

Personne n'est intéressé par le calcul de mes produits ou bien vous n'avez rien compris ou bien vous trouvez ça sans intérêts?

nodgim · #30

Pardon Yanyan mais perso je n'ai pas fait assez d'étude pour comprendre ce que tu as écrit.

Yanyan · #31

Tu prends un polynôme et tu permutes ses coefficients ensuite tu multiplies ces polynômes entre eux.

[latex](aX^2+bX+c)(ax^2+cX+b)(bX^2+aX+c)(bX^2+cX+a)(cX^2+aX+b)(cX^2+bX+a)[/latex] pour n=3 , 6 permutations.

Bamby2 · #32

j'ai passé la liste des nombre premier jusqu'à 1 millions sur le site proposé par Nodgim.

et il en existe 779 pour qui ca ne marche pas.
le plus petit étant : 111119
j'ai les résultats dans un fichier, mais le site refuse de l'uploader:
"
Le nom de fichier n'est pas correct
(Il est soit trop long, soit contient des caractères illégaux comme des accents ou des espaces)
"

en même temps il fait 1.4Mega, c'est que ca en fait des nombres premiers (78498)

Et quitte a être dans les chiffres, l'exécution a prit 159sec sur un PC moisit, en java sous eclipse.

EDIT, je viens de voire la limitation à 500k, j'ai coupé au premier premier qui ne divise pas un parfait (111119) ca permet d'avoir les résultats pour les précédents pour vérifier.
http://www.prise2tete.fr/upload/Bamby2- … 111119.txt

MthS-MlndN · #33

Sur une meilleure machine, le mien a mis trois minutes environ pour arriver jusqu'au nombre 111119, le premier premier qui ne marche pas.

Tu peux uploader ton fichier sur un site extérieur pour faire plaisir aux curieux

Et peux-tu nous montrer ton code ? Je suis très curieux (et épaté par tes perfs !)

@Yanyan : casse-tête algorithmique de première, je ne m'attaque pas a un tel sac de nœuds

Yanyan · #34

Tu n'aurais pas une fonction "développe" pour faire le cas n=3?

MthS-MlndN · #35

Je viens de penser a un truc.

Le développement de ton giga-polynôme pour une valeur donnée de n sera le développement d'un polynôme produit de n! polynômes de degré n-1, n! étant le nombre de permutations différentes des n coefficients.

Tu auras donc [latex]n^{n!}[/latex] termes dans ton développement, avant réduction. Tu dois pouvoir compter le nombre de ces termes qui font apparaître un certain nombre de fois chaque coefficient (avec de la combinatoire basique) et tu peux connaître directement le degré en X de chacun de ces termes...

De la, tu peux sans doute calculer "simplement" le coefficient de chaque X^p, non ?

Bamby2 · #36

mon code n'a absolument rien d'extraordinaire,
voici mon fichier .java, avec .txt ajouter pour l'upload.
http://www.prise2tete.fr/upload/Bamby2- … m.java.txt
le fichier lu est un copier/coller de la liste du site de Nodgim des premiers jusque 1 million.

j'ai modifier légèrement pour écrire dans un fichier directement, (4 lignes d'ajouter) car l'affichage sous eclipse fait ramer un truc de fou.(ca descend à 104sec pour les 78498 premiers premier).

MthS-MlndN · #37

L'affichage fait toujours ramer les codes... C'est stupéfiant a quel point ça peut fausser des performances.

Et en effet, le code n'a rien d'extraordinaire. Il est seulement propre

nodgim · #38

Bon je sais pas trop lire ce langage, mais je suis étonné que ce soit aussi court!

Franky1103 · #39

Yanyan a écrit:
Tu prends un polynôme et tu permutes ses coefficients ensuite tu multiplies ces polynômes entre eux.

[latex](aX^2+bX+c)(ax^2+cX+b)(bX^2+aX+c)(bX^2+cX+a)(cX^2+aX+b)(cX^2+bX+a)[/latex] pour n=3 , 6 permutations.

Je veux bien essayer, mais à vrai dire, je ne vois pas trop où tu veux en venir.
Si on développe ce polygône, on aura 3^6 = 729 termes, ça risque de devenir vite lourdingue.
Allez je commence: les termes devant x12 et 1 sont les mêmes a²b²c²

Yanyan · #40

Cela fait un moment que j'ai attrapé le monstre avec maple mais impossible de copier le résultat ça fait 20 minutes que ça copie et rien.
Je ne peux pas partager le résultat.

Yanyan · #41

Soit p un nombre premier et [latex]P_{\sigma}(10)=\sum_{i=0}^{9}(\sigma(i)-1) 10^i[/latex] pour une permutation [latex]\sigma[/latex] du groupe symétrique à 10 éléments.

Puisque p est premier l'application dans le corps à p éléments qui à x associe a.x est une bijection pour a non nul, autrement dit on peut passer d'un [latex]P_{\sigma_0}(10)[/latex] non nul fixé à [latex]P_{\sigma}(10)[/latex] par multiplication par un élément noté [latex]n_{\sigma}[/latex].
Or il est clair que [latex]n_{\sigma_1 \sigma_2}=n_{\sigma_1}n_{\sigma_2}[/latex] et puisque toute permutation est produit de transpositions on arrive au résultat suivant :

Soit un nombre composé de tous les chiffres de 0 à 9 une et une seule fois qui est non nul modulo p alors il existe un nombre du même type nul modulo p si et seulement si un des nombres obtenus en échangeant seulement deux chiffres dans le nombre de départ est nul modulo p.

Je pense que cela réduit les calculs pour trouver le fameux p de la question ++.

Qu'en pensez-vous?

nodgim · #42

"Soit un nombre composé de tous les chiffres de 0 à 9 une et une seule fois qui est non nul modulo p alors il existe un nombre du même type nul modulo p si et seulement si un des nombres obtenus en échangeant seulement deux chiffres dans le nombre de départ est nul modulo p".

Si c'est vrai c'est très puissant !

Yanyan · #43

L'idée est que modulo p on peut passer d'un nombre non nul à n'importe quel autre par une multiplication. Je fixe un élément non nul modulo p par exemple 1234567890 pour passer à n'importe quel autre nombre du genre on permute or si on permute une première fois puis une seconde fois par une permutation on a multiplié entre eux les deux éléments qui envoient sur les autres.

Or si on multiplie modulo p par un élément et qu'on tombe sur 0 alors l'un des deux termes est nul, puisque ce n'est pas le nombre c'est l'élément.
On conclu par le fait que toutes permutations est produit de transpositions et encore le fait qu'un produit est nul si l'un des facteurs est nul.

Nodgim as-tu compris?
Sinon on attendra les éclairages des autres.

Yanyan · #44

IL Y A UNE ERREUR c'est bien sûr dans le "c'est clair", il aurait fallu des nombres universels qui par leur multiplication permute d'une certaine façon et ça c'est impossible car une transposition étant égale à son inverse il aurait fallu la même chose par passage au morphisme.
Désolé...

nodgim · #45

C'est faux bien sûr car si c'était vrai, pour un nombre p quelconque, il n'y aurait que C(10,2)-1=44 résultats possibles modulo p, ce qui ne pourrait expliquer qu'il faut attendre un nb à 6 chiffres pour trouver un non diviseur.

Bien essayé tout de même.

scarta · #46

j'ai vu qu'on soumettait par ici ses programmes pour trouver les solutions.
Voici le mien :

1° Générer toutes les permutations dans un tableau
2° Créer un tableau de booléens pour faire un crible pour les nombres premier
3° Pour chaque entier,
3.1° Si le crible indique qu'il est composé, on passe au suivant
3.2° Sinon:
3.2.1° On élimine du crible tous ses multiples
3.2.2° On regarde s'il divise au moins un entier de notre tableau.
3.2.3° S'il n'en divise aucun; on l'affiche et on s’arrête
3.2.4° Sinon, on passe au suivant

La génération prend environ 352ms, la recherche ensuite 8471 ms; soit donc 8.82s pour afficher 111119

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 - 04-08-2011 13:10:55

Multiple de 7 parfai

#0 Pub

#27 - 04-08-2011 13:19:17

Multiple d 7 parfait

#28 - 04-08-2011 13:22:09

Multiple de 7 arfait

scarta a écrit:

#29 - 04-08-2011 14:01:20

Multiplee de 7 parfait

#30 - 04-08-2011 14:23:03

Multiple de 7 pparfait

#31 - 04-08-2011 14:35:53

Multpile de 7 parfait

#32 - 04-08-2011 15:16:28

multiple de 7 oarfait

#33 - 04-08-2011 15:19:27

Muliple de 7 parfait

#34 - 04-08-2011 15:22:11

mumtiple de 7 parfait

#35 - 04-08-2011 15:32:13

multipke de 7 parfait

#36 - 04-08-2011 15:58:06

Multiple de 7 parafit

#37 - 04-08-2011 18:05:02

Multiple e 7 parfait

#38 - 04-08-2011 18:24:05

Multiple de 7 prafait

#39 - 04-08-2011 19:18:08

multiple de 7 pardait

Yanyan a écrit:

#40 - 04-08-2011 20:33:10

multiple dr 7 parfait

#41 - 04-08-2011 22:26:26

Mlutiple de 7 parfait

#42 - 04-08-2011 22:30:27

Multiple de 7 arfait

#43 - 04-08-2011 22:43:27

Multiple de 7 pparfait

#44 - 04-08-2011 23:02:59

Multiple de 7 parrfait

#45 - 05-08-2011 08:15:50

Multiple de 7 parrfait

#46 - 05-08-2011 18:19:32

Multiple de 7 pafrait

Réponse rapide

Sujets similaires

Mots clés des moteurs de recherche

Pied de page des forums