|
#1 - 18-07-2020 15:31:40
- Sydre
- Professionnel de Prise2Tete
- Enigmes résolues : 15
- Messages : 245
vrible carré
Salut
On note [latex]\sigma[/latex] la fonction qui à [latex]n\in\mathbb{N}[/latex] associe le nombre de restes [latex]r\in\mathbb{N}<n[/latex] tels que [latex]nq+r[/latex] puisse être carré avec [latex]q\in\mathbb{N}[/latex]
Par exemple [latex]\sigma(3)=2[/latex] car un carré peut être de la forme [latex]3q+0[/latex] ou [latex]3q+1[/latex] mais pas [latex]3q+2[/latex]
Expliciter [TeX]\lim_{n\to +\infty}\frac{\sigma(n)}{n}[/TeX] Spoiler : [Afficher le message] En déduire un résultat relatif à la densité des carrés dans [latex]\mathbb{N}[/latex]
#2 - 18-07-2020 20:02:19
- nodgim
- Elite de Prise2Tete
- Enigmes résolues : 0
- Messages : 3802
Criblle carré
Es tu sûr d'avoir identifié une limite unique ?
#3 - 18-07-2020 21:58:44
- Sydre
- Professionnel de Prise2Tete
- Enigmes résolues : 15
- Messages : 245
croble carré
@nodgim Spoiler : [Afficher le message] L'énoncé ne dit rien sur la nature de la limite
Dire qu'elle est indéterminée est une réponse valable mais il faut le démontrer.
#4 - 19-07-2020 09:30:19
- nodgim
- Elite de Prise2Tete
- Enigmes résolues : 0
- Messages : 3802
Criblle carré
On montre facilement que ce rapport vaut 1/2 pour les nombres premiers et 1/4 au plus pour les multiples de 4.
En revanche, je n'ai pas compris la remarque sur la densité des carrés dans N. Elle est nulle, bien sûr, mais qu'attends tu comme réponse ?
#5 - 20-07-2020 09:20:51
- scarta
- Elite de Prise2Tete
- Enigmes résolues : 49
- Messages : 1960
Crible acrré
De mémoire (je l'ai déjà fait il y a longtemps...), les fonctions "nombre de résidus quadratiques de Zn" et "nombre de y admettant une solution à x²=y dans Zn" sont toutes les deux multiplicatives - et on pouvait facilement les calculer pour une puissance de p un premier quelconque
Mais bon de toutes les façons la densité des carrés dans Z est nulle (si je peux sauter directement à la fin)
#6 - 20-07-2020 11:52:52
- scarta
- Elite de Prise2Tete
- Enigmes résolues : 49
- Messages : 1960
Crile carré
Soit s(n) le nombre de carrés dans Zn - i.e. le nombre de y dans 0..n-1 présentant une solution à x²=y, modulo n Soit q(n) le nombre de résidus quadratiques dans Zn - les y ci-dessus qui sont premiers avec n.
Montrons que s et q sont multiplicatives - i.e. si m et n sont premiers entre eux, s(m.n) = s(m).s(n) et idem q(m.n) = q(m).q(n) Soient m et n premiers entre eux : Z(m.n) est identique à Zm x Zn, à un isomorphisme près z -> la paire (z mod m, z mod n)
- Soient un carré dans Z(m.n) : x et y tels que x² = y mod m.n, on a (x mod m)² = (y mod m) mod m.n, et idem mod n. - Soient un carré dans Zm et un autre dans Zn : (x1*x2)² = (y1*y2) mod m.n
Tout carré dans Z(m.n) correspond donc à une paire de carrés (un dans Zm et un dans Zn) et vice versa : donc s(mn) = s(m).s(n).
De là, on montre pareil pour q puisque y premier avec m.n implique y premier avec m et y premier avec n.
Une fois ce résultat démontré, considérant la décomposition en nombres premiers n=produit(p_i^alpha_i), s(n)=produit(s(p_i^alpha_i)) et idem pour q Reste plus qu'à déterminer s et q pour des puissances de nombres premiers. Soit p premier. Les carrés de Z(p^n) se décomposent en deux parties : - les résidus quadratiques - et les autres qui ne sont pas premiers avec p^n ==> donc multiples de p
Un carré non résidu est donc multiple de p (et même de p² puisque carré). On obtient donc la formule suivante s(p^n) = q(p^n) + s(p^(n-2)) En effet, puisque chaque carré non résidu est un multiple de p², il correspond à un carré modulo p^(n-2) multiplié par p² ensuite
Exemple avec les puissances de 3 3^2 - 1, 4, 7 résidus - 0 carré 3^4 - 1, 4, 7 , 10 , 13 , 16 , 19 , 22 , 25 , 28 , 31 , 34 , 37 , 40 , 43 , 46 , 49 , 52 , 55 , 58 , 61 , 64 , 67 , 70 , 73 , 76 , 79 résidus - 0, 9, 36, 63 autres carrés Et (0, 9, 36, 63) sont bien 9* (0, 1, 4 7) trouvés pour 3^2
A partir de là c'est plus facile. On peut trouver q pour p impair à partir de l'indicatrice phi (c'est phi/2) Phi est elle même est vachement simplifiée par le fait qu'on considère p^n, et phi(p^n) = p^(n-1)(p - 1) ou encore p^n - p^(n-1) Accessoirement, s(p^0) = s(1) = 1 et s(p) = q(p) + 1 (puisque tous les carrés sont des résidus sauf 0)
En faisant marcher la formule de récurrence, on a s(p^2k) = q(p^2k) + q(p^2k-2) + q(p^2k-4) + ... + q(p²) + s(p^0) = somme((-p)^j, j=1..2k)/2 + 1 = (p^(2k+1)-p)/2(1+p) + 1 s(p^(2k+1)) = q(p^2k+1) + q(p^2k-1) + q(p^2k-3) + ... + q(p^3) + q(p) + 1 = -somme((-p)^j, j=0..2k+1)/2 + 1 = (p^(2k+2)-1)/2(p+1) + 1 En rentrant le 1 sur le même dénominateur, on a - s(p^n) = (p * (p^n + 1) + 2) / (2p+2) pour n pair - s(p^n) = (p * (p^n + 2) + 1) / (2p+2) pour n impair
C'est joli non ? Par exemple, pour 45, on a s(9)*s(5) = 4*3 = 12, et il y en a effectivement 12 : 0 , 1 , 4 , 9 , 10, 16 , 19, 25 , 31, 34, 36 et 40 Pour p=2, je me rappelle plus, mais y'avait une astuce. Ca me reviendra
Ca n'aidera pas à calculer ta limite Mais je trouvais la formule jolie
#7 - 20-07-2020 14:08:17
- Sydre
- Professionnel de Prise2Tete
- Enigmes résolues : 15
- Messages : 245
crinle carré
@nodgim Spoiler : [Afficher le message]
On montre facilement que ce rapport vaut 1/2 pour les nombres premiers
Par exemple, oui. Curieux de voir tes arguments cependant !
1/4 au plus pour les multiples de 4
[latex]\frac{1}{2}[/latex]au plus pour les multiples de [latex]4[/latex]. Il faut quand même démontrer la décroissance pour conclure.
Reste à voir si on ne peut pas déterminer la limite pour des suites extraites d'entiers bien choisies (et pourquoi pour ces suites il n'y a pas d'indétermination ?).
Pour la remarque : je pensais pouvoir montrer un résultat intéressant du au fait que comme la densité des carrés dans [latex]\mathbb{N}[/latex] est nulle et évidemment [latex]\lim_{n\to +\infty}\sigma(n)=+\infty[/latex] les cribles associés aux différents [latex]n[/latex] ne "s'alignent" pas, mais à la relecture j'ai été un peu vite en besogne. A oublier pour l'instant donc.
@scarta Je vais prendre le temps de lire tout ça
#8 - 20-07-2020 16:38:50
- scarta
- Elite de Prise2Tete
- Enigmes résolues : 49
- Messages : 1960
Crible caré
Voilà j'ai tout retrouvé Les formules pour les puissances de deux sont trouvables à partir de q(2^n), qui vaut 1 pour 2 et 4, et sinon 2^n/8 (je peux formaliser la démo au besoin mais bon) Du coup, en sommant les q(), on trouve les s(), comme avant.
Donc, les formules sont: [TeX]
s(2^n) = \frac{2^{n-1}+4}{3} \text{ pour n pair}\\ s(2^n) = \frac{2^{n-1}+5}{3} \text{ pour n impair}\\ s(p^n) = \frac{p.(p^n+1) + 2}{2p+2} \text{ pour n pair}\\ s(p^n) = \frac{p.(p^n+2) + 1}{2p+2} \text{ pour n impair}\\ s(m.n) = s(m).s(n) \text{ pour m et n premiers entre eux} [/TeX] Ca permet un calcul très rapide du résultat - pour un nombre à 15 chiffres je fais du 5 millièmes de secondes sans même filtrer sur les nombres premiers!!! Ex : [latex]\sigma(123456789101112) = 7719215530650[/latex]
Et pour 1234567891011121314151617181920 : 13503132102537699880289461920 en 5 secondes.
#9 - 20-07-2020 17:03:10
- nodgim
- Elite de Prise2Tete
- Enigmes résolues : 0
- Messages : 3802
Crible carér
Je dis bien 1/4 au plus ( comme limite) pour les nombres de la forme 4n. Disons plus précisément 1/4 pour les nombres de la forme 4p, p premier.
En effet, soient les expressions :
(n+k)² = n²+k² + 2kn (n-k)² = n² + k² - 2kn
Différence : 4kn.
n est donc axe de symétrie pour un nombre 4n, puisque (n+k)² et n-k)² ont même valeur modulo 4n, puisque la différence 4kn = 0 [4n]
Ensuite, il y a du cas par cas lorsque n est composé, 4n ou pas. Dans ce cas, y²-x² = 0 [n] est possible, ce qui ne l'est pas avec des nombres premiers ( hormis de part et d'autre de la moitié ). Je n'ai pas creusé la limite min de s(n)/n, mais si on veut beaucoup y²-x² = 0 [n], il faut n avec beaucoup de diviseurs, ce qui fait grandir le nombre. Pas sûr qu'on fasse bouger beaucoup la limite 1/2 ou 1/4 .
#10 - 20-07-2020 19:07:05
- Franky1103
- Elite de Prise2Tete
- Enigmes résolues : 49
- Messages : 3220
- Lieu: Luxembourg
croble carré
Le fait que la densité des carrés dans N soit nulle ne me semble pas contrintuitif, mais j'ai appris à me méfier de l'infini: LOL
#11 - 20-07-2020 21:19:53
- Sydre
- Professionnel de Prise2Tete
- Enigmes résolues : 15
- Messages : 245
criblz carré
@nodgim
Oui d'accord, j'avais mal compris ton précédent message
@scarta
Bravo, il me semble que tu as presque tout dit !
On en déduit directement pour quelles suites d'entiers la limite de l'énoncé converge et vers quelles valeurs.
#12 - 21-07-2020 09:19:51
- scarta
- Elite de Prise2Tete
- Enigmes résolues : 49
- Messages : 1960
crinle carré
Oui, en effet. Considérant les nombres premiers par exemple, on à [latex]\frac{\sigma(p)}{p} = \frac{p+1}{2p}[/latex], limite = [latex]\frac{1}{2}[/latex]
Pour un nombre square-free, on ne converge pas : la valeur est en [latex]\frac{1}{2^q}[/latex] avec q nombre de facteurs premiers, mais à aucun moment on atteindra u square-free suffisamment grand pour que le ratio soit inférieur à 1/2: il existera toujours un nombre premier plus grand que ce square-free pour lequel le ratio sera 1/2
Du coup, pour répondre à la question la limite n'existe pas puisque le ratio ne converge pas. La définition d'une limite est la suivante: soit L la limite, si elle existe : pour tout [latex]\epsilon > 0 [/latex] aussi petit qu'on veut, il existe un [latex]N[/latex] tel que pour tout [latex]n>N[/latex], [latex]|\frac{\sigma(n)}{n} - L| < \epsilon[/latex].
Là, l'apparition de valeurs pour des valeurs de n premier empêchent toute convergence. Le fait de pouvoir converger sur des sous-suites ne prouve pas grand chose - et de toute façon, puisque le ratio est compris entre 0 et 1, il est borné, et d'après le théorème de Bolzano-Weierstrass on peut en extraire une sous-suite convergente.
Moi être content Je crois bien que c'est la première fois en 18 ans que je ressors ce théroème
|
|