Bonjour à tous
Une fois n'est pas coutume, je vous soumet une question que je me suis posé hier soir avant de m'endormir (non je ne suis pas fou ) et à laquelle je n'ai pu apporté de réponse.
Je vais essayer d'être clair bien que cela est un peu dur à énoncer:
_______________________________________
Vous connaissez tous je suppose le jeux de la suite logique.Ce jeux consiste à donner au joueur une suite de nombres qu'il doit compléter sachant qu'ils sont reliés de façon uniforme par la même relation que l'on nomme algorithme.
Le joueur, pour pouvoir compléter cette suite doit trouver cet algorithme.
Les algorithmes des suites logiques sont souvent bidons et non mathématiques et peuvent alors appeller à plusieurs réponses à conditions qu'elles soient justifier de maniére logique ou loufoque.
Pour ma part je vais refaçoner ce jeux.
Ici, un algorithme est une succession de calculs élémentaires dans c'est à dire l'addition, la soustraction (dans le cas où le resultat reste dans
) , la multiplication et la division (dans le cas où le résultat de la division est toujours entier).
***Edit Moi-Même : Rajouter l'exponentiation (mettre au carré, au cube etc...)***
Par exemple, un algorithme reliant 1 à 2 est ajouter 1, un autre est multiplier par 2, ou encore multiplier par 4 et soustraire 2 etc...
On peut ainsi créer une infinité d'algorithme.
Ma question est alors la suivante :
Quelque soient les entiers naturels a, b et c. Existe-t-il toujours un algorithme qui permet de trouver b en fonction de a et c en fonction de b.
Par exemple, si on prend l'algorithme : multiplier par 2 et soustraire 1
On voit bien que par cet algorithme en obtient 7 en fonction de 4 et 13 en fonction de 7.
Donc il existe bien un algorithme qui relie 4 - 7 - 13
Est-ce alors vrai pour tout entiers naturels ?
Quelque soit la réponse ,
_____________________________________
Si la réponse est oui alors voici une nouvelle question :
Au bout de combien d'entier naturel ne pourra-t-on plus trouver d'algorithme reliant le 2é au 1e, le 3e au 2e , .... , le n-éme au (n-1)-éme
Pareillement, quelque soit la réponse ,
J'espere avoir été clair, c'est assez dur à expliquer comme je l'ai dit, si vous n'avez pas compris quelque chose dites le moi
jord
>NM
La question du 1) est-ce bien :
soient a, b et c
existe-t-il f telle que :
b=f(a)
c=f(b)=f²(a)
avec f composée de +,-,x,: à valeurs entières ?
Pour le 2) (voire le 1) ), je sens que les nombres premiers devront intervenir dans le raisonnement de la résolution de ton PB; peut-être chercher par là...
Philoux
Salut Nightmare,
c'est une question très intéressante....
Dans le cas où la suite logique ne contient qu'une seule division ou soustraction ou multiplication ou addition, je pense qu'il existe un moyen très simple pour, trouver la "suite logique" : régression linéaire.
En revanche, en combinant plusieurs opérations différentes telle que tu l'as décrit.....je vois pas trop.
En quelque sorte philoux c'est ça.
C'est plutot :
Sachant que relie deux éléments par un nombre fini d'opérations élémentaires.
Cette relation n'est pas forcément une fonction.
Merci pour le conseil pour la 2) je vais essayer de creuser par là
Jord
en fait, j'avais mal compris ta question. je pensais que tu évoquais le cas où:
instant t on ajoute x,
instant t+1 on multiplie par y,
instant t+2 on ajoute x
....
Mais comme je l'ai dit précedemment, s'il existe une relation linéaire parfaite entre deux variables, il est sûr que la régression trouvera les coeffs...mais quant à le prouver.
régression linéaire: il s'agit d'expliquer une variable Y par une ou plusieurs variables X1,....Xp.
L'équation est de la forme Y = a1X1 + a2X2 + .....+ apXp + constante + erreur.
L'erreur n'existe pas dans le cas que tu as évoqué car la relation entre Y et les Xi est parfaite.
l'objectif de la régression est de trouver a1, a2,...., ap de tel manière à ce que l'erreur soit la plus faible possible
Je ne te suis pas trés bien enzo.
Je vois ce qu'est une régression linéaire mais je ne vois pas en quoi cela nous aide à montrer l'existence (ou non) d'un tel algorithme ?
Jord
bon un petit exemple:
je construit une suite telle que:
un+1 = 2*un + 1
ce qui donne pour les premières valeurs:
1
3
7
15
31
63
127
255
511
1023
je fais une régression entre un et un+1 et le résultat:
y = 2x + 1 soit un+1 = 2un + 1
Oui daccord mais ici ça marche car la régression est parfaite mais elle ne l'est pas toujours et n'est parfois qu'approximative (c'est là qu'intervient l'erreur).
Ce qu'il faut trouver dans mon probléme est une relation parfaite quelque soit les 3 entiers.
Jord
c'est exactement ça....si tu veux donne moi une suite de ce type et je peux trouver les coeffs, histoire que tu vois que ça marche...
Je ne te suis de nouveau plus...
Dans le cas de la suite que tu as donné dans ton autre post,ça marche bien (on a l'algorithme multiplier par 2 puis rajouter 1).
Mais peux-tu garantir que ces coefficients sont entiers ? (car je rappelle que l'algorithme ne doit comporter que des entiers)
Par exemple prenons les nombres 4-18-51
Par régression linéaire , quel algorithme trouves-tu qui relies 4 à 18 et 18 à 51 ?
Jord
excat...bien vu, j'avais zappé le coup des entiers. Alors dans ce cas là, ça devient autrement plus complexe....désolé d'avoir été à côté de la plaque si longtemps. De toute façon, je dois partir
Alors bon courage dans tes recherches!!
Merci j'en aurais besoin
En tout cas merci à toi d'avoir essayé
Si quelqu'un à une idée qu'il n'hésite pas
Jord
Je ne suis pas sur que tu y trouves grand chose. J'ai demandé à mon frére qui est ingénieur en informatique et il n'a rien trouvé, il a dit qu'il n'était pas mathématicien
Jord
Bonjour Nightmare (Modérateur),
assez intéressante comme question mais elle manque de précisions:
les exemples que tu as donné pour expliquer le mot "algorithme"laissent croire que c'est une transformation affine avec
mais avec aussi
entier aumoins pour les deux valeurs entières distinctes x=a et x=b et bien entendu
est-ce bien cela?
si c'est cela tu vois bien que c'est un systéme linéaire à 2 équatios et 2 inconnues son détérminant est d'où
on aboutit alors avec la condition
au fait que l'entier b-a doit etre un diviseur commun des 3 entiers
,
et
prenons l'exemple de ,
et
on a
,
,
et
tous multiples de 3 d'où
et
et l'algorithme est
pour ,
et
on a
n'est pas diviseur de
donc pas d'algorithme dans ce cas.
Voilà en tout cas c'est ce que j'ai compris du mot "algorithme"d'aprés les explications de Nightmare (Modérateur)
si ce n'est pas cela priére de bien vouloir donner d'autres exemples pour bien mettre au clair la signification mathématique de ce mot
amicalement majid52
Bonsour majid52
Non ce n'est pas forcément une fonction affine, c'est une succession finie de calculs élémentaires.
D'ailleur dans ces calculs élémentaires j'aimerais ajouter l'exponentiation.
Donc par exemple un algorithme serait :
Jord
Oui en fait je viens de me rendre compte que sans l'exponentiation c'est tout bonnement comme vous me le faites remarquer une fonction affine...
Re Nigthmare
> La régression fonctionne alors dans le cas de fonction affine. En suivant le raisonnement de majid52, si les coeffs de la régression appartiennent à alors il n'y a pas d'algo, s'ils appartiennent à
alors il y en a une.
> j'avais oublié ça hier mais il existe un algo (réseaux de neurones) qui est capable d'approximer n'importe quelle fonction. L'ennui avec cette méthode, c'est qu'elle nécessite un nombre d'exemples "suffisant" (=avoir un bon paquet de valeurs en entrée) pour fonctionner correctement.
pour la régression:
- si tu as qqch ds cet ordre: opération élémentaires puis exponentiation, je ne pense pas que ça marche.
- pour le cas où l'ordre est différent, autrement dit, exponentiation puis opérations +,-,*,/ ça devrait marcher à condition de rajouter les explicatives correspondantes: X², X3, ....ça devient vite très lourd.
pour les réseaux de neurones: ça marche ds tous les cas
Merci à toi en tout cas je vais essayer de résumer un petit peu tout ce qu'on m'a dit et essayer de l'appliquer.
Jord
une preuve:
L'algorithme recherché est une fonction du terme précédent. Ainsi,
un+1 = f(un) + c où c est une constante.
Quelque soit la nature de f on peut écrire (car dans notre cas on ne s'intéresse qu'à l'exponentiation et aux quatre opérations élémentaires) :
un+1 = c + a1 unp + a2 unp-1 + .... + ap un0.
Autrement dit, il existe toujours une forme linéaire pour décrire un+1
D'après le théorème de Gauss-Markov, l'estimateur de la régression linéaire est le meilleur estimateur possible (pour simplifier).
Voilà, je te passe le détail de Gauss-Markov....tu peux toujours essayer de regarder si tu veux, mais il faut quand même un bon bagage stat pour percuter.
Bonjour tout le monde;à mon avis un algorithme qui permet de créer une suite logique d'entiers à partir d'un entier a est une fonction dont tous les itérés en a sont des entiers.
Comme Nightmare (Modérateur) veut en plus qu'elle soit une succession d'opérations élémentaires elle est polynomiale à coefficients rationnels (comme l'a bien vu enzo).On peut donc voir le problème comme suit:
étant donné 3 entiers existe-t-il
telle que
(la condition
assurant que tous les itérés de f en a soient des entiers)
Bonjour,
Je suis peut-être à côté de la plaque, mais j'ai l'impression que l'"algorithme" existe toujours, et que c'est un polynôme à coefficients dans , suivi d'une division par un entier, et que tous les paramètres se calculent facilement.
Je comprends l'énoncé ainsi :
Soit des nombres entiers. On suppose que si
, alors
(*) (sinon, souci !). Existe-il une suite finie d'opérations élémentaires + - * / ^ exp à paramètres dans
permettant de passer d'un
à son successeur ?
Prenons trois exemples.
Exemple 1 : 4, 18, 51.
Exemple 2 : 4, 18, 51, 4, 18, 51, 4, 18, 51 (une sorte de boucle).
Exemple 3 : 1, 3, 7, 15, 31, 63, 127, 255, 511, 1023.
Dans les "suites" , supprimons les couples
qui sont les mêmes.
On obtient les "suites" suivantes, avec les
différents deux à deux, sauf éventuellement avec le dernier d'entre eux (**) :
Exemple 1 : 4, 18, 51.
Exemple 2 : 4, 18, 51, 4.
Exemple 3 : 1, 3, 7, 15, 31, 63, 127, 255, 511, 1023.
Soit le nombre d'entiers dans la "suite"
Exemple 1 :
Exemple 2 :
Exemple 3 :
Sauf erreur (à démontrer rigoureusement, en travaillant dans , et en s'appuyant sur les hypothèses (*) et (**)), il existe un unique polynôme
à coefficients rationnels et de degré inférieur ou égal à
tel que :
Notons
En écrivant toutes les relations , il vient :
Donc :
Exemple 1 :
donc
Exemple 2 :
donc
Exemple 3 :
donc
(c'est bien ainsi que l'exemple avait été construit plus haut)
Nicolas
Re-bonjour tout le monde;
Nicolas_75,je reprends l'exemple de la suite et l'algorithme que tu as trouvé
pour
pas de problème tu as
et
mais
n'est plus entier et ton algorithme ne génére donc pas une suite logique d'entiers.Comme je l'ai expliqué plus haut il faut trouver
tel que
et
(s'il existe bien entendu)
elhor_abdelali, nous ne répondons pas à la même question.
Je comprends ta problématique (plus intéressante que la mienne) : non seulement, trouver l'"algorithme", mais faire en plus en sorte que les nombres générés ensuite soient tous entiers.
Quant à moi, j'essayais juste de répondre à la question initiale de Nightmare, qui demandait de relier des nombres existants. Cf messages ci-dessus et message initial :
"Ma question est alors la suivante :
Quelque soient les entiers naturels a, b et c. Existe-t-il toujours un algorithme qui permet de trouver b en fonction de a et c en fonction de b.
Par exemple, si on prend l'algorithme : multiplier par 2 et soustraire 1
On voit bien que par cet algorithme en obtient 7 en fonction de 4 et 13 en fonction de 7.
Donc il existe bien un algorithme qui relie 4 - 7 - 13
Est-ce alors vrai pour tout entiers naturels ?
[etc...]"
C'est du moins ma compréhension.
Cordialement,
Nicolas
Une condition nécéssaire:
supposons qu'il existe tel que:
et
en écrivant
(
,
)on voit que:
et donc que l'on doit avoir:
Une condition suffisante:
Supposons que et posons alors;
(c'est un entier naturel non nul) et
(c'est un entier) il est alors facile de voir que l'algorithme
génére une suite logique d'entiers a,b,c..
remarque: on voit que le mot "algorithme" se réduit à une transformation affine à coefficients entiers et qu'une condition nécéssaire et suffisante d'existence d'un algorithme générant la suite d'entiers a,b,c.. est que
Voilà,j'éspére que j'ai répondu à ta question Nightmare
Vous devez être membre accéder à ce service...
Pas encore inscrit ?
1 compte par personne, multi-compte interdit !
Ou identifiez-vous :