Nouvelles factorisations
dans Arithmétique
Si $p$ est un nombre premier, je note $p^{(a)}$ à la place de $(p!)^a$. Par exemple :
$11^{(1)}7^{(-1)}5^{(-1)}3^{(-1)}2^{(1)}=22\quad $ et $\quad 5^{(1)}3^{(-3)}2^{(1)}=\dfrac {10}{9}$.
Tout rationnel positif s'écrit comme un quotient de produits de factorielles de nombres premiers.
C'était l'objet de la question $B1$ du "70th annual Putnam" et c'est assez simple.
Ce qui me tire souci c'est l'unicité de cette écriture :-(
$11^{(1)}7^{(-1)}5^{(-1)}3^{(-1)}2^{(1)}=22\quad $ et $\quad 5^{(1)}3^{(-3)}2^{(1)}=\dfrac {10}{9}$.
Tout rationnel positif s'écrit comme un quotient de produits de factorielles de nombres premiers.
C'était l'objet de la question $B1$ du "70th annual Putnam" et c'est assez simple.
Ce qui me tire souci c'est l'unicité de cette écriture :-(
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
Pour le démontrer on suppose qu'il y a deux écritures distinctes.
Cela entraîne que 1 s'écrit comme un quotient de produits de factorielles de nombres premiers. Après simplification il ne peut plus rester une factorielle de nombre premier car le plus grand nombre premier y figurant ne serait pas simplifiable.
On va pouvoir parler de factoriellisation (pardon Chaurien). Des questions subsistent :
- peut-on définir le pgcd ? le ppcm ?
- comment reconnaitre un nombre entier ?
- comment écrire $2018$ ?
Amicalement
Ça ne me paraît pas insurmontable.
-- Schnoebelen, Philippe
[2, 16], [3, -9], [5, -8], [7, -3], [11, 4], [13, -1], [19, 2], [23, -3], [31, 3], [37, -1], [47, 1], [59, -1], [61, 1], [67, -2], [71, 1], [79, -1], [83, 1], [491, 1], [503, -1], [997, -1], [1009, 1]
ou avec les notations de Cidrolin:
$1009^{(1)}997^{(-1)}503^{(-1)}491^{(1)}83^{(1)}79^{(-1)}71^{(1)}67^{(-2)}61^{(1)}59^{(-1)}47^{(1)}37^{(-1)}31^{(3)}23^{(-3)}19^{(2)}13^{(-1)}11^{(4)}7^{(-3)}5^{(-8)}3^{(-9)}2^{(16)}$
Pourquoi me demander pardon ?
Notre belle langue française est une langue vivante, et elle doit donc vivre, et « factoriellisation » me semble un néologisme tout à fait conforme à son génie propre.
On ne peut en dire autant de l'ignoble « écriture-inclusive » qui la déforme gravement et qui a été de ce fait dénoncée par toutes les autorités compétentes.
Bonne nuit.
Fr. Ch.
J'ai une solution pour éviter de rendre imprononçable la langue:
Dès que l'usage de l'écriture inclusive se manifeste dans une phrase on féminise.
Jandri, pourrais tu montrer ton programme ?
Cordialement,
Rescassol
C'est parce que 1949 et 1951 sont deux nombres premiers jumeaux et que 1950 est un produit de "petits" nombres premiers.
@ Rescassol
J'ai écrit un programme avec Maple en associant à chaque entier la liste des puissances des factorielles des nombres premiers consécutifs qui le représente, liste que je représente par un polynôme.
Par exemple $5= (2!)^{-2} (3!)^{-1} (5!)^{1}$ est représenté par la liste $(-2 , -1, 1)$ donc par le polynôme $P(5)=-2 -x + x^2$.
On a alors $P(ab)=P(a)+P(b)$.
Le programme utilise la fonction isprime(n) qui teste si n est premier, ithprime(k) qui affiche le k-ème nombre premier ainsi que degree et coeff pour passer du polynôme obtenu à la liste.
cidrolin:=proc(n0) local n,u,p,k,np,r: u(2):=1:u(3):=x-1:np:=1: for n from 4 to n0 do p:=2: while (n mod p) <>0 do p:=p+1 od: if p=n then # n est premier np:=np+1: # recherche du premier qui précède n p:=n-2: while not(isprime(p)) do p:=p-2 od: u(n):=x^np-x^(np-1)-add(u(k),k=p+1..n-1) else # n n'est pas premier u(n):=u(p)+u(n/p) fi od: p:=u(n0): r:=NULL: # pour transformer le polynôme p en liste for k from degree(p,x) to 0 by -1 do if coeff(p,x,k)<>0 then r:=r,[ithprime(k+1),coeff(p,x,k)] fi od: r end:cidrolin(2018); donne:[1009, 1], [997, -1], [503, -1], [491, 1], [83, 1], [79, -1], [71, 1], [67, -2], [61, 1], [59, -1], [47, 1], [37, -1], [31, 3], [23, -3], [19, 2], [13, -1], [11, 4], [7, -3], [5, -8], [3, -9], [2, 16]
Merci, Jandri, je vais tâcher de traduire ça en Python.
Cordialement,
Rescassol
$A=\{2,4,8,12,14,16,19,22,\cdots,1009,\cdots\}$ est stable par multiplication, pas par addition.
Amicalement
-- Schnoebelen, Philippe
Toutes ces suites sont stables par multiplication.
J’ai un code en Python qui fonctionne, il utilise la décomposition d’une factorielle en puissances de nombres premiers avec la formule qui va bien.
def cf(n,p): pp=p s=0 r=1 while True: r=n//pp if r: s+=r pp*=p else: break return s n=input().split() if len(n)==1: n,d=int(n[0]),1 else: n,d=map(int,n) nb=max(n,d) crible=[True]*(nb+1) crible[0:2]=False,False m=2 while m<=(nb+1)**.5: crible[2*m::m]=[False for _ in range(2*m,nb+1,m)] m+=1 while not crible[m]: m+=1 prem=[k for k in range(nb+1) if crible[k]] def liste(nb): div=dict() k=0 while nb!=1: if nb%prem[k]==0: div[prem[k]]=0 while nb%prem[k]==0: div[prem[k]]+=1 nb//=prem[k] k+=1 d=dict() while div: f=max(div) n=div[f] l={p:cf(f,p) for p in prem if p<=f} for p,e in l.items(): d[p]=e*n if p in div: div[p]-=e*n else: div[p]=-e*n div.pop(f) return d np=liste(n) dp=liste(d) for p,e in dp.items(): if p in np: np[p]-=e else: np[p]=-e s=sorted(np,reverse=True) print(" ".join("%d#%d"%(p,np[p]) for p in s if np[p] and p!=1))Dans ce code, (p!)k est noté p#k.-- Schnoebelen, Philippe
Pour $n=p_1^{(a_1)} \cdots p_k^{(a_k)}$ et $m=p_1^{(b_1)}\cdots p_k^{(b_k)}$ rationnels positifs je pose :
$f(n,m)=p_1^{(\min (a_1;b_1))} \cdots p_k^{(\min(a_k;b_k))}\quad$ ; $\quad g(n,m)=p_1^{(\max (a_1;b_1))} \cdots p_k^{(\max(a_k;b_k))}$ et $\quad h(n)= a_1+ \dots +a_k$ ( $h$ est totalement additive).
par exemple $f(7,5)= f(7^{(1)} 5^{(-1)} 3^{(-1)},5^{(1)} 3^{(-1)}2^{(-2)})=7^{(0)}5^{(-1)} 3^{(-1)}2^{(-2)}$ tandis que $g(7,5)=7^{(1)}5^{(1)} 3^{(-1)}2^{(0)}$ et $h(17)=-2$
Pour intéresser nos amis topologues, on peut définir une distance en posant : $d(n,m)=h(g(n,m))-h(f(n,m))$
J'ai pas pu m'empêcher de faire joujou moi aussi en copiant sur Jandri. Je l'ai suivi en ce qui concerne son codage (additif) des factorisations à la Cidrolin via les polynômes. Mais comme c'est pas moi qui paye, j'ai choisi d'utiliser des polynômes composés de monômes $a_pX^p$ avec $p$ premier, avec la signification $a_pX^p \leftrightarrow (p!)^{a_p}$.
Ma programmation est récursive et utilise les règles $(A), (B), (C)$ ci-dessous. Le polynôme associé à la factorisation de $n$ est noté $J_n$ (en l'honneur de Jandri) et la fonction récursive a le nom de Cidrolin pour l'initiateur du fil.
// n = (2!)^a_2 * (3!)^a_3 * (5!)^a_5 * ... --> J_n(X) = a_2 X^2 + a_3 X^3 + a_5 X^5 + .. // J pour Jandri // Ainsi J_1(X) = 0, J_2(X) = X^2, J_3(X) = -X^2 + X^3 because (2!)^-1 * (3!)^1 = 6/2 = 3 // Règles de calcul : // (A) J_1(X) = 0, J_2(X) = X^2 // (B) p < q premiers consécutifs : J_q(X) = X^q - X^p - somme des J_k(X) pour p < k < q (merci Jandri) // (C) J_{nm}(X) = J_n(X) + J_m(X) function Cidrolin(n) if n eq 1 then return ZX!0 ; end if ; // rule (A) if n eq 2 then return X^2 ; end if ; // rule (A) if IsPrime(n) then p := PreviousPrime(n) ; return X^n - X^p - &+[ZX| Cidrolin(k) : k in [p+1..n-1]] ; // rule (B) end if ; // La factorisation de n = p_1^e_1 * p_2^e_2 * .. est la séquence [<p_1,e_1>, <p_2,e_2>, ....] return &+[ e*Cidrolin(p) where p, e is Explode(pe) : pe in Factorisation(n)] ; // rule (C) end function ;Et voilà ce que cela donne pour $2018$. On voit le polynôme $J_{2018}$. Et ensuite, j'ai fait un truc ``pour la gueule'' comme on dit dans le métier. C'est le coup de la fonction Pretty ci-dessous. A l'aide du polynôme $J$, on élabore un groupe libre (non commutatif) ayant un générateur par monôme $a_pX^p$, le nom de ce générateur étant $(p)$. Et puis je passe de l'additif au multiplicatif.
> J := Cidrolin(2018) ; > J ; X^1009 - X^997 - X^503 + X^491 + X^83 - X^79 + X^71 - 2*X^67 + X^61 - X^59 + X^47 - X^37 + 3*X^31 - 3*X^23 + 2*X^19 - X^13 + 4*X^11 - 3*X^7 - 8*X^5 - 9*X^3 + 16*X^2 > Pretty(J) ; (2)^16 * (3)^-9 * (5)^-8 * (7)^-3 * (11)^4 * (13)^-1 * (19)^2 * (23)^-3 * (31)^3 * (37)^-1 * (47) * (59)^-1 * (61) * (67)^-2 * (71) * (79)^-1 * (83) * (491) * (503)^-1 * (997)^-1 * (1009)Eh bien, je me suis amusé. Merci à vous deux.
Pour la factorisation usuelle (celle où $40=2^3 \times 5$), la fonction $f$ est le pgcd, $g$ est le ppcm et $h$ est $\Omega$. Ici on ne peut pas utiliser ces mots là.
Merci Claude mais je ne mérite pas cet honneur!
C'est parce que le procédé de Cidrolin établit une bijection $f$ entre $\Q_+^*$ et les suites entières nulles à partir d'un certain rang que j'ai introduit $\Z[X]$. D'ailleurs cela munit $\Q_+^*$ d'une structure d'anneau isomorphe à $(\Z[X],+,.)$ avec comme première loi le produit des rationnels et comme seconde loi $a*b=f^{-1}(f(a)f(b))$.
Mais pour ce qu'on en fait en pratique il est plus clair comme tu l'as fait de n'utiliser que les monômes $a_pX^p$ avec $p$ premier.
L'autre jour, j'ai posté un peu vite sans mentionner assez d'explications. La fonction récursive en magma que j'ai fournie dans mon post provient de l'analyse de ton programme maple. Mon codage vérifie par définition $J_{p!}(X) = X^p$ pour $p$ premier. Et il est clair, que pour deux entiers premiers $p < q$
$$
q! = q \times \left(\prod_{p < k < q} k\right) \times p!
$$
que $p,q$ soient premiers ou pas, d'ailleurs. En donnant un coup de $J_\bullet$, on obtient ainsi
$$
X^q = J_q(X) + \sum_{p < k < q} J_k(X) + X^p \qquad \qquad (\heartsuit)
$$
C'est cela qui permet de calculer $J_q(X)$ de manière récursive. Et quand je dis que j'ai posté trop vite sans explication, c'est que viens d'une vieille école dans laquelle il était tout simplement interdit de fournir un programme sans en amener la documentation, voire la preuve. Je vais radoter mais tu es probablement trop jeune pour comprendre (Structured programming : Bohm-Jacopini theorem, 1966, Knuth, Structured programming with goto statements 1974, invariants Hoare, Arsac ...etc..). C'est ``à cette école'' que j'ai été formé par des informaticiens et il n'était pas recommandé d'écrire des fonctions de plus de 20 lignes, d'emboiter plus de 3 boucles (voire deux) ...etc..
De plus, pas trop de pédagogie quand on poste trop vite. La moindre des choses, c'est d'abord de fournir des petits exemples :
Et je couche encore $2018$ car avant le trick $(\heartsuit)$ pris chez toi, ma première version trop récursive ne me le donnait pas !
> J := Cidrolin(2018) ; > J ; X^1009 - X^997 - X^503 + X^491 + X^83 - X^79 + X^71 - 2*X^67 + X^61 - X^59 + X^47 - X^37 + 3*X^31 - 3*X^23 + 2*X^19 - X^13 + 4*X^11 - 3*X^7 - 8*X^5 - 9*X^3 + 16*X^2 > Pretty(J) ; (2)^16 * (3)^-9 * (5)^-8 * (7)^-3 * (11)^4 * (13)^-1 * (19)^2 * (23)^-3 * (31)^3 * (37)^-1 * (47) * (59)^-1 * (61) * (67)^-2 * (71) * (79)^-1 * (83) * (491) * (503)^-1 * (997)^-1 * (1009)Et puis, une fois que des choses sont un peu près au point, on peut s'amuser pour le fun. On dispose donc de deux bases du groupe multiplicatif $\Q_+^*$, la base des nombres premiers $(p)_{p \in P}$ et depuis Cidrolin (existence) et toi (unicité), de la base $(p!)_{p \in P}$. On va pas se gêner pour exprimer l'une dans l'autre à l'aide d'une matrice triangulaire (infinie) à diagonale unité. Ci-dessous, quelques exemples en prenant au lieu de $P$ l'ensemble des premiers entre $2$ et un premier donné.
Les matrices carrées sont indexées (lignes et colonnes) par des premiers. Par exemple, la petite matrice $2 \times 2$ ci-dessus, donne $J_2, J_3$ sur $X^2, X^3$.
A quoi cela sert ? A rien. Si : à faire joujou.
Si $n=p_1^{(a_1)}\cdots p_k^{(a_k)}$ et $m=p_1^{(b_1)}\cdots p_k^{(b_k)}$, on pose : $n$ éq $m$ ssi $|a_1|=|b_1|$ , $|a_2|=|b_2|$ , ... ,$|a_k|=|b_k|$.
C'est une relation d'équivalence dans l'ensemble $\Q^*_+$. Quand $n \neq 1$ il y a $2^k$ éléments dans $cl(n)$, la classe de $n$.
On a $cl(1)=\{ 1 \}\quad$; $\quad cl(2)=\{ 2,1/2 \}\quad$; $\quad cl(3)=\{ 3,1/3,12,1/12 \}\quad$; $\quad cl(4)=\{ 4,1/4 \}$
et $cl(5)=\{ 5,1/5,2880,1/2880,180,1/180,80,1/80 \}$.
Si $n$ éq $m$ alors $d(n,1)=d(m,1)$.
On peut constater qu'au début ($n \in \{1,2,3,\cdots,12\}$), la classe de $n$ ne contient que des entiers ou des inverses d'entiers. Quel est le plus petit entier dont la classe contient $x \notin \N$ tel que $\frac1x \notin \N$ ?
Débutant en Python, j'ai pu apprécier et utiliser le programme de Nicolas Patrois (tu)
$14=2^{(1)}3^{(-1)}5^{(-1)}7^{(1)}$ et $cl(14)$ contient $\dfrac72=2^{(-1)}3^{(-1)}5^{(-1)}7^{(1)}$.
J'ai réussi à obtenir la liste des équivalents de $n$, en ajoutant ces lignes au programme de Nicolas Patrois.
Il est possible sans doute de le peaufiner.
s=[p for p in s if np[p] and p!=1] from math import * A=[];t=0;s1=2**len(s)-1 while t<=s1: t1=int(bin(t)[2:]);B=[];t3=1 while t3<=len(s): t2=2*int(t1-10*floor(t1/10))-1 B=B+[t2] t3=t3+1 t1=floor(t1/10) t=t+1;nn=1 for p in s: nn=factorial(p)**(np[p]*B[s.index(p)])*nn A=A+[nn] print(A)Par exemple pour $90$, on a sa factorisation et sa classe:Une erreur à signaler ( un volontaire ?)
EXAMPLE
a(1)=0 (by convention).
a(2)=1 since 2=2!.
a(3)=0 since 3=3!/2!.
a(4)=2 since 4=2!*2!.
a(5)=-4 since 5=5!/(3!*2!*2!). C'est a(5)=-2
-- Schnoebelen, Philippe
-- Schnoebelen, Philippe
Je découvre avec retard ton incidente me concernant à propos du mot « factoriellisation ».
D'abord, je suis juste un usager de la langue française soucieux de son maniement avec correction, et non une autorité linguistique, donc il n'y a pas lieu de me demander pardon, spécialement à moi.
Pour ce qui est de ma position personnelle, je suis tout à fait favorable aux néologismes qui respectent ce qu'on pourrait appeler le génie de notre langue, et « factoriellisation » comme « cyclogone » vu dans un autre fil, me semblent parfaitement convenables. J'avais moi-même utilisé « continuisation » comme l'opération réciproque de la « discrétisation ». Et même « primitivation », pourtant impeccable, n'est toujours pas accepté par le correcteur d'orthographe.
Je suis parfaitement d'accord avec l'idée d'une langue qui évolue, comme tout corps vivant, mais qui évolue conformément à sa nature propre, et non par insertion forcée de vocables étrangers, ni par altérations délibérées comme le parler-racaille, ni par autoritarisme idéologique comme la dite « écriture-inclusive ». Le petit rhinocéros devient un grand rhinocéros, il ne devient pas un grand hippopotame, comme dirait Alexandre Vialatte.
Si tu faisais une faute par mot - voire plus - comme certains barbares qui osent venir poser ici des questions et refuser agressivement de se corriger, c'est là que tu devrais demander pardon, et pas à moi mais à tous tes lecteurs. Mais comme on dit familièrement : « c'est pas demain la veille ».
Bien cordialement,
Fr. Ch.
02/12/2017