Conway Sequence Generator [obsolete]

Miscellaneous programs and scripts, opensource or not, and sometimes, random mathematical stuff.
Kafou
Poulidor Gnomonique
Posts: 1526
Joined: Sun Aug 19, 2007 7:17 pm
Location: dans son labo
Contact:

Re: Conway's Sequence Generator

Post by Kafou »

Gamall wrote:Parce qu'en fait, je ne pensais pas utiliser la "vraie" définition d'un atome :tomates (cf la def de conway dans l'article joint, c'est le truc le plus proche de l'article original que j'ai pu trouver).
Cet article est illisible :oO
Je pensais simplement nommer mes atomes (qui du coup ne mérient pas ce nom) arbitrairement, en prenant un nombre arbitraire de premiers éléments de la suite, et exprimer les suivants en fonction de ceux-là.
Plus ou moins compris...
En regardant les chiffres, on voit que les séquences des termes de rang supérieur utilisent énormément les séquences des premiers termes.
Ben ouais c'est le principe des "atomes", non ?
En gros, je compte définir un dictionnaire, en en faisant varier la taille en fonction du rang que je veux calculer (edit: en fait ce n'est pas une bonne idée, pourquoi je m'acharne à voulir absolument coder un caractère de la suite sur un octet ? Je vais plutôt prendre une notation adhoc pour exprimer le terme de rang N en fonction de tous les termes de rang < N, on verra bien ce que ça donne) (edit 2: aie, ça ne marche bien que pour les tout premiers rangs, mais après bof bof... il y a certainement une astuce) :? L'idée que j'essaye, sans doute très maladroitement, d'appliquer, c'est exploiter la redondance de la suite.
Tu veux regrouper les atomes avec des "molécules" toujours plus grosses quoi ? (molécules qui seraient tes éléments de dico)
Il y a une redondance gigantesque dans cette suite ! Compresse un des fichiers de sortie de ton conway_output, pour rire :lol ( rang 60 et 7z, j'ai quatre millièmes :nanan???re à comparer avec le taux de 1/5 obtenu avec une mauvaise chaîne pseudo-aléatoire de 1, 2 et 3 de même longeur ! Donc cette suite a visiblement une entropie quasi-nulle !)
Muahaha, moi je te compresse l'infinité des termes de la suite sur un seul octet, voire deux bits, d'ailleurs je t'ai déjà fourni le décompresseur, un peu plus haut dans ce thread :banghead :haha :ange2 :blush Mais oui c'est hyper redondant. Ceci dit en y récléchissant 2 minutes on trouve déjà un codage bidon qui fait mieux que 1/5 :lol (coder chaque paire de chiffres sur 3 bits, la paire "33" n'existant pas) D'ailleurs dans mon prog puisque je suis un gros malade je code mes chiffres sur 2 bits, ce qui permet certaines optimisations à côté :love
Je pense que le meilleur moyen d'aller très très vite et loin dans le calcul de cette suite sans faire exploser la bécane c'est de trouver une notation compressée et une sorte de morphisme des règles de calcul du rang suivant entre la notation 123 et la notation compressée.
Mon idée était de laisser complètement tomber la notation 123 (sauf pour la sortie) en la remplaçant par les atomes de la liste (la suite qui commence avec un 3 est entièrement codable par atomes, celle qui commence avec un 1 l'est à partir de la ligne 7 ou 8 je crois).
L'ennui c'est que je n'y connais pas grand-chose en matière d'algorithmes de compression... donc je pense que je vais pas mal ramer avant de trouver une méthode satisfaisante :bobo
Je m'y connais *un petit peu* là dedans mais je vois pas exactement ce que tu veux en faire en fait :D
Avec les atomes de base, oui. Mais avec un dictionnaire adhoc on pourra exploiter la redondance de la bête :barbare Mainfestement il y a moyen. Le tout c'est de le trouver :bobo
Si tu m'expliques ton idée plus en détails et avec des exemples (et qu'elle est effectivement réalisable), je pourrai t'aider.
Oooops, pardon, j'appelais résidu tout ce qui ne peut pas s'exprimer en fonction du dictionnaire choisi; donc dans le cas des atomes de conway, tous les 12 et 3 qui restent collés à chaque élément sont des résidus pour moi. (encore que par exemple pour Rn on pourrait utiliser Ac etc :?)
Tout atome se décompose (= en passant à la ligne suivante) avec les autres atomes. Initaliser ton dictionnaire avec les 92 atomes me semble le minimum.
Bon, je suis un peu stone -- beaucoup -- (j'ai toujours du sommeil en retard), donc je pense que je vais me prendre un bouquin qui ne prenne pas trop la tête et aller au dodo, avant de voir des éléphants roses :bobo
Dit-elle, et le lendemain à 9h du mat' :
Gamall wrote:J'ai commencé à bidouiller un peu, mais pour l'instant je me bats plus avec l'encodage unicode de Java qu'avec le problème lui-même :D Mais j'auraisapô !
Héhé elle a fini par se remettre à Conway :OO
Kafou
Poulidor Gnomonique
Posts: 1526
Joined: Sun Aug 19, 2007 7:17 pm
Location: dans son labo
Contact:

Re: Conway's Sequence Generator

Post by Kafou »

A propos,
(encore que par exemple pour Rn on pourrait utiliser Ac etc )
Non. Regardons ce que ça donnerait :

Fr
-> Ac.11222113 (= Rn hein)
-> Ra.21322113
-> Fr.121113222113
-> (Ac.11322113).11123113322113
-> (Ra.2113222113).3112132123222113

On se retrouve avec deux éléments consécutifs tels que le dernier chiffre du premier est égal au premier du second, et donc le théorème n'est plus valable.

Je ne sais pas comment les atomes ont été construits, je n'ai pas lu l'article, mais ils n'ont certainement pas été choisis au hasard ! :D
Gamall
Hic sunt dracones
Posts: 4174
Joined: Fri May 26, 2006 11:09 pm
Contact:

Re: Conway's Sequence Generator

Post by Gamall »

Aïe ma tête, je ne suis plus d'accord avec une bonne partie des trucs que je pensais hier :oO
Kafou wrote:Cet article est illisible :oO
Il n'est pas très aéré, c'est vrai. Ce qui m'agace le plus c'est que j'ai 50 articles qui font référence à celui de Conway, et que je n'arrive pas à trouver l'original sur le net ! Ca me rend dingue ! Tout le monde en parle mais personne n'a pris la peine d'en mettre une version en ligne !

Parce que ce truc là, moi je veux bien: -> http://mathworld.wolfram.com/CosmologicalTheorem.html, mais il y a vraiment des trucs zarb dedans:

par exemple, essayons de reconstituer Ho... dépend de Pn... qui dépend de Ca... qui dépend de Ho ::gne

Si tu comprends quelque-chose à ça, toi, plzzz helppppp !!!

Ce qui m'emmerde, c'est que j'afvais fondé mon observation du résidus sur cette table :banghead
Kafou wrote:Tu veux regrouper les atomes avec des "molécules" toujours plus grosses quoi ? (molécules qui seraient tes éléments de dico)
En gros oui, mais je suis en train de revenir sur la plupart des points de mon idée donc...
Kafou wrote:Muahaha, moi je te compresse l'infinité des termes de la suite sur un seul octet, voire deux bits, d'ailleurs je t'ai déjà fourni le décompresseur
Moi je peux faire encore mieux: je te compresse n'importe quel fichier sur 0 bits... bien sûr, il faut que je te fournisse un décompresseur différent pour chaque fichier :foufou
Kafou wrote:(la suite qui commence avec un 3 est entièrement codable par atomes, celle qui commence avec un 1 l'est à partir de la ligne 7 ou 8 je crois).
Ce serait génial si c'était vrai :? Normalement, c'est ce que dit le théorème cosmologique (qu'il existe un N tel que toute chaine se décompose en élements après N jours).

Mais, pour ce que je voyais sur mathworld, il restait des résidus :? Donc soit leur tableau est du délire, soit c'est moi qui ai mal compris ce qu'ils ont essayé de faire.
Kafou wrote: mais je vois pas exactement ce que tu veux en faire en fait :D
Tu sais quoi ? Moi non plus :banghead

Là déjà, pour démarrer (vu que je fous en l'air mon idée de dico arbitraire, manifestement mauvaise, pour repartir sur les vrais atomes de Conway) mon objectif sera de créer un algorithme qui génère tous les atomes de Conway.

Déjà ça je pense que ça va m'occuper un bon moment, vu que c'est une définition à la "il n'existe aucun", et que je n'ai aucune idée de la taille du plus gros des atomes (donc en y allant brutalement et en testant tous les cas... je pense que je vais tomber sur un os :?)
Kafou wrote:On se retrouve avec deux éléments consécutifs tels que le dernier chiffre du premier est égal au premier du second, et donc le théorème n'est plus valable.Je ne sais pas comment les atomes ont été construits, je n'ai pas lu l'article, mais ils n'ont certainement pas été choisis au hasard ! :D
Je ne vois pas en quoi ça contredit le théorème:

J'vais résumer: je vais noter & S le successeur de la séquence S. (& = alpha dans l'article)

Par exemple & "111221" = "312211"

Et je vais noter # l'application & appliquée n fois (peu importe n>= 1).

Je note aussi + l'opérateur de concaténation. "11" + "22" = "1122" (noté point dans l'article)

Une séquence divisible est une séquence S telle qu'il existe deux séquences L et R telles que
S = L+R et # S = #L + #R
.

Et un atome, c'est une séquence indivisible du point de vue de la définition précédente.

Pour employer des gros mots, # est un automorphisme sur le group des atomes, muni de + :assassin

Bref, ça n'interdit pas que le dernier char de #L soit égal au premier de #R ;)

Et tu vois au passage la difficulté de démontrer qu'il y en a un nombre fini, a fortiori 92 :banghead

Si seulement j'avais l'article de Conway :cry
Kafou wrote:Dit-elle, et le lendemain à 9h du mat' :
J'ai dormi, entre-temps... un peu :?
Kafou wrote:Héhé elle a fini par se remettre à Conway
Et j'ai bien peur d'y laisser ma peau :bobo Et ce sera de ta faute :hum
{<§ Gamall Wednesday Ida §>}
{ Mods and Programs - Mods TES-IV Oblivion }
Gamall
Hic sunt dracones
Posts: 4174
Joined: Fri May 26, 2006 11:09 pm
Contact:

Re: Conway's Sequence Generator

Post by Gamall »

Tiens d'ailleurs... Par définition 1, 2 et 3 sont toujours des atomes (L et R doivent être non vides, j'ai oublié de préciser)... donc la table de mathworld est vraiment fausse, parce que ni 1 ni 2 n'y apparaissent, seulement 3.

Or la définition ne dépend pas du terme de départ de la suite...
{<§ Gamall Wednesday Ida §>}
{ Mods and Programs - Mods TES-IV Oblivion }
Kafou
Poulidor Gnomonique
Posts: 1526
Joined: Sun Aug 19, 2007 7:17 pm
Location: dans son labo
Contact:

Re: Conway's Sequence Generator

Post by Kafou »

Gamall wrote:Donc soit leur tableau est du délire, soit c'est moi qui ai mal compris ce qu'ils ont essayé de faire
::gne :banghead
Oui, tu as mal compris, désolé d'être direct.

Alors reprenons.
Gamall wrote:
  • par exemple, essayons de reconstituer Ho... dépend de Pn... qui dépend de Ca... qui dépend de Ho
  • Ce serait génial si c'était vrai
  • Mais, pour ce que je voyais sur mathworld, il restait des résidus
  • Ho est simplement la dérivation de Er.
  • C'EST vrai.
  • Tu m'étonnes que j'avais pas compris ton histoire de résidus ! Ce que tu appelles résidus... c'est simplement les atomes eux-même !
Dans ce qui suit chaque élément est suivi entre parenthèses de sa correspondance en notation chiffrée.

U(3)se dérive en Pa(13) qui se dérive en Th(1113), etc.

Rn(311311222113) se dérive en Ho(1321132).At(1322113)

Ho(1321132) ne "dépend" pas de Pm, c'est Er(311311222) qui se dérive en Ho(1321132).Pm(132)

J'espère que comme ça tu comprends mieux.
Gamall wrote:Je ne vois pas en quoi ça contredit le théorème:
C'est simple, reprenons mon exemple en dérivant la dernière ligne :

(Ra.2113222113).3112132123222113
-> (Fr.122113322113).132112111312111213322113 en décomposant atome par atome
= 1113122113122113322113132112111312111213322113

(Ra.2113222113).3112132123222113
= 13211321132221133112132123222113
-> 11131221131221133221232112111312111213322113 en décomposant avec les chiffres

On ne retombe pas sur nos pattes ;)
Gamall wrote:Et j'ai bien peur d'y laisser ma peau :bobo Et ce sera de ta faute :hum
J'en serais fort honoré :huhu

-> miam
Gamall
Hic sunt dracones
Posts: 4174
Joined: Fri May 26, 2006 11:09 pm
Contact:

Re: Conway's Sequence Generator

Post by Gamall »

Kafou wrote: Ce que tu appelles résidus... c'est simplement les atomes eux-même !
*épiphanie, activation du neurone et tout*

Ca y est, j'ai compris leur tableau :lol

Je m'étais mise dans la tête qu'ils avaient fait comme tout le monde, et défini les trucs ligne par ligne, et je ne voulais pas en démordre... et c'est pour ça que le tableau ne collait à rien, et me foutait tout en l'air avec ces résidus àlakon qui sortaient de Dieu sait où :lol
Kafou wrote:Oui, tu as mal compris, désolé d'être direct.
Ne sois pas désolé, ça m'arrange bien d'avoir mal compris, vu que dans le cas contraire on serait pas dans la m***** :mdr
Kafou wrote:On ne retombe pas sur nos pattes ;)
Ha oui, tiens j'avais pas vu ça non plus :foufou

En fait, je pense que je serais tombée dans ce panneau là tôt ou tard, même avec un dico arbitraire, je n'avais pas pensé aux conséquences d'un remplacement sur la dérivation :banghead

Bha... ça aura au moins servi à expliciter la définition une bonne fois pour toutes :huhu


Bon, c'est bien, les jetons tombent déjà plus en place qu'avant :yahoo

Il reste ceci:
Gamall wrote:Tiens d'ailleurs... Par définition 1, 2 et 3 sont toujours des atomes (L et R doivent être non vides, j'ai oublié de préciser)... donc la table de mathworld est vraiment fausse, parce que ni 1 ni 2 n'y apparaissent, seulement 3.Or la définition ne dépend pas du terme de départ de la suite...
Si tu arrives à m'expliquer pourquoi 3 est un atome et pas 1 ni 2, j'arriverai même à dormir cette nuit :)
{<§ Gamall Wednesday Ida §>}
{ Mods and Programs - Mods TES-IV Oblivion }
Kafou
Poulidor Gnomonique
Posts: 1526
Joined: Sun Aug 19, 2007 7:17 pm
Location: dans son labo
Contact:

Re: Conway's Sequence Generator

Post by Kafou »

Heureux de t'avoir aidé à piger.

Voici un autre tableau sûrement plus simple à comprendre :
http://www.btinternet.com/~se16/js/lands2.htm

3 est présent parce que c'est l'uranium, le terme de départ utilisé pour construire tous les autres éléments.

1 et 2 n'apparaissent pas parce qu'il n'y en a pas besoin, les 92 éléments du tableau suffisent à "tourner en boucle" à partir d'un certain rang.

Alors ensuite, pourquoi Conway est parti de 3 et non de 1 ou 2, j'en sais fichtrement rien ! :mdr
Gamall
Hic sunt dracones
Posts: 4174
Joined: Fri May 26, 2006 11:09 pm
Contact:

Re: Conway's Sequence Generator

Post by Gamall »

Kafou wrote:1 et 2 n'apparaissent pas parce qu'il n'y en a pas besoin, les 92 éléments du tableau suffisent à "tourner en boucle" à partir d'un certain rang.
Oui, mais Conway prétend qu'il y a en tout exactement 92 atomes, selon la def énoncée plus haut :?



edit: au fait, mon prog en Java est déjà plus rapide que l'ancien en C++ sur la même tâche :lol C'est dire si l'autre n'est pas optimisé :mdr
{<§ Gamall Wednesday Ida §>}
{ Mods and Programs - Mods TES-IV Oblivion }
Kafou
Poulidor Gnomonique
Posts: 1526
Joined: Sun Aug 19, 2007 7:17 pm
Location: dans son labo
Contact:

Re: Conway's Sequence Generator

Post by Kafou »

Gamall wrote:Oui, mais Conway présent qu'il y a en tout exactement 92 atomes, selon la def énoncée plus haut :?
J'ai pas essayé de chercher (ne parlons pas de comprendre) la démonstration.

Il y a en effet exactement 92 atomes "stables". Imaginons qu'on parte de 1 :

1
11
21
1211
111221
312211
13112221
1113213211 = Hf.Sn

Je sais donc qu'à partir de la 8ième ligne je tournerai toujours sur les 92 éléments du tableau et ne retomberai donc jamais sur les 7 premières lignes. En partant de 2 c'est dès la deuxième ligne qu'on a 12 = Ca.

En essayant de partir de 1 ou de 2 les "atomes" formés par les quelques lignes de chiffres obtenues avant qu'on ne tombe sur une ligne faite des 92 atomes du tableau ne se retrouvent jamais dans la dérivation des suivants, ce sont donc des atomes instables, et ils n'appartiennent donc pas à la liste des 92 atomes stables. C'est valable pour n'importe quelle suite de chiffres utilisée comme ligne de départ.

Je ne pense pas que ce raisonnement soit une preuve de quoi que ce soit, c'est juste mon intuition, la façon dont je comprends les choses.

Edit : en fait je crois que t'avais pas compris le principe d'atome "stable" et "instable". Les 92 éléments du tableau sont stables (plus ou moins comme les 92 éléments chimiques naturels, d'où l'analogie), mais ça n'empêche pas qu'il en existe d'autres ! Ces derniers (tels que "1", "2", etc.) sont donc en quelque sorte hautement radioactifs, et disparaissent après un nombre fini de dérivations (leur "demi-vie" :lol ), comme dans la nature aussi ! (mais le rapprochement s'arrête là)
edit: au fait, mon prog en Java est déjà plus rapide que l'ancien en C++ sur la même tâche :lol C'est dire si l'autre n'est pas optimisé :mdr
Héhé... :foufou
Last edited by Kafou on Fri Aug 24, 2007 11:30 pm, edited 2 times in total.
Gamall
Hic sunt dracones
Posts: 4174
Joined: Fri May 26, 2006 11:09 pm
Contact:

Re: Conway's Sequence Generator

Post by Gamall »

Kafou wrote:Edit : en fait je crois que t'avais pas compris le principe d'atome "stable" et "instable". Les 92 éléments du tableau sont stables (comme les 92 éléments de chimie présents dans la nature, d'où l'analogie), mais ça n'empêche pas qu'il en existe d'autres ! Ces derniers (tels que "1", "2", etc.) sont donc en quelque sorte radioactifs, et disparaissent après un nombre fini de dérivations (leur "demi-vie" s:lol s:lol ), comme dans la nature aussi !
C'est vrai que ça colle bien comme terminologie :) [ton stable correspond au "common" de l'article, je pense, cad qui se retrouve dans les rangs suivants (si on est sur la même longueur d'onde et que Madame Soleil a bien deviné ce qu'ils voulaient dire par "common", parce que ce n'est pas défini.)]

Et justement j'avais manqué cette partie là,
Conway proved that there is a finite set of common elements that is stable, etc....
Donc il y a des conditions supplémentaires sur les "éléments", qui sont alors un sous-ensemble des atomes.

Et tout ça colle bien avec ton intuition. :)

Ceci dit, en continuant la lecture, je tombe qur un os: les éléments transuranés: on les avais oubliés ceux-là :assassin
He also found two infinite families of elements
that are persistent, in the sense that each such element S appears in alpha^n(S) for some
n > 0 (in fact for n = 2), and so keeps reappearing. These he called the isotopes
of Neptunium and Plutonium, collectively known as the transuranic elements. His
Cosmological Theorem asserts that there is some integer N such that any N-day-old
string splits into common and transuranic elements.
Donc en fait, il y a bel et bien des résidus (même si ce n'est pas ceux que je croyais au départ). Je ne sais pas si ce sont des atomes (en tous cas ce ne sont pas des éléments), mais on sait qu'il y en a une infinité... donc ça rique de poser problème au mirage de l'écriture atomique:
Kaf wrote:Tout atome se décompose (= en passant à la ligne suivante) avec les autres atomes
en effet on va se retrouver rapidement avec plein de 123 qui vont exploser autour des atomes, ces fameux éléments transuranés :deg
Héhé... :foufou
En fait... il écrit les rangs 1 à 56 en qq secondes (ce qui est bien mieux que mon horreur en cpp), mais après c'est la mémoire qui lui manque :lol Bref :foufou [en brutal, hein, je n'ai pas commencé à toucher aux atomes, j'essaye de dompter Java, là :D ]
{<§ Gamall Wednesday Ida §>}
{ Mods and Programs - Mods TES-IV Oblivion }
Kafou
Poulidor Gnomonique
Posts: 1526
Joined: Sun Aug 19, 2007 7:17 pm
Location: dans son labo
Contact:

Re: Conway's Sequence Generator

Post by Kafou »

Arf, 1h après j'étais encore en train d'éditer mon post, tes quotes ne correspondent pas parfaitement :lol
Gamall wrote:ton stable correspond au "common" de l'article, je pense, cad qui se retrouve dans les rangs suivants (si on est sur la même longueur d'onde et que Madame Soleil a bien deviné ce qu'ils voulaient dire par "common", parce que ce n'est pas défini.)
Oui stable = common.
Gamall wrote:Donc il y a des conditions supplémentaires sur les "éléments", qui sont alors un sous-ensemble des atomes.
Elément c'est comme une classe, atome c'est comme un objet. OK ? :fear
Gamall wrote:Donc en fait, il y a bel et bien des résidus (même si ce n'est pas ceux que je croyais au départ). Je ne sais pas si ce sont des atomes (en tous cas ce ne sont pas des éléments), mais on sait qu'il y en a une infinité... donc ça rique de poser problème au mirage de l'écriture atomique:
Tu m'apprends quelque chose.
Sauf qu'il appelle ça "éléments transuraniques" donc c'est bien des éléments :p
Heureusement pour nous, ce n'est pas le cas de 1 et de 2, et pour ma part ça me suffit :D
Gamall wrote:brutal, hein, je n'ai pas commencé à toucher aux atomes, j'essaye de dompter Java, là
Hé ho, et si tu t'occupais de trouver mon algo pour ne plus avoir de problème de mémoire ? :p
Il est compatible avec la méthode "atomique" donc tu chercheras pas pour rien.
A moins que tu ne préfères que je te le donne direct.
Gamall
Hic sunt dracones
Posts: 4174
Joined: Fri May 26, 2006 11:09 pm
Contact:

Re: Conway's Sequence Generator

Post by Gamall »

Kafou wrote:Arf, 1h après j'étais encore en train d'éditer mon post,... :lol
Il est dingue :huhu
Kafou wrote:Elément c'est comme une classe, atome c'est comme un objet. OK ? s:fear s:fear
Nan, pas OK :monstre

Ce qu'il faudra absolument faire, pour le salut des générations qui suivront, c'est faire un petit mémoire pour mettre la terminologie à jour, pour éviter le syndrôme Babel.

Rien que pour le mot "stable", par exemple, on peut avoir au moins trois définitions qui collent bien à l'intuition qu'on a du mot (stabilité à la "22", stabilité par l'opérateur alpha (celle des atomes donc), stabilité au sens "common")
Sauf qu'il appelle ça "éléments transuraniques" donc c'est bien des éléments :p
Syndrome Babel :gni

Dans ma tête:

atome = chaîne telle qu'il n'existe pas d'écriture S = L+R vérifiant #S = #L+#R
élément = les 92 atomes "communs" (en fait en relisant, l'article pose atome= élément... c'est un mot de gâché à mon avis :sweat Il n'y a pas une infinité d'élements dans la table de Mandeleiev. Pourtant il y a une infinité d'atomes au sens de la def, c'est pour ça que je préfère limiter le terme élément aux 92 :sweat :sweat :sweat :sweat)
elem transurané: en fait dans l'article ils précisent bien que c'est un élément... selon leur def, donc un atome selon la mienne. Ce qui répond à ma question "un elem trans est-il yun atome ?" : oui. Et ça répond aussi à ma question "y a t il une infinité d'atomes ?" : oui.
Kafou wrote:A moins que tu ne préfères que je te le donne direct.
Nan ! Pas drôle :fouet

Et de toutes façons il faut que j'apprenne le Java pour le boulot, Conway est un aussi bon prétexte qu'autre-chose pour ça :foufou
{<§ Gamall Wednesday Ida §>}
{ Mods and Programs - Mods TES-IV Oblivion }
Gamall
Hic sunt dracones
Posts: 4174
Joined: Fri May 26, 2006 11:09 pm
Contact:

Re: Conway's Sequence Generator

Post by Gamall »

Bon, il consomme beaucoup de mémoire pendant les calculs, c'est vrai, mais au moins il est zouli tout plein, mon prog :ouioui Ce sera le prog sur la suite de Conway le plus convivial de l'Histoire :lol

Image

Et il est quand-même nettement plus rapide que le précédent :)

Demain, je m'attaque aux atomes :monstre :archer :archer :archer :archer :archer :archer

(déterminer si une chaine est atomique ou non, puis construire le dictionnaire des atomes qui sera utilisé par la suite... si j'ai du pot, je retomberai sur le truc de Mathworld :lol)

edit: heu non, il faut que j'apprenne à mettre le calcul dans un autre thread avant, parce que le bouton stop ne risque pas de marcher, là :lol
{<§ Gamall Wednesday Ida §>}
{ Mods and Programs - Mods TES-IV Oblivion }
Kafou
Poulidor Gnomonique
Posts: 1526
Joined: Sun Aug 19, 2007 7:17 pm
Location: dans son labo
Contact:

Re: Conway's Sequence Generator

Post by Kafou »

Comme pour ton post présentant ton machin qui fait les bbcode pour mise en ligne sur wiwiland, je ne vois pas l'image.

Mais je suis allé les chercher dans le thread où tu les as attachées.

Utiliser autre chose que des 1 des 2 et des 3 en entrée c'est nul ^^

Rajoute un timer ! :twisted

Bon courage pour les atomes si tu comptes créer toi-même ton "dictionnaire", j'ai aucune idée de comment on fait pour déterminer quelle suite de chiffres est un atome ou pas :D (quelle est leur définition en fait)

(pour ma part je comptais juste partir d'un ou plusieurs atomes et les dériver autant de fois que voulu)

(PS : les elfes ils tirent sur la petite boule jaune ou l'espèce de moussaka géante ?)
Gamall
Hic sunt dracones
Posts: 4174
Joined: Fri May 26, 2006 11:09 pm
Contact:

Re: Conway's Sequence Generator

Post by Gamall »

Kafou wrote:Comme pour ton post présentant ton machin qui fait les bbcode pour mise en ligne sur wiwiland, je ne vois pas l'image.
::gne

Je note ça dans un coin :?
Kafou wrote:Utiliser autre chose que des 1 des 2 et des 3 en entrée c'est nul ^^
Je sais rhoooo, c'était juste pour le screen :P

Et il faut le faire au moins une fois dans sa vie pour voir pourquoi c'est nul :D
Kafou wrote:Rajoute un timer !
SIR Yes Sir !
Kafou wrote:Bon courage pour les atomes si tu comptes créer toi-même ton "dictionnaire", j'ai aucune idée de comment on fait pour déterminer quelle suite de chiffres est un atome ou pas s:D s:D (quelle est leur définition en fait)
Ben, la définition, je l'ai donnée là :
Gamall wrote:je vais noter & S le successeur de la séquence S. (& = alpha dans l'article)

Par exemple & "111221" = "312211"

Et je vais noter # l'application & appliquée n fois (peu importe n>= 1).

Je note aussi + l'opérateur de concaténation. "11" + "22" = "1122" (noté point dans l'article)

Une séquence divisible est une séquence S telle qu'il existe deux séquences L et R telles que
S = L+R et # S = #L + #R
.

Et un atome, c'est une séquence indivisible du point de vue de la définition précédente.

Pour employer des gros mots, # est un automorphisme sur le group des atomes, muni de + :assassin
Kafou wrote:(pour ma part je comptais juste partir d'un ou plusieurs atomes et les dériver autant de fois que voulu)
Ben oui, mais tu obtiendras toujours un composé de plusieurs atomes, et il faudra bien que tu les sépares... donc il nous faut....

Tadaaaa...

un algo pour déterminer si une chaîne quelconque est un atome donc...

Retadaaa... (regarde la def)

un algo pour déterminer si une chaîne est séparable ('splits' dans l'article) donc

Tidiiiiiiiii

un algo pour déterminer si une écriture donnée "passe bien à travers # " (pour éviter les gros mots)

Et là on regarde la def mathématique et on est très très très déprimés: la def, c'est une def de matheux, pas une def d'informaticien: lemme de Zorn à fond les ballons, il faut vérifier un truc pour tout n > 0. En maths (non constructives) ça prend 4 symboles et ça se manipule bien, mais nous, hein ? Comment on va faire ça ?

Même avec ton algo de dingue, faudra se lever tôt pour vérifier ce type de propriétés :nonnon

Ben en fait, cet épineux problème, je pense que tu as commencé à le résoudre hier :D

Quand tu as fait ta petite démo pour prouver qu'on ne pouvait pas utiliser Ac dans Rn, quand je m'embrouillais dans la table de mathworld ?

Tu as tout de suite vu qu'il y avait un problème à cause des deux chiffres consécutifs après un certain nombre de coups: en fait ce que tu as prouvé, c'est qu'en posant S = L+R avec le L et le R que je proposais, on avait #S != #L + #R (en trouvant un n), ce qui signifie que S ne se sépare pas en L + R. C'est une partie de la démonstration du fait que Rn est un atome.

Ce qui nous aide là dedans, c'est qu'on a une piste pour une caractérisation des endroits où une chaîne ne peut pas se couper: c'est un endroit tel qu'il y ait 'accrochage' (forme ****X + X******) à partir d'un certain rang.

Et on dirait bien que c'est la seule façon d'accrocher les wagons :?

donc maintenant, le problème c'est d'essayer de caractériser les couples de chaines qui auront cette propriété à un certain rang. Et je pense qu'on peut faire ça par une étude de cas sur un nombre de caractères très réduit au début et à la fin des deux chaînes. On va déterminer mathématiquement ce qu'il en est pour tous les cas possibles, les coder dans le programme, et après basta, on aura un algo pour trouver les cassures dans une chaîne. (en O(n) en plus)

Si tout de passe bien :gni....



Voilà, c'est la piste à laquelle je pense pour l'instant :? Dis-moi si tu trouves ça raisonnable, ou si j'ai encore loupé un machin gros comme une maison :foufou
Kafou wrote:(PS : les elfes ils tirent sur la petite boule jaune ou l'espèce de moussaka géante ?)
La petite boule jaune, censée figurer l'atome :) (ou toi, au choix :diable)
{<§ Gamall Wednesday Ida §>}
{ Mods and Programs - Mods TES-IV Oblivion }
Locked

Who is online

Users browsing this forum: Google [Bot] and 345 guests