|
#1 - 25-08-2011 10:02:10
- scarta
- Elite de Prise2Tete
- Enigmes résolues : 49
- Messages : 1960
Soyons concis + modificatons
Considérez un instant le nombre suivant: 557 518 629 963 265 578 538 392 956 816 209 037 649 510. 70 chiffres, c'est long: il est plus rapide de le noter (2^142-4)/10, soit uniquement 12 caractères. Dans cet exemple, je suis bien entendu parti d'une formule pour ensuite afficher son nombre.
Maintenant, passons à plus dur: le nombre suivant est généré aléatoirement et fait 300 chiffres. Faites chauffer vos neurones, et essayer de trouver une expression la plus concise possible pour l'exprimer. Je met une durée assez longue pour vous permettre de chercher assez longtemps.
Règles: - 1 chiffre ou 1 symbole compte un caractère. - Les symboles autorisés sont : + - * / ( ) ^ ! Pi e [ ] . , "espace" ainsi que les lettres de l'alphabet (précisions: Pi compte pour 1, mais la fonction exp pour 2, car c'est "e^..."; par compte le nombre "e" compte pour 1) - Les crochets signifient "partie entière" - J'afficherai les classements au fur et à mesure - Je n'ai pas de résultat optimal (en fait je n'ai pas de résultat tout court, je commencerai à chercher en même temps que vous)
956 425 096 295 023 313 676 289 504 730 943 577 668 228 791 345 033 614 868 829 857 878 459 501 887 400 968 016 605 738 823 283 171 043 414 062 785 776 320 845 512 509 611 954 904 053 761 441 037 284 635 703 717 716 985 862 465 098 795 338 888 079 839 573 892 785 635 209 837 086 598 329 266 643 006 282 836 323 583 045 601 107 639 668 609 182 359 695 452 928 391 178 835 243 314 550 628 412 799 128
Classement: 1°: w9Lyl6n 2°: Scarta 2° ex aequo: Clydevil
#2 - 25-08-2011 11:00:49
- Clydevil
- Expert de Prise2Tete
- Enigmes résolues : 29
- Messages : 914
- Lieu: Seahaven island
soyons concis + midifications
Salut. Super idée cette enigme, par contre je me demande sil ne serait pas encore temps de couper un peu dans le lard, 300 chiffres c'est beaucoup (ca limite les outils utilisable comme wolfram qui fait la tête).
#3 - 25-08-2011 12:02:22
- scarta
- Elite de Prise2Tete
- Enigmes résolues : 49
- Messages : 1960
Soyons concis + modifcations
La demande de Clydevil étant légitime, je réduis la complexité: 99 chiffres seulement (plus, ça nécessiterai un outillage trop complexe)
Edit: à la réflexion, non je laisse l'ancien (désolé pour les changements à répétition)
#4 - 25-08-2011 12:22:38
- Clydevil
- Expert de Prise2Tete
- Enigmes résolues : 29
- Messages : 914
- Lieu: Seahaven island
doyons concis + modifications
Salut, Une petite estimation: En oubliant pi et e (qui ne me semblent pas utile mais de toute manière ca ne changerait que très peu qualitativement ce que je m'apprête à dire) on a en tout 18 symboles pour écrire une formule. Il faut considérer la famille des "formule d'environ 80 caractères" pour en avoir autant que de nombres de 100 chiffres (18^80 =~ 10^100), dans l'optique que bien sur toutes ces formules soient valides et en bijection parfaite avec notre ensemble de nombres à 100 chiffres. (alors qu'en pratique il y a certainement peu de formule valide et beaucoup donne le même nombre). On considérant qu'un caractère sur deux est numérique que qu'on a dans ce qui reste 1 formule valide sur 100 et en se donnant un peu de marge on peut imaginer vaguement pouvoir "formuliser" un nombre de 100 chiffres quelconque avec une formule de 95 caractères, on fera aveuglement confiance à ce 95 dans la suite de cette petite remarque. Ce qui est aussi marrant à noter c'est la proportion des nombres "très compactables", avec seulement 1 symbole de moins, soit 94 symboles on représente au mieux que 1/18 de nos nombres de 100 chiffres, et avec 80 symboles on sans doute plus de chance de gagner au loto 2 fois que d'être tombé par hasard sur un nombre de 100 chiffres à ce point compactable. Conclusion la formule sera certainement assez grosse: 95 symboles On retiendra qu'au bilan avec les symboles autorisés une formule a en moyenne une très mauvaise capacité de compression(95%...), et que tomber par hasard sur un nombre très-compactable est exponentiellement improbable...
Edit: La reflection était valable pour un énonce de 100 chiffres. A adapter.
#5 - 25-08-2011 14:33:57
- TiLapiot
- Expert de Prise2Tete
- Enigmes résolues : 16
- Messages : 852
- Lieu: au terrier ;^)
soyons cobcis + modifications
Yaka just rechercher où apparaissent les décimales "956 425 ... 799 128" dans Pi, là je suis déjà en train de tatônner dans la lonnnnngue liste http://trucsmaths.free.fr/telech/1000000.zip
ok, je sors :-))
#6 - 25-08-2011 18:26:58
- scarta
- Elite de Prise2Tete
- Enigmes résolues : 49
- Messages : 1960
Soyons concis + odifications
Bonne idée de TiLapiot (quoique irréalisable à mon avis), mais pour cela il faudrait ajouter la partie entière.
Allez du coup, j'autorise 2 symboles supplémentaires.
#7 - 26-08-2011 11:30:09
- Clydevil
- Expert de Prise2Tete
- Enigmes résolues : 29
- Messages : 914
- Lieu: Seahaven island
Soyons concis + modificaions
J'ouvre le classement avec une formule simple de 300 caractères:
956 425 096 295 023 313 676 289 504 730 943 577 668 228 791 345 033 614 868 829 857 878 459 501 887 400 968 016 605 738 823 283 171 043 414 062 785 776 320 845 512 509 611 954 904 053 761 441 037 284 635 703 717 716 985 862 465 098 795 338 888 079 839 573 892 785 635 209 837 086 598 329 266 643 006 282 836 323 583 045 601 107 639 668 609 182 359 695 452 928 391 178 835 243 314 550 628 412 799 128
mouhahaha. (Si je gagne avec ca j'explose de rire)
#8 - 30-08-2011 09:49:32
- scarta
- Elite de Prise2Tete
- Enigmes résolues : 49
- Messages : 1960
Soyons concis + modificaions
Malin Bon allez, je baisse la difficulté en étant moins restrictif sur l'énoncé
#9 - 30-08-2011 10:10:48
- Clydevil
- Expert de Prise2Tete
- Enigmes résolues : 29
- Messages : 914
- Lieu: Seahaven island
Soyons concis + modificaitons
Salut, Tu peux détailler les libertés qu'on a gagné. ".,lettres alphabet?".
Sinon avec ce probleme je me suis rendu compte de ce qu'est le hasard et l'entropie. C'est fondamental de bien saisir que même a travers une formule d'une forme donnée le nombre de digit des données numérique au sein de la formule est en moyenne égal au nombre de digits de ce qu'on vise, c'est essentiel dans la théorie de l'information. Et donc par conséquent lorsqu'on désire compacter avec ce genre de manière et bien si on met moins de donnée on ne peut espérer que par hasard avoir 1 digit en commun de plus avec la cible, de même pour 2 digit de plus etc.. Au bilan si dans notre formule on a simplement ^ et + alors on a 1 chance sur 100 de trouver un a b c tel quel a^b+c soit plus petit d'un caractère que le résultat visé (et je parle en bien sur en se limitant aux triplets qui tombent proche) Ce que je veux illustrer c'est vraiment que quelque soit l'angle d'approche il n'y a pas de raffinage possible ni de bon procède on se heurtera quoi qu'il arrive au mur de l'entropie rendant de plus en plus rare les expressions compactes de ce qu'on vise lorsqu'elles existent, et même astucieusement il faudra brute-forcer sur des dizaines de milliers de résultats pour gagner quelques digits par rapport à l'original.
C'est ca le hasard. Ça ne peut pas en moyenne se décrire de manière concise.
PS:Même avec une 100aine de symboles possibles(ce dont on est très loin dans l'énoncé) pour trouver une formule qui exprime un nombre random de 300 caractères il faut forcement en moyenne au moins 150 caractères dans la formules, car c'est infranchissable mais 100^150 fait 10^300.
#10 - 30-08-2011 10:16:06
- scarta
- Elite de Prise2Tete
- Enigmes résolues : 49
- Messages : 1960
soyons concos + modifications
Intéressant (je relirai ça à tête reposée). Pour répondre à la question: avec lettres de l'alphabet, on gagne la possibilité d'écrire des mots. 2 peut donc être écrit comme étant "1+1" ou "un plus 1" ou autre, tant que le nombre 2 est bien décrit
Mon score est de 204 avec le nouvel énoncé (et sans se fouler)
#11 - 30-08-2011 10:39:26
- w9Lyl6n
- Professionnel de Prise2Tete
- Enigmes résolues : 26
- Messages : 220
Soyons concis + modfiications
en trichant
4tJz4UnvRAiEfnFP0XLZA1LIqPhhmK1XoWZ1NSSbPCWNqMNvrFFM D5Av2zXKeoXVe1P196Jo4EHecAmu56cGfFym3MQSUvFIuwI1rJipr 85tkfz97NJ44CkpBGGOUfHgSa4m9TgGV13jdBeHM2XGVk78LoK8 UY6WBTF7jSjK en base 62
J'ai utilisé le système alphanumérique complet http://www.dcode.fr/conversion-base-n
#12 - 30-08-2011 10:42:40
- Clydevil
- Expert de Prise2Tete
- Enigmes résolues : 29
- Messages : 914
- Lieu: Seahaven island
Soyons cooncis + modifications
204! intéressant.
On remarquera que dans la version light de l'énoncé on a 41 symboles différents. Et que 41^186 = environ 10^300. Par conséquent on est sur qu'en moyenne on ne peut pas exprimer un nombre quelconque de 300 caractères en moins de 186 caractère. (Et c'est une minoration optimiste pour les raisons évoquées dans mon premier post.)
Ton 204 c'est un truc du genre:
"et6gfipuq32gvm4cs2yp3telu4xc6a5wnu6d5zwz mmy7u2y2as1zmok2d400v5ix8nxq0svfsdat0gec gezi1dgw3itbcjpp1ys5tasltni8vib4xzuagrxu etmchxt0mr1ckr608wxr1g937e6evong6rqik4bg 3rmn6hfeesm9vz1jw98v868q4u4hcg788 en base 36"
Qui fait 204 caractères. comme de par hasard. Et j'égalise! que d'action! Mouhahah.
#13 - 30-08-2011 10:57:07
- scarta
- Elite de Prise2Tete
- Enigmes résolues : 49
- Messages : 1960
Soyons concis + modificatons
Je crois que je vais afficher le classement uniquement, pas le score Sinon chapeau à w9Lyl6n qui prend la pôle position !
#14 - 30-08-2011 11:28:15
- w9Lyl6n
- Professionnel de Prise2Tete
- Enigmes résolues : 26
- Messages : 220
Soyons concsi + modifications
Plus sérieusement, je ne pense pas que l'on puisse faire beaucoup mieux que le changement de base. le nombre étant aléatoire, sans prendre trop de risque :
je parie que personne en utilisant les ~70 caractères permis n'arrivera à faire mieux que : log N / log 70 =~163 caractères (N étant le nombre à compresser)
En effet si on considère les 70^163 combinaisons de caractères utilisant ces symboles, elles recouvrent bien moins que N nombres différents (car certaines combinaisons n'ont pas de sens et on retombe plein de fois sur les même nombres). La probabilité que l'une de ces 70^163 combinaisons donne N est donc extrêmement faible.
#15 - 06-09-2011 16:22:14
- EfCeBa
- Administrateur
- Enigmes résolues : ∞+1
- Messages : 11×569
Soyons concis + modificcations
Je n'ai pas essayé de programmer mais j'avais l'idée de quelque chose comme :
C'est récursif et surement très gourmand en calcul...
Il faut ensuite parcourir tab pour chercher la chaine la plus courte possible, en n'omettant pas le fait qu'il faut rajouter 2 parenthèses lorsqu'on rentre un niveau de plus dans le tableau.
#16 - 06-09-2011 17:13:27
- scarta
- Elite de Prise2Tete
- Enigmes résolues : 49
- Messages : 1960
Soyons concis + modificattions
Pas mal comme idée.
A la base, j'étais parti sur autre chose: une sorte de couverture des entiers avec des grands nombres avec une définition de petite taille; mais si c'est plus rapide, c'est beaucoup moins efficace
#17 - 06-09-2011 17:24:47
- shadock
- Elite de Prise2Tete
- Enigmes résolues : 39
- Messages : 3334
Soyons concis + modificatioons
Moi j'ai tout de suite essayé la factorisation en nombre premier en essayant d’arriver vers un nombre du type : [latex](\sum_{i=1}^4 a_i^{n_j})+k[/latex] avec [latex]n_j[/latex] les puissances [latex]a_i \in \mathbb{P}[/latex] et [latex]k \in \mathbb{N}[/latex] de manière à ce que k soit le plus petit entier possible de la différence entre le nombre de 300 chiffres et la somme des puissances nombres premiers inférieurs à 10.
Mais trop long à faire surtout pour la factorisation en nombres premiers.
Shadock
"L'expérience est une lanterne qui n'éclaire que celui qui la porte." L-F. Céline
#18 - 06-09-2011 17:39:31
- w9Lyl6n
- Professionnel de Prise2Tete
- Enigmes résolues : 26
- Messages : 220
Soyons conciss + modifications
En fait il y a peut être une manière très courte d'écrire ce nombre : il faut étudier pour ça le programme de générateur pseudo-aléatoire qui l'a généré.
Si le programme est suffisamment court, il se compressera très bien. Mais si il s'appuie sur une liste de grand nombre pour générer le pseudo-aléatoire, là on n'est pas sûr d'avoir un bon résultat avec cette méthode.
#19 - 06-09-2011 20:42:39
- scarta
- Elite de Prise2Tete
- Enigmes résolues : 49
- Messages : 1960
soyons conciq + modifications
L'algo est le suivant: 1) je branche mon pad numérique USB (j'ai pas le clavier numérique intégré au laptop) 2) Je prends ma fille de 6 mois sur les genoux, le pad devant elle 3) Je la laisse s'exciter dessus. 4) Je supprime tous les caractères qui ne sont pas des chiffres, et j'en garde 300
Je pense pas qu'on puisse réduire ça en une formule
#20 - 06-09-2011 23:41:06
- w9Lyl6n
- Professionnel de Prise2Tete
- Enigmes résolues : 26
- Messages : 220
Soyons concis + modificattions
ça me donne quand même une idée : quand on tape "au hasard" sur le clavier, on a tendance à taper sur les touches de proche en proche, sans faire d'un coup de grands sauts. Peut être qu'on peut exploiter ça...
#21 - 07-09-2011 08:25:45
- scarta
- Elite de Prise2Tete
- Enigmes résolues : 49
- Messages : 1960
Soyons conci s+ modifications
Quand on a des petits doigts et des petites mains, on y va des 2 mains
#22 - 07-09-2011 09:06:56
- Clydevil
- Expert de Prise2Tete
- Enigmes résolues : 29
- Messages : 914
- Lieu: Seahaven island
Soyons cocis + modifications
Oui du coup si c'est un enfant (ou même n'importe quel individu) qui a généré l'aléatoire on a d'avantage de chance de pouvoir le compresser (car quelque soit le nombre de main il y aura une certaine continuité ou régularité). Faudrait faire un tableau des chaines de Markov Le pourcentage de chaque digit dans le nombre. Le pourcentage de chaque digit dans le nombre en fonction du digit précèdent. Et éventuellement d'autre quantités.
#23 - 07-09-2011 09:45:00
- SHTF47
- Imprnnçbl de Prs2Tt
- Enigmes résolues : 39
- Messages : 1629
- Lieu: Autre nom du colin
soyons cobcis + modifications
Et après avec ça vous calculerez la probabilité qu'on a de voir un singe taper au clavier un passage de la Bible sans faire de faute
La musique est une mathématique sonore, la mathématique une musique silencieuse. [Edouard HERRIOT]
#24 - 07-09-2011 18:38:50
- shadock
- Elite de Prise2Tete
- Enigmes résolues : 39
- Messages : 3334
Soyons concis + modificaions
Si on admet une manière "quantique" d'enregistrer de l'information un seul bit appelé Q-bit dans deux états en même temps :
On peut chercher une fonction qui à un nombre associe deux nombres plus petits voir trois si on a de la lumière qui vient par le haut (sur l'image). Et donc avec un couple (x;y;z) je pense qu'on peut minimiser le nombre de caractères.
Et pourquoi ne pas essayer avec les congruences ? (Maintenant que je fait spé maths vous pouvez en parler )
Je ne fais que donner des idées, par contre si qq'un connais bien les langages de programmation j'aimerai bien voir ce que ma méthode avec la factorisation en nombre premier donne. Parce que à la main....c'est trop dur et surtout trop long !
"L'expérience est une lanterne qui n'éclaire que celui qui la porte." L-F. Céline
#25 - 10-09-2011 09:11:47
- Memento
- Professionnel de Prise2Tete
- Enigmes résolues : 30
- Messages : 176
Soyons ocncis + modifications
Même avec un ordinateur, c'est très long, le nombre fait tout de même 300 chiffres. J'ai essayé (sans grand espoir) avec des applets en ligne utilisant des algorithmes pour les grands nombres mais sans résultat, heureusement ...
Mots clés des moteurs de recherche
|
|