Enigmes

Forum dédié aux énigmes et à toutes formes de jeux de logique.

Déconnexion

Tu n'es pas identifié sur Prise2tete : s'identifier.

accueil Accueil forum Forum
[+]

 #1 - 25-08-2011 10:02:10

scarta
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 1934

Soyons concis + modiications

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

  • |
  • Répondre

#0 Pub

 #2 - 25-08-2011 11:00:49

Clydevil
Expert de Prise2Tete
Enigmes résolues : 29
Messages : 914
Lieu: Seahaven island

Soyons concis + modifiications

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 : 1934

soyons concis + modificatiobs

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

soyons convis + 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 lol
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 concis + modificationq

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 : 1934

Soyons conncis + modifications

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 + modificatiobs

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

lol 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 : 1934

Soyons concsi + modifications

Malin smile
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 + modificaions

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.

smile

 #10 - 30-08-2011 10:16:06

scarta
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 1934

qoyons concis + 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 conciss + modifications

en trichant big_smile

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 conciis + 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. big_smile comme de par hasard. Et j'égalise! que d'action!
Mouhahah. lol

 #13 - 30-08-2011 10:57:07

scarta
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 1934

soyons convis + modifications

Je crois que je vais afficher le classement uniquement, pas le score tongue
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 concis + lodifications

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 + modificatuons

Je n'ai pas essayé de programmer mais j'avais l'idée de quelque chose comme :

Code:

function concis(nombre) {
 tab = array()
 for (n = 2, n < limite_a_definir, n++) {
  racine = racine_nieme(nombre, n)
  entier = arrondi(racine)
  difference = entier^n - nombre
  if (entier > limite_taille) entier = concis(entier)
  if (n > limite_taille) n = concis(n)
  if (difference > limite_taille) difference = concis(difference)
  tab []= array(entier, n, difference)
 }
 retour tab
}

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 : 1934

Soyons ocncis + modifications

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 + modification

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 smile


"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 concis + modfiications

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 : 1934

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 smile

 #20 - 06-09-2011 23:41:06

w9Lyl6n
Professionnel de Prise2Tete
Enigmes résolues : 26
Messages : 220

soyins concis + modifications

lol
ç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 : 1934

soyons concus + modifications

Quand on a des petits doigts et des petites mains, on y va des 2 mains smile

 #22 - 07-09-2011 09:06:56

Clydevil
Expert de Prise2Tete
Enigmes résolues : 29
Messages : 914
Lieu: Seahaven island

Soyons concis + moddifications

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 tongue
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 cpncis + 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 lol


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 convis + modifications

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 :

http://loacmateo.files.wordpress.com/2010/12/mecanique_quantique3.jpg

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 tongue)

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 concos + 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 ...

Réponse rapide

Rédige ton message
| | | | Upload | Aide
:) :| :( :D :o ;) :/ :P :lol: :mad: :rolleyes: :cool:
Sécurité

Répondez à la devinette suivante : 

Le père de toto a trois fils : Pif, Paf et ?

Sujets similaires

Sujet Date Forum
P2T
Un tour de cartes par Vasimolo
14-09-2009 Enigmes Mathématiques
P2T
Concours Griego 5&6 par Promath-
24-02-2012 Enigmes Mathématiques
04-02-2017 Enigmes Mathématiques
P2T
Gâteau 35 par Vasimolo
12-02-2011 Enigmes Mathématiques
P2T
12-12-2015 Enigmes Mathématiques
P2T
Gâteau 60 par Vasimolo
08-06-2013 Enigmes Mathématiques
10-01-2013 Enigmes Mathématiques
P2T
14 = 16 par fred101274
22-12-2010 Enigmes Mathématiques
30-08-2008 Enigmes Mathématiques

Pied de page des forums

P2T basé sur PunBB
Screenshots par Robothumb

© Copyright 2002–2005 Rickard Andersson

Prise2Tete Forum Statistiques Liste des membres Hall of Fame Contact
© Prise2tete - Site d'énigmes et de réflexion.
Un jeu où seules la réflexion, la logique et la déduction permettent de trouver la solution.

Flux RSS de Prise2Tete Forum Jeux & Prise2Tete Test & Prise2Tete Partenariat et Publicité sur Prise2Tete