Inscription / Connexion Nouveau Sujet
Niveau autre
Partager :

Formule et contre formule ?

Posté par
sinkingels
19-07-15 à 23:54

Bonjour, je ne suis plus étudiant ni rien, mais juste intéressé et j'ai une question !
Mon post est certainement au mauvais endroit, le titre très abstrait je vous prie de m'en excuser, je savais pas trop comment placer ca, et meme exprimer avec des mots ce que je recherche reste compliqué...
j'ai pas encore réussi à trouver quoique ce soit sur le net à ce sujet (mais je ne désespère pas).

y a t il un moyen de trouver une formule qui génèrerai les nombres exclus des résultats éventuels d'une autre formule qui se trouve avoir 2 inconnus ?

imaginons que j'ai un ensemble de nombre correspondant a 10XY + 6X + 3Y + 18  (pour x et y entiers >ou= a 1 )
du coup on peut trouver les nombres notamment 37, 53, 56, 76 ... et de fait pleins d'autres ...

la question c'est comment trouver une formule (ou alors existe il la formule ou un moyen de la construire) qui trouverai la totalité des nombres excluant ceux qui sont réponses a la formule originale ?

l'idée c'est de trouver parmi les nombres entiers positifs, les nombres qui ne correspondent pas a la formule de base et qui quelque soit x et y entiers ne seront jamais une réponse a celle ci... malgré les deux variables.

comme un negatif photo des sorties eventuels de la formule de base.

J'espère être suffisamment clair dans mes propos, n'hésitez pas a me demander plus de précisions.
Si une telle méthode existait ce serait vraiment très appréciable  
Sinon n'hésitez pas a m'envoyer que ce soit des cours ou des documents sur les formules a 2 inconnus et les facon de les traiter.

Merci beaucoup

Posté par
LeDino
re : Formule et contre formule ? 20-07-15 à 13:13

Je reformule (et généralise) ton problème :

Connaissant l'expression d'une fonction  F(X,Y) = Z
Connaissant les domaines variation de X, de Y et de Z
On définit A comme l'ensemble des valeurs prises par Z,  et A' son complémentaire.

Comment caractériser et trouver directement les points  Z'  de  A'  ?


A mon sens, il n'y a pas de réponse générale à ce problème.
Il faut considérer la fonction F et étudier ses propriétés pour trouver par ordre de préférence :
1. une formule directe,
2. un algorithme de construction directe de A',
3. un crible consistant à construire A,  qui donne A' par élimination progressive...
Le problème du crible étant de s'assurer qu'un nombre candidat à être dans A' a été intégralement criblé.

Pour l'exemple que tu donnes :  Z = 10XY + 6X + 3Y + 18   (X, Y, Z dans N*)

Je ne pense pas qu'on puisse trouver une formule directe (simple).
Un crible est possible.
Un algorithme de construction directe est possible grâce à la propriété de croissance de Z en fonction de X et de Y.
L'algorithme consiste à parcourir le crible par valeurs croissantes.
Entre deux valeurs ordonnées du crible, on connait alors les valeurs de A' dans cet intervalle. Et on itère.

Posté par
alainpaul
re : Formule et contre formule ? 20-07-15 à 17:36

Bonjour,

J'ai  pensé aussi à un crible:de p(x,y)=10xy+6x+3y+18

p(x+1,y)=p(x,y)+10y+6

p(x,y+1)=p(x,y)+10x+3



Soit un tableau:
p(1,1)        p(2,1)     p(3,1) ...
  37            53         69

p(1,2)        p(2,2)     p(3,2)
  50            76         102

p(1,3)        p(2,3)     p(3,3)
  63            99         135
...                                  ...


incrément colonne n ,10n+3
incrément ligne  p  ,10p+6


Je me pose une question:existe-t' il des doublets:p(x_1,y_1)=p(x_2,y_2)?


Alain

Posté par
alainpaul
re : Formule et contre formule ? 20-07-15 à 19:24

Bonsoir,

Je me réponds: oui.

y pair alors: p(x,y)=10xy+6x+3y+18=p(\frac{y}{2},2x)


D'autres idées?


Alain

Posté par
alainpaul
re : Formule et contre formule ? 22-07-15 à 11:08

Bonjour,

Qu'a donc produit le demandeur,
aurait-il une idée?


Amicalement,

Alain

Posté par
sinkingels
re : Formule et contre formule ? 22-07-15 à 22:13

globalement j'avance pas des masses !

pour l'idée d'établir un crible j'ai pensé utiliser excel
définir sur une feuille a toutes les possibilités éventuelles entre x pour les colonnes et y les lignes du logiciel... je sais pas bien comment faire donc je l'ai fait sous format papier et ca marche mieux (mais c'est quelque peu longuet et pas très lisible)... puis ensuite dans une feuille b lui demander de supprimer les résultats obtenus sur la feuille a a tout les entiers qui soit (il se pourrait que excel ai un système de détection de formules "simples" qui pourrait éventuellement récupérer une formule a partir de ces résultats) mais a vrai dire, j'en suis loin.

j'ai essayer de triturer la formule mais rien de cohérent ne sort ...

Dans l'idée, il me faudrait plutot les coordonnées des points tels que 10xy+6x+3y+18 ne peut pas etre egal a (10ab+6a+3b+18)-1
puis la meme chose pour -2 et ainsi de suite que je puisse definir l'ensemble des points non contenus dans les résultats de la formule.

Pour l'instant ca me travaille beaucoup, et ce topic m'aura aidé
merci a toi alain
Ma contre formule n'est pas au point xD mais si je trouve quelque chose je n'oublierai pas de le poster ici

Posté par
LeDino
re : Formule et contre formule ? 23-07-15 à 02:34

Si F(X,Y) est croissante en X et en Y, il y a des solutions "pratiques" à ton problème.
Mais tout dépend de l'utilisation que tu veux en faire.
Il est possible avec un programme (par exemple en Python) d'écrire une fonction qui à partir d'un nombre quelconque, donne le prochain nombre Z interdit. Ensuite, par appels successifs de cette fonction on peut alors progresser dans l'ensemble A'... intervalle par intervalle.

Pour commencer il suffit de suivre l'algorithme suivant (non optimal, mais améliorable en stockant des listes de valeurs...) :


def F(X,Y): 
    return 10*X*Y + 6*X + 3*Y + 18

def ProchainZ(N):
    Znext = 10**12
    X = 1
    Y = 1
    Z = F(X,Y)
    if ( N < Z): return Z
    while (Z <= N):
        X = X+1
        Z = F(X,Y)
        if (Z > N) :
            Znext = min(Znext, Z)
            X = 1
            Y = Y+1
            Z = F(X,Y)
            if (Z > N): Znext = min(Znext, Z)
    return Znext

TEST:
Z = 1
for i in range(100):
    Z = ProchainZ(Z)
    print(Z), "  ",

RESULTAT:
 37     50     53     63     69     76    85     89      99    101
102    115    117    122    128    133    135    141    145    149
154    165    167    168    171    180    181    191    193    197
201    206    207    213    214    219    229    232    234    237
243    245    257    258    260    261    267    271    277    279
283    284    293    297    300    306    309    310    313    315
323    325    329    333    336    341    343    349    351    352
357    362    366    369    373    375    386    387    388    389
398    399    401    405    414    419    421    423    425    427
429    432    437    440    444    453    459    465    466    467

Posté par
alainpaul
re : Formule et contre formule ? 23-07-15 à 09:57

Bonjour,


Où passe les doublons?

Par exemple:Z=76 correspond à p(1,4) et p(2,2),

Remarque:
*  les nombres 37+13k sont au tableau.
** la formule a généré quatre nombres consécutifs:
   386,387,388,389


Alain

Posté par
LeDino
re : Formule et contre formule ? 23-07-15 à 12:46

Bonjour Alain,

Les doublons sont ne sont pas intéressants dans la recherche de A (ou de A').
Si Sinkingels veut connaître la liste des valeurs de A' : il l'a.

Quand on applique le crible d'Eratosthène pour trouver les nombres premiers, on ne s'intéresse pas spécifiquement aux nombres qui sont éliminés "plusieurs fois" parce qu'à la fois multiples de 2, de 3, de 5... On s'intéresse juste à ce qui reste au final.

C'est ce que fait l'algorithme que je propose.

Posté par
sinkingels
re : Formule et contre formule ? 23-07-15 à 17:08

Moi dans l'idée c'était pas tant d'avoir un ensemble de points (bien que ce serait chouette aussi) mais la finalité serait la formule qui donnerai tout les autres résultats ...

Dans le fond mon ensemble de points c'est difficilement malléable, calculable, comme tellement concret mais volumineux que trop abstrait (et de fait pour eratostene, son crible bien que très utile et très beau ne procure pas de formule définie pour les nombres premiers et ne permet pas de faire grandir les nombres premiers et de plus se trouve être très lent a produire)
par contre une formule (qu'importe le nombre d'inconnus) c'est suffisamment court pour espérer établir une démonstration histoire de prouver ce qu'on raconte

je me rend compte que j'en demande beaucoup xD

Ensuite je pense qu'avoir des coup d'oeuil pour des cas précis remarquables peut aider a voir ca sous un autre angle

globalement je crois que 10xy+6x+3y+18=10x'y'+6x'+3y'+18 si xy=x'y'
ca marche avec (1;2) et (2;1) ... mais aussi avec (3;4) et (2;6) (et de fait (4;3) et (6;2))

dites moi si je vous dit que 10xy+6x+"3y+18 = 51 312 458 comment faire pour déterminer les couples x et les y possibles entiers ?
le résultat est pas important mais la méthode pourrait m'aider

merci

Posté par
LeDino
re : Formule et contre formule ? 23-07-15 à 19:41

Citation :
je me rend compte que j'en demande beaucoup xD
Non.
Tu demandes n'importe quoi ...

Et je t'ai déjà répondu : pour le cas général il n'y a pas de formule possible.

Au cas par cas, il faut voir...
Est-ce que l'exemple que tu as donné est précisément le cas qui t'intéresse, ou bien est-ce juste un exemple parmi plein d'autres ?
Si c'est LE cas qui t'intéresse, c'est à vérifier mais je ne pense quand même pas qu'une formule puisse y répondre.
Mais dans un sens, un algorithme est une sorte de formule... avec une complexité qui croit avec la taille.

Si on savait au moins à quoi diable va servir cette "formule"... on pourrait peut-être t'aider mieux.
En fait tu n'as pas dit quelle était la finalité de ta recherche.

Posté par
LeDino
re : Formule et contre formule ? 23-07-15 à 19:43

Dans le cas général absolu avec F(X,Y) quelconque : je te l'ai déjà dit, il n'y a pas de formule.
Et avec ce F(X,Y), je doute qu'il y en ait une (plus simple qu'un algorithme, s'entend).

On pourrait t'aider mieux si on savait quelle est la finalité de ta recherche.
Tu n'as toujours pas dit à quoi une "formule" te servirait...

Posté par
LeDino
re : Formule et contre formule ? 23-07-15 à 19:59

Citation :
globalement je crois que  10xy + 6x + 3y + 18 = 10x'y' + 6x' + 3y' + 18   si  xy=x'y'

C'est FAUX la plupart du temps !
C'est faux même pour un des exemples que tu as donnés...

F(1,2) = 20 + 12 + 3 + 18 = 53
F(2,1) = 20 +  6 + 6 + 18 = 50

Pour que cela fonctionne, il faut en plus avoir :  2(x-x') = (y'-y)

Posté par
LeDino
re : Formule et contre formule ? 23-07-15 à 20:01

Citation :
globalement je crois que 10xy+6x+3y+18=10x'y'+6x'+3y'+18 si xy=x'y'
ca marche avec (1;2) et (2;1) ... mais aussi avec (3;4) et (2;6) (et de fait (4;3) et (6;2))
Faux la plupart du temps...
Y compris pour un de tes exemples : F(2,1) différent de F(1,2)

Il faut avoir en plus :  2(x-x') = (y'-y)

Posté par
LeDino
re : Formule et contre formule ? 23-07-15 à 20:02

Désolé pour le double post : lag du serveur...

Posté par
alainpaul
re : Formule et contre formule ? 24-07-15 à 12:18

Bonjour,


J'avais déjà donné la relation:  p(x,y)=p(\frac{y}{2},2x) , y pair.

Pour l'exemple: p(2,6)  p(2,6)=p(\frac{6}{2},2\times 2)=p(3,4)
Vérifiée  donc pour p(1,2) = p(2,1),

Remarque:
je ne vois pas d'autre voie que l'algorithme donné par  "LeDino"


Alain
PS:un problème voisin:les correspondances bijectives f(m,n)de Cantor.

Posté par
LeDino
re : Formule et contre formule ? 24-07-15 à 13:25

Citation :
je ne vois pas d'autre voie que l'algorithme donné par  "LeDino"

Bonjour Alain,

Mon algorithme est un peu "brut de fonderie"...
Il est assez simple (pour ne pas dire simpliste), donc assez facile à comprendre.
Il consiste à rechercher la courbe de niveau limite (les Z immédiatement inférieurs ou égaux au dernier ZA trouvé) puis à chercher le ZA suivant (Znext) au voisinage immédiat (+1 en X).
Il fonctionne pour F croissante en X et en Y.

On peut l'améliorer, par exemple en stockant la dernière frontière évaluée (et en la gérant à chaque itération : des points entrent, des points sortent).
Ou si on ne veut rien stocker : en cheminant sur la frontière (+1 en Y, -DX en X)... DX sera toujours bien plus petit que le dernier X.

On peut aussi l'améliorer beaucoup plus en tenant compte des propriétés de la surface F(X,Y)=Z.
Dans l'exemple donné par sinkingels, chaque courbe de niveau est une hyperbole. On doit donc pouvoir chercher le Znext plus facilement sur la frontière puisqu'on connait son équation et qu'elle est inversible (X donne Y et réciproquement).

Dans ces conditions, il est peut être possible d'aboutir à un algorithme très peu gourmand, qui se rapprocherait presque de la "formule" que cherche sinkingels.
Mais ça n'a d'intérêt que si on sait à quoi cela serait utile.



Vous devez être membre accéder à ce service...

Pas encore inscrit ?

1 compte par personne, multi-compte interdit !

Ou identifiez-vous :


Rester sur la page

Désolé, votre version d'Internet Explorer est plus que périmée ! Merci de le mettre à jour ou de télécharger Firefox ou Google Chrome pour utiliser le site. Votre ordinateur vous remerciera !