Enigmes

Forum dédié aux énigmes et à toutes formes de jeux de logique.

Déconnexion

Tu n'es pas identifié sur Prise2tete : s'identifier.

accueil Accueil forum Forum
[+]

 #1 - 18-07-2020 15:31:40

Sydre
Professionnel de Prise2Tete
Enigmes résolues : 15
Messages : 217

criblz carré

Salut smile

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]



Annonces sponsorisées :
  • |
  • Répondre

#0 Pub

 #2 - 18-07-2020 20:02:19

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3786

crinle 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 : 217

xrible carré

@nodgim
Spoiler : [Afficher le message]
L'énoncé ne dit rien sur la nature de la limite smile

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 : 3786

Crible 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 : 1656

Crible carrré

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 : 1656

Crible caré

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 smile
Mais je trouvais la formule jolie

 #7 - 20-07-2020 14:08:17

Sydre
Professionnel de Prise2Tete
Enigmes résolues : 15
Messages : 217

Crible ccarré

@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 lol

 #8 - 20-07-2020 16:38:50

scarta
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 1656

Crble carré

Voilà j'ai tout retrouvé smile
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 : 3786

ctible carré

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 : 3063
Lieu: Luxembourg

Crble 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 : 217

Criible carré

@nodgim

( comme limite)

Oui d'accord, j'avais mal compris ton précédent message smile

@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 : 1656

rCible 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 smile
Je crois bien que c'est la première fois en 18 ans que je ressors ce théroème smile

 

Réponse rapide

Rédige ton message
| | | | Upload | Aide
:) :| :( :D :o ;) :/ :P :lol: :mad: :rolleyes: :cool:
Sécurité

Répondez (numériquement) à la petite énigme suivante : 

Un berger a 30 moutons, ils meurent tous sauf 15, combien en reste-t-il ?

Pied de page des forums

P2T basé sur PunBB
Screenshots par Robothumb

© Copyright 2002–2005 Rickard Andersson

Prise2Tete Forum Statistiques Liste des membres Hall of Fame Contact
© Prise2tete - Site d'énigmes et de réflexion.
Un jeu où seules la réflexion, la logique et la déduction permettent de trouver la solution.

Flux RSS de Prise2Tete Forum Jeux & Prise2Tete Test & Prise2Tete Partenariat et Publicité sur Prise2Tete