Inscription / Connexion Nouveau Sujet
Niveau terminale
Partager :

Combien il y à t-il de carrés inférieurs à un nombre donné

Posté par
Guimzo
22-09-16 à 23:56

Bonjour,

Qui aurait des pistes s'il vous plaît, pour un petit probléme de dénombrement.
L'indicatrice d'Euler nous dit que la quantité de nombres qui sont inférieurs à n et premiers avec n peut être calculée selon la formule :

Phi(n) = n*(1-1/p1)*(1-1/p2)*(...)*(1-1/k)
p1,p2,pk étant les facteurs premiers de n.

On sait aussi que la somme des carrés de 1 à n peut être calculée par la formule :
S(c) = (1/6)*n*(n+1)*(2n+1)

Ma question est de savoir comment calculer la quantité de nombres carrés qui sont inférieurs à un nombre n donné ?? ( par une formule comme les deux précédentes )

Exemple :
Soit le nombre donné 77
Les carrés qui sont inférieurs à 77 sont :
{1 ; 4 ; 9 ; 16 ; 25 ; 36 ; 49 ; 64 }

Il y à donc 8 carrés qui sont inférieurs à 77.
Existe t-il une formule qui permette de calculer ce nombre de carrés du même genre que pour Phi(n) ou S(c) etc....?

Merci

Posté par
lyceen
re : Combien il y à t-il de carrés inférieurs à un nombre donné 23-09-16 à 09:01

Bonjour,

Selon moi, il suffit de prendre la partie entière de la racine de ton nombre, et tu obtiens le nombre de carrés inférieurs...

Si n=77,  8 \le \sqrt{n}  \le 9, donc il y a 8 carrés.

Posté par
Guimzo
re : Combien il y à t-il de carrés inférieurs à un nombre donné 23-09-16 à 10:59

Bonjour,
Merci @lyceen pour ta réponse ; effectivement, ce nombre correspond en réalité à la partie entière de la racine carrée du nombre de départ.
Mais est-il possible de trouver cette quantité par une formule comme pour par exemple l'indicatrice d'Euler qui donne la quantité de nombres inférieurs à n et premiers avec n..??
Exemple de formule :

C(n) = 2*(p1-p2)
Avec p1 et p2 les facteurs de n
Pour 77 la formule est vérifiée ; mais ce n'est pas une formule qui rend compte de tous les nombres...

Posté par
lyceen
re : Combien il y à t-il de carrés inférieurs à un nombre donné 23-09-16 à 11:06

En toute honnêteté, je ne saurais te le dire. Je ne crois pas avoir étudié l'indicatrice d'Euler, je me suis basé sur une hypothèse.

Je préfère laisser les profs du site répondre.

Posté par
Guimzo
re : Combien il y à t-il de carrés inférieurs à un nombre donné 23-09-16 à 12:10

Merci en tout cas @Lycéen pour tes remarques.
En fait la question peut se traduire ainsi :
Comment calculer la partie entière de la racine carrée d'un nombre, sans connaître la racine carré du nombre, c'est à dire calculer la partie entière de la racine carrée de p uniquement à partir des facteurs de p...?

J'ai commencé à calculer ainsi :
Dans le cas où p n'aurait que 2 facteurs premiers , c'est à dire que

p = a² - b² = n *m avec n > m

En partant du fait que nous connaissons les facteurs n et m de p, nous allons nommer x cette partie entière de la racine carrée de p et poser :

a = (x+y)

On a donc y que l'on ne  connaît pas non plus.
Et notre équation devient :

p = (x+y)² - b²

Nous savons que b = a-m nous avons donc b = (x+y) - m
L'équation devient  :

p = (x+y)² - ( (x+y) - m )²

p = x²+y²-( (x+y-m)*(x+y-m))
p = x²+y² - ( x²+xy-mx+xy+y²-my-mx-my+m²)
p = x²+y² - ( x²+y²+m²+2xy-2mx-2my)
p= x²+y²-x²-y²-m²-2xy+2mx+2my

p= 2mx+2my-2xy-m²

Maintenant comment résoudre l'équation afin de trouver x et y ..???

Posté par
Guimzo
re : Combien il y à t-il de carrés inférieurs à un nombre donné 23-09-16 à 12:50

Bonjour,
Désolé, il y à une petite erreur dans :
========================================
p = (x+y)² - ( (x+y) - m )²

p = x²+y²-( (x+y-m)*(x+y-m))
p = x²+y² - ( x²+xy-mx+xy+y²-my-mx-my+m²)
p = x²+y² - ( x²+y²+m²+2xy-2mx-2my)
p= x²+y²-x²-y²-m²-2xy+2mx+2my

p= 2mx+2my-2xy-m²
=====================================

J'ai oublié le 2xy dans le développement de (x+y)²
Donc l'équation finale n'est pas p = 2mx+2my-2xy-m²

Mais
p =  2mx+2my-m²

Posté par
lyceen
re : Combien il y à t-il de carrés inférieurs à un nombre donné 23-09-16 à 13:07

Merci pour cette explication, je sens que je me pencherai dessus dans les jours qui suivent.

Posté par
Guimzo
re : Combien il y à t-il de carrés inférieurs à un nombre donné 23-09-16 à 13:12

Du coup l'équation :
p= 2mx+2my-m²

est une identité de Bézout :

(2m)x + (2m)y = (p+m²)

Et au final, nous avons comme solutions de l'équation :
{x = [(n+m)/2] - k ; y = k} avec k étant un nombre entier quelconque.

Le probléme n'est donc pas résolu ; il y à t-il donc une autre  façon pour calculer la partie entière de la racine carrée de p sans connaître sa racine carrée...??

Posté par
Guimzo
re : Combien il y à t-il de carrés inférieurs à un nombre donné 23-09-16 à 17:53

Une autre piste :
( Dans le cas où notre nombre n'est composé que de 2 facteurs premiers )

Notre nombre p =77 = 11 * 7
Phi(77) = (11-1)*(7-1) = 10*6 = 60

Nous savons donc qu'il y à 60 nombres inférieurs à 77 et qui sont premiers avec 77.
Parmi ces nombres il y à donc la quantité de nombres carrés cherchés,
Parmi Phi(77) comment éliminer d'autres nombres qui ne répondent pas à l'énoncé, par exemple les puissances de 3 du genre  2^3 ; 3^3 ; ...

Posté par
jsvdb
re : Combien il y à t-il de carrés inférieurs à un nombre donné 23-09-16 à 19:10

Bonjour guimzo

Pour un entier k donné, si n_k est le nombre de carrés parfaits qui lui soient inférieurs, on a effectivement \blue n_k =E(\sqrt k) + 1.
On peut la montrer rapidement :
Si p^2 \leq k < (p+1)^2 alors il y a n_k = p+1 carrés parfaits plus petits que k. Or p \leq \sqrt k < (p+1). Ce qui fait que p =E(\sqrt k).
D'où le résultat.

Je ne connais pas d'amélioration de ce résultat qui semble optimum d'ailleurs; la fonction partie entière faisant partie de ces petits monstres qui ne sont ni continus ni périodiques, qui ne vérifient même pas E(x^2) = E(x)^2, qui n'ont aucune propriété de linéarité potable. Enfin bref ! tout pour plaire.

Maintenant, si tu veux pousser un peu la recherche, tu peux faire ceci :

Montrer que  {\displaystyle \sum _{j=1}^{n}(2j-1)= n^{2}.}

Posté par
Guimzo
re : Combien il y à t-il de carrés inférieurs à un nombre donné 23-09-16 à 20:53

Bonsoir,
Merci @jsvd pour ta participation.
Mais nk n'est pas égal à E(sqrt(k))+1
nk est égal à E(sqrt(k))

La question n'est pas de montrer que la somme des n nombres impairs consécutifs est un carré...
Le probléme est de savoir comment calculer la partie entière de la racine carrée d'un nombre donné, sans connaître la racine du nombre...??
Autrement dit la quantité de nombres carrés qui sont inférieurs à un nombre donné n qui n'est pas lui-même un carré..??

Posté par
carpediem
re : Combien il y à t-il de carrés inférieurs à un nombre donné 23-09-16 à 21:18

salut

par définition E(x) est le nombre d'entiers non nuls inférieurs à x

donc E(\sqrt n) est le nombres d'entiers non nul dont le carré est inférieur à n

et si on a nommé (car elle existait bien avant l'homme) la fonction partie entière c'est justement parce qu'on ne peut pas faire autrement ...


en d'autres termes pour compter le nombre d'entiers dont le carré est inférieur à n il n'y a pas d'autres moyens que de compter le nombre d'entiers dont le carré est inférieur à n et qu'on notera E(\sqrt n)

....

Posté par
Guimzo
re : Combien il y à t-il de carrés inférieurs à un nombre donné 23-09-16 à 22:46

Bonsoir,
Merci @carpediem pour tes explications ; mais j'ai du mal à croire que l'on ne pourrait calculer cette quantité de nombres carrés, autrement que par le calcul de la racine carrée...
Quelqu'un aurait-il prouvé que l'on ne pouvait calculer cette quantité autrement..?
Aurais-tu s'il te plaît un lien vers cette preuve..?

Posté par
jsvdb
re : Combien il y à t-il de carrés inférieurs à un nombre donné 24-09-16 à 09:52

Guimzo @ 23-09-2016 à 20:53

Bonsoir,
Merci @jsvdb pour ta participation.
Mais n_k n'est pas égal à E(\sqrt k)+1
n_k est égal à E(\sqrt k)


Si tu considères que 0 n'est pas un carré parfait, oui.

n_0 = E(\sqrt 0)+1=1
n_1 = E(\sqrt 1)+1=2
n_4 = E(\sqrt 2)+1=3
***
n_{122} = E(\sqrt {122})+1=12

Maintenant, avec Carpediem, on te dit que dans l'état actuel de nos connaissances de chercheurs et enseignants agrégation, on n'a pas d'autres formules.
Dans nos posts, on t'a proposé des pistes de réflexion (qui dépassent un peu le cadre de la terminale) pour essayer de te montrer qu'on ne peut pas faire autrement : cela ne constitue pas une preuve, mais tu vas devoir t'en contenter.

Posté par
jsvdb
re : Combien il y à t-il de carrés inférieurs à un nombre donné 24-09-16 à 10:45

Maintenant, si  la question t'intéresse à ce point, tu peux regarder comment sont répartis les carrés :

0
1 2 3
4 5 6 7 8
9 10 11 12 13 14 15
16 17 18 19 20 21 22 23 24
25 26 27 28 29 30 31 32 33 34 35
36 ....
(n-1)² ((n-1)²+1) ((n-1)²+2) ((n-1)²+3) ... ((n-1)²+2n - 2) ((n-1)²+2n - 1)


Donc, le problème revient au suivant :
On note I_n = [[n², n² + 2n]] pour tout entier n.
Etant donné un entier k, peut-on trouver une fonction \psi : \N \rightarrow \N  telle que k \in [[\psi (k)^2, \psi (k)^2 + 2.\psi (k)]] .

La réponse est oui et était contenu dans ce que tu croyais n'être pas le problème, savoir, montrer que  \displaystyle {\sum _{j=1}^{n}(2j-1)= n^{2}.}
 \\

Maintenant, la tête de la fonction \psi , je ne la connais que par le biais de  ... E(\sqrt k)

Une autre façon de voir le problème globalement :
Peut-on résoudre une équation du second degré à coefficients réels sans passer par le discriminant et des racines carrées ? Si la réponse est oui, alors je veux savoir tout de suite.

Autre façon de voir le problème :
On ne peut pas exprimer la racine d'un nombre entier à priori quelconque sous la forme \dfrac{p}{q} avec p \in \Z et q \in \N^*. Pas besoin de lien pour savoir si quelqu'un l'a démontré. C'est archi-classique.

Conclusion : la forme la plus simple de la fonction \psi est \psi(k) = E(\sqrt k) .

Maintenant, ce que l'on peut éventuellement faire, c'est de trouver un équivalent de E(\sqrt k)k \in [[n², n² + 2n]] pour n tendant vers l'infini, le tout par le biais de formule de Taylor et compagnie. Mais même là, j'ai peur qu'on ne soit pas plus avancé.

Posté par
Guimzo
re : Combien il y à t-il de carrés inférieurs à un nombre donné 24-09-16 à 13:30

Bonjour,
Merci @jsvd pour tes amples explications.
Donc du coup dans l'état actuel des connaissances on ne peut pas calculer* ne serait-ce que le nombre carré précédent un nombre quelconque donné....??!
C'est quand même extraordinaire, que l'on sache calculer la quantité de nombres pairs ou impairs inférieurs à un nombre donné, la quantité* de nombres premiers inférieurs à n, .... mais la quantité de nombres carrés inférieurs à un nombre donné serait impossible à calculer et reviendrait à calculer une racine carré sous la forme p/q...
Merci pour vos éclaircissements

Posté par
carpediem
re : Combien il y à t-il de carrés inférieurs à un nombre donné 24-09-16 à 17:30

si on peut ...

même un esclave (un robot) peut le faire pour nous ...



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

Inscription gratuite

Fiches en rapport

parmi 1733 fiches de maths

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 !