Une somme

[skilveg]

Bonjour,

Apparemment, si , et sont trois entiers naturels et si est une fonction, on a l'identité
[CENTER]

[/CENTER]

Est-ce que quelqu'un voit pourquoi? Merci d'avance à tous ceux qui essaieront!

[Nightmare]

Salut !

Tu es sûr de ta relation? Pour moi elle ne marche pas...

[Nightmare]

Oups ! Je n'avais pas vu que tu avais changé les indices !

Je vais chercher avec ceux là.

[Zavonen]

Une idée comme ça.
Tu considères les nombres premiers entrant dans la décomposition de m,n et p
Soient donc p_1,p_2, .., p_r
de sorte que chaque entier m,n,l est entièrement caractérisé par un jeu d'exposants, éventuellement nuls:
(n_1, ...,n_r) pour n ce qui signifie que n=p_1^n_1 ....p_r^n_r
(m_1, ...,m_r) pour m ce qui signifie que m=p_1^m_1 ....p_r^m_r
(l_1, ...,l_r) pour l ce qui signifie que l=p_1^l_1 ....p_r^l_r
Dans le problème les sommes ne jouent aucun rôle particulier pas plus que l'ensemble des valeurs de f. Il s'agit de montrer que les produits dd' donnent les mêmes éléments quand on fait:
d|n et d|m ou pour chaque d d'|l et d'|mn/d²
ou bien:
d|n et d|l et ou pour chaque d d'|m et d'|nl/d²
Les d solutions du 1°cas ont un jeu d'exposants
(d_1, ..,d_p) ou pour chaque i d_i <=Min(m_i,n_i)
et où pour chaque d d' a un jeu d'exposants:
(e_1, ...,e_p) ou pour chaque i ei<=Min(l_i,n_i+l_i-2d_i)
Évidemment les nombres dd' ont pour jeu d'exposants:
(d_1+e_1, ...,d_r+e_r)
Il faudrait donc voir que les n-uples ainsi obtenus quand les d_i varient comme il est dit plus haut, sont les mêmes que dans l'autre cas.
C'est pas gagné mais c'est peut être faisable.

[skilveg]

Oui, j'avais pensé aussi à ça et un peu creusé... Peut-être pas assez :mur:

Bonne soirée

[Zavonen]

Quand m et n sont premiers entre eux il me semble que ça marche. Dans les deux cas on trouve tous les n-uples :
(k_1, ... ,k_r) où k_i<=l_i

[Zavonen]

Ce petit programme ne prouve rien, mais il vérifie ton résultat.
Il génére trois suites d'exposants de taille r donnée quelconque.
Chaque suite correspond à un entier M,N et L comme dans ton problème.
On ne connait pas les entiers premiers p_1, ..,p_r mais on n'a pas besoin de les connaître
On ne raisonne que sur les exposants.
A la fin on doit vérifier que les nombres qui apparaissent sont en nombre égal et que ce sont les mêmes.
Chose que j'ai vérifiée après plusieurs appels
Le résultat de l'exécution pourrait te guider dans ton raisonnement.
Si tu n'as pas d'interprète python tu peux en télécharger un gratos, avec son EDI (idle), quel que soit ton OS (windows,linux, mac)

Code: Tout sélectionner

# -*- coding: utf-8 -*-
# les nombres sont traités comme des suites d'exposants
import random
def randseq(r, n):
    """génère une suite de r exposants entre 0 et n"""
    return [random.randint(0, n) for i in range(0, r)]

def div(L):
    """retourne la liste des diviseurs de L"""
    if L == []:
        return [[]]
    D = div(L[1:])#appel récursif
    return [[x] + X for x in range(0, L[0] + 1) for X in D]

def pgcd(L1, L2):
    """Comme son nom l'indique"""
    return [min(L1[i], L2[i]) for i in range(0, len(L1))]

def prod(L1, L2):
    """produit de deux nombres"""
    return [L1[i] + L2[i] for i in range(0, len(L1))]
def quot (L1, L2):
    """quotient de deux nombres"""
    return [L1[i]-L2[i] for i in range(0, len(L1))]
def gen1(L, N, M):
    """ genère les couples d,d'première version"""
    g1 = pgcd(N, L)
    A = div(g1)
    B = [[X, Y]  for X in A for Y in div(prod(M, quot(prod(N, L), prod(X, X))))]
    return B
def gen2(L, N, M):
    """ genère les couples d,d' seconde version"""
    g1 = pgcd(N, M)
    A = div(g1)
    B = [[X, Y]  for X in A for Y in div(prod(L, quot(prod(N, M), prod(X, X))))]
    return B

if __name__ == "__main__":
    """programme principal"""
    M = randseq(2, 3);#génration des exposants de M
    N = randseq(2, 3);#génération des exposants de N
    L = randseq(2, 3);#génération des exposants de L
    print M
    print N
    print L
    R1 = gen1(L, N, M)
    R2 = gen2(M, N, L)
    print R1
    print R2
    print len(R1)
    print len(R2) #affiche toujours la même longueur
    Diff = [X for X in R1 if X not in R2]
    print Diff #affiche [] donc les deux coïncident.
 


[Zavonen]

Ce problème me turlupine (m'intéresse).
J'ai publié ce matin deux messages que j'ai fini par annuler, parce qu'ils comportaient des erreurs.
Je te soumets un code qui essaie de prouver ton assertion, et qui malheureusement prouve le contraire, mais j'ai pu faire une erreur.
Parfois les résultats coïncident, parfois ils ne coïncident pas. Si tu as le temps regarde ce code (vraiment simple).

Code: Tout sélectionner

# -*- coding: utf-8 -*-
# les nombres sont traités comme des suites d'exposants
import random
def randseq(r, n):
    """génère une suite de r exposants entre 0 et n"""
    return [random.randint(0, n) for i in range(0, r)]

def div(L):
    """retourne la liste des diviseurs de L"""
    if L == []:
        return [[]]
    D = div(L[1:])#appel récursif
    return [[x] + X for x in range(0, L[0] + 1) for X in D]

def pgcd(L1, L2):
    """Comme son nom l'indique"""
    return [min(L1[i], L2[i]) for i in range(0, len(L1))]

def prod(L1, L2):
    """produit de deux nombres"""
    return [L1[i] + L2[i] for i in range(0, len(L1))]
def quot (L1, L2):
    """quotient de deux nombres"""
    return [L1[i]-L2[i] for i in range(0, len(L1))]
def gen(L, N, M):
    """ genère les couples d,d'première version"""
    g1 = pgcd(N, L)
    A = div(g1)
    B = [[X, Y]  for X in A for Y in div(prod(M, quot(prod(N, L), prod(X, X))))]
    return B

if __name__ == "__main__":
    """programme principal"""
    M = randseq(2, 3);#génération des exposants de M
    N = randseq(2, 3);#génération des exposants de N
    L = randseq(2, 3);#génération des exposants de L
    print M
    print N
    print L
    R1 = gen(L, N, M)
    R2 = gen(M, N,L)
    print len(R1)
    print len(R2)
    Diff = [X for X in R1 if X not in R2]
    print Diff
   
 

par exemple pour M=12 N=9, L=108
je trouve une différence de 15 couples
60 solutions dans le premier cas
75 dans le second

[skilveg]

Il me semble que pour ton "gen(L, N, M)" tu t'es trompé dans le code, tu mets un produit au lieu d'un pgcd. (D'ailleurs, c'est fait en quel langage?)

En ce qui me concerne j'avais codé tout ça en Maple et ça marchait:

Code: Tout sélectionner

ens:=proc(m,n,l)
   local d1, d2, s:
   s:=NULL:
   for d1 from 1 to min(n,l) do
      if irem(n,d1)=0 and irem(l,d1)=0 then
         for d2 from 1 to min(m,n*l/(d1^2)) do
            if irem(m,d2)=0 and irem(n*l/(d1^2),d2)=0 then
               s:=s,d1*d2
            fi
         od
      fi
   od:
   return(sort([s]))
end;

test:=proc(N)
   local m,n,l:
   for m from 1 to N do
   for n from 1 to N do
   for l from 1 to N do
      if ens(m,n,l)ens(l,m,n) then return(m,n,l) fi
   od od od:
   return(true)
end;

[Zavonen]

tu mets un produit au lieu d'un pgcd.

Exact je vais changer ça.
C'est du Python.

[Zavonen]

J'ai changé le code:

Code: Tout sélectionner

import random
FP=[2,3,5,7,11,13,17]

def convert(L):
    R=[FP[i]**L[i] for i in range(0,len(L)) ]
    return reduce((lambda x,y:x*y), R)

def randseq(r, n):
    """génère une suite de r exposants entre 0 et n"""
    return [random.randint(0, n) for i in range(0, r)]

def div(L):
    """retourne la liste des diviseurs de L"""
    if L == []:
        return [[]]
    D = div(L[1:])#appel récursif
    return [[x] + X for x in range(0, L[0] + 1) for X in D]

def pgcd(L1, L2):
    """Comme son nom l'indique"""
    return [min(L1[i], L2[i]) for i in range(0, len(L1))]

def prod(L1, L2):
    """produit de deux nombres"""
    return [L1[i] + L2[i] for i in range(0, len(L1))]
def quot (L1, L2):
    """quotient de deux nombres"""
    return [L1[i]-L2[i] for i in range(0, len(L1))]
def gen(L, N, M):
    """ genère les couples d,d'première version"""
    g1 = pgcd(N, L)
    A = div(g1)
    B = [[X, Y]  for X in A for Y in div(pgcd(M, quot(prod(N, L), prod(X, X))))]
    return B

if __name__ == "__main__":
    """programme principal"""
    M = randseq(2, 3);#génération des exposants de M
    N = randseq(2, 3);#génération des exposants de N
    L = randseq(2, 3);#génération des exposants de L
    print "N=",convert(M)
    print "M=",convert(N)
    print "L=",convert(L)
    R1 = gen(L, N, M)
    R1=[[convert(X[0]),convert(X[1])] for X in R1]
    R2 = gen(M, N,L)
    R2=[[convert(X[0]),convert(X[1])] for X in R2]
    print "gen(L,N,M)=",R1
    print "gen(M,N,L)=",R2
    Diff1=[X for X in R1 if X not in R2]
    Diff2=[X for X in R2 if X not in R1]
    print "Diff1=",Diff1
    print "Diff2=",Diff2
 

Voici une exécution:

Code: Tout sélectionner

N= 24
M= 6
L= 12
gen(L,N,M)= [[1, 1], [1, 3], [1, 2], [1, 6], [1, 4], [1, 12], [1, 8], [1, 24], [3, 1], [3, 2], [3, 4], [3, 8], [2, 1], [2, 3], [2, 2], [2, 6], [6, 1], [6, 2]]
gen(M,N,L)= [[1, 1], [1, 3], [1, 2], [1, 6], [1, 4], [1, 12], [3, 1], [3, 2], [3, 4], [2, 1], [2, 3], [2, 2], [2, 6], [2, 4], [2, 12], [6, 1], [6, 2], [6, 4]]
Diff1= [[1, 8], [1, 24], [3, 8]]
Diff2= [[2, 4], [2, 12], [6, 4]]
 

On trouve des couples différents, mais les produits sont les mêmes

[Zavonen]

Confirmation, ça marche:

Code: Tout sélectionner

    print "N=",convert(M)
    print "M=",convert(N)
    print "L=",convert(L)
    R1 = gen(L, N, M)
    R1=[[convert(X[0]),convert(X[1])] for X in R1]
    print "gen(L,N,M)=",R1
    R1=[X[0]*X[1] for X in R1]
    print "produits=",R1
    R2 = gen(M, N,L)
    R2=[[convert(X[0]),convert(X[1])] for X in R2]
    print "gen(L,N,M)=",R2
    R2=[X[0]*X[1] for X in R2]
    print "produits=",R2
    Diff=[X for X in R1 if X not in R2]
    print Diff

Une exécution parmi 100:

Code: Tout sélectionner

N= 72
M= 9
L= 6
gen(L,N,M)= [[1, 1], [1, 3], [1, 9], [1, 2], [1, 6], [1, 18], [3, 1], [3, 3], [3, 2], [3, 6]]
produits= [1, 3, 9, 2, 6, 18, 3, 9, 6, 18]
gen(L,N,M)= [[1, 1], [1, 3], [1, 2], [1, 6], [3, 1], [3, 3], [3, 2], [3, 6], [9, 1], [9, 2]]
produits= [1, 3, 2, 6, 3, 9, 6, 18, 9, 18]

Donc ta proposition semble vraie.
En fait jusqu'à présent je réfléchissais avec l'idée que les couples étaient les mêmes, mais ce sont seulement leurs produits, ce qui complique l'affaire.

[Zavonen]

Je pense qu'une démo par récurrence est possible sur N, en raisonnant sur la famille des exposants.
si N=1 cas (0,0,....,0) le résultat est évident.
Il faut montrer qu'on peut augmenter un exposant de N d'une unité. Le problème étant symétrique en les exposants on peut supposer sans restreindre la généralité qu'il s'agit du premier exposant.
En somme si L et M sont quelconques et si N=(n_1, ...,n_r) est tel que la propriété est vérifiée pour (M,N,L) il faut montrer qu'elle l'est aussi pour:
(M,N',L) où N'=(n_1+1, ... ,n_r).
Il faut donc voir quand on rajoute une unité à n_1 quels nouveaux couples (d,d') on crée et quels produits ils engendrent.
J'ai pu montrer que si n_1 >l_1 et n_1>m_1 c'est trivialement vrai.
Pour le reste il faudrait se lancer dans une étude de cas mais je n'ai pas réussi à conclure.
Je vais arrêter parce que j'ai beaucoup d'autres choses à faire.
Si tu parviens au résultat, de cette façon ou d'une autre peux tu publier ta preuve?
Bonne chance.

[skilveg]

OK. Merci en tout cas pour ton intérêt.

[Zavonen]

Nous en étions donc parvenus au point suivant:
Essayer de démontrer le résultat par récurrence sur n, sachant qu'il est évident pour n=1
Or on peut en fait raisonner exposant par exposant, et on peut donc commencer à supposer que m,n et p sont tous puissances d'un seul et unique nombre premier p (quel qu'il soit). On assimile maintenant tout nombre à son exposant, ainsi j'écrirais tout simplement n au lieu de p^n.
Désignons par all_inf(x,y) tous les nombres qui sont inférieurs à x et à y.
Désignons par gen(l,n,m) la liste des sommes e+d où e est dans all_inf(x,y) et où pour chaque d , e parcourt l'ensemble all_inf(m,l+n-2d).
Le but est de montrer d'une façon ou d'une autre (par exemple par récurrence sur n, que:
gen est symétrique en l et m (n joue ici un rôle de pivot).
Optons pour la récurrence sur n.
Examinons la croissance de gen quand n augmente d'une unité, ce que j'appelle la dérivée partielle discrète relativement à n de la fonction de trois variables g.
J'ai donc écrit un petit programme.
Supposons par exemple que lm+l est également clair et facile à démontrer.
Reste à voir ce qui se passe lorsque n est entre m et m+l.
On le voit bien:
On rajoute à chaque fois une séquence qui commence par n+1 et dont la longueur raccourcit d'une unité à chaque fois que n augmente de 2 unités.
Je n'ai pas encore pu le démontrer, mais cela parait accessible.
Supposons que nous ayons établi ce comportement pour gen(l,n,m) et pour gen(m,n,l). De fait il est exactement le même. Le résultat est acquis.