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 - 08-10-2018 08:35:57

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

Noombres a²+b²

Bonjour @ tous.

Je me demandais comme ça en passant si la densité des nombres < n donné,  qu'on peut écrire sous la forme a² + b² augmentait ou diminuait avec n.....

On comptera pour 2 fois ( ou plus) un nombre qui s'écrit de 2 ( ou plus ) façons
différentes, par exemple 25 = 5² + 0² = 3² + 4² .

Bonne recherche

  • |
  • Répondre

#0 Pub

 #2 - 08-10-2018 17:59:56

enigmatus
Expert de Prise2Tete
Enigmes résolues : 0
Messages : 561

Nombres a²b²

Salut nodgim,
L'ensemble des points de coordonnées entières (a,b), tels que a**2 + b**2 < n**2, avec b<a, sont situés dans le huitième du cercle de centre O et de rayon n, limité par l'axe des x et la première bissectrice.
Le nombre de tels points est environ égal à l'aire de cette portion de cercle, soit pi*n**2/8.
La proportion des points doit donc tendre vers pi/8 = 0,3927.

Un calcul exact avec n=200 donne un rapport de 0,3969.

 #3 - 09-10-2018 08:09:17

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

Nombres a+b²

Salut Enigmatus.
C'est bien l'idée. En revanche, je ne suis pas tout à fait d'accord quand tu dis que le nombre de points est équivalent à l'aire. C'est précisément en examinant cet écart qu'on peut se faire une idée de la réponse.

 #4 - 09-10-2018 08:40:38

enigmatus
Expert de Prise2Tete
Enigmes résolues : 0
Messages : 561

nolbres a²+b²

Sauf sur les bords, dont l'importance relative diminue avec le rayon du cercle, on peut associer chaque point à une zone d'une unité d'aire.

J'ai poursuivi le calcul jusqu'à n=4000, c'est-à-dire a**2+b**2 ≤ 16000000, et j'obtiens un rapport de

Code:

6286581 / 16000001 = 0.392911

Ajouté :
Et pour n=10000

Code:

39278418 / 100000001 = 0.392784

 #5 - 09-10-2018 15:31:02

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

Nomrbes a²+b²

Merci pour tes chiffres, Enigmatus.

Avec la formule approximative que j'ai trouvée :

6287028 pour n = 16 * 10 ^ 6 soit ratio = 0,392939...

39279516 pour n = 10 ^ 8 soit ration = 0,392795....

Des données un peu plus fortes que le réel, mais assez proches tout de même.

Ce sont bien les bords qui jouent un rôle dans cette histoire.
Reste à en mesurer les effets le plus finement possible.

 #6 - 09-10-2018 18:08:15

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

nombres a²+v²

En fait, je me demande si l'excés dans ma formule n'est pas due au fait que tu as choisi comme frontière des carrés parfaits. Visuellement, ça peut s'expliquer.

Bien entendu, la formule en question est une approximation.

 #7 - 09-10-2018 20:31:28

enigmatus
Expert de Prise2Tete
Enigmes résolues : 0
Messages : 561

Nombrees a²+b²

J'aurais dû adopter la même notation que toi, et comparer a**2+b**2 à n, et non à n**2 comme je l'ai fait.

Ça ne change rien au raisonnement, et mon script peut traiter des limites supérieures n quelconques. Les valeurs max pour a et b sont alors int(sqrt(n)).

Dis-moi quelles valeurs tu veux comparer avec les tiennes.

 #8 - 10-10-2018 09:18:36

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

Nombes a²+b²

Merci Enigmatus.

Alors, pour en rester à l'ordre de grandeur des 2 valeurs calculées :

n = 16*10^8 + 10^3

n = 10^8 + 10 ^ 4

Il ne faudrait pas non plus que je d'adapte ma formule aux résultats, ce serait tricher.....

 #9 - 10-10-2018 09:32:04

enigmatus
Expert de Prise2Tete
Enigmes résolues : 0
Messages : 561

Nombres ²a+b²

Voici déjà pour la seconde valeur :

Code:

N2=100010000 N=10000
Nombre de valeurs distinctes = 18459656
100010000 =>  39282396 / 100010001 = 0.392785

Ajouté :
Je n'arrive pas à traiter la première valeur : mémoire saturée et ordinateur bloqué.

 #10 - 10-10-2018 16:24:41

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

Nombbres a²+b²

Excuse Enigmatus, j'avais 16*10¨8 + 10^3 alors que je voulais écrire 16*10^6 + 10^3.

Sinon, tu as précisé " valeurs distinctes". Or dans l'énoncé, j'ai précisé que des valeurs identiques pouvaient être trouvées pour certains nombres, mais qu'il fallait les compter pour autant de valeurs. En vérité, il s'agit bien de compter les points dans la partie de plan en question.

 #11 - 10-10-2018 17:18:14

enigmatus
Expert de Prise2Tete
Enigmes résolues : 0
Messages : 561

Nobres a²+b²

Ça va tout de suite mieux :

Code:

N2=16001000 N=4000
Nombre de valeurs distinctes = 3127096
16001000 =>  6287002 / 16001001 = 0.392913

Le nombre de valeurs distinctes est donné à titre indicatif. C'est bien le nombre total de points que j'utilise pour le calcul.

 #12 - 10-10-2018 17:47:06

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

Nombres a+²b²

D'après le théorème des 2 carrés de fermat, ça revient à faire la somme
[TeX]{\sum_{i=1}^n{4*(d_1(i)-d_3(i))}}/n[/TeX]
où d1 / d3 sont les nombres de diviseurs de i congrus à 1 / 3 modulo 4.

J'imagine que je devrais pouvoir coder ça rapidement (mais j'ai pas de quoi coder dans l'immédiat)

 #13 - 10-10-2018 19:01:28

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

Nombrees a²+b²

@ Enigmatus: D'accord merci.

Tu observeras que les densités ont sensiblement augmenté en augmentant légèrement les valeurs de n, ce qui était plus ou moins attendu au franchissement d'un carré parfait, mais ce qui est contraire à la tendance sur une plus grande échelle. Si ma formule donne une valeur excédentaire pour un carré parfait, elle donne une valeur déficitaire quand on s'éloigne du carré parfait. ( Ma formule donnne les mêmes valeurs de densité entre 10 ^ 8 et 10 ^ 8 + 10 ^ 4, écart trop faible).

As tu une idée de la façon dont le calcul approximatif peut se faire ?   

Tu doit pouvoir trouver un intervalle de confiance, et en déduire que dans le pire des cas, la densité est toujours décroissante entre 2 nombres quand le rapport entre le plus grand et le plus petit dépasse une certaine valeur.

 #14 - 11-10-2018 10:11:45

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

nombres z²+b²

Après codage et affichage graphique, je trouve ça
http://www.prise2tete.fr/upload/scarta-density.png

Les données de 1000 en 1000 sont ici http://www.prise2tete.fr/upload/scarta-res.txt

C'est bizarre, ça m'a l'air assez différent des 0.39... mentionnés

 #15 - 11-10-2018 14:56:59

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

Nobres a²+b²

Pardon Scarta, mais pour ton graphique, que représente l'axe 0y ?

 #16 - 11-10-2018 23:27:24

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

Nombrse a²+b²

Le ratio « nombre d’écritures différentes /n »
En fait je viens de réaliser qu’on pouvait faire bien plus simple comme calcul, plutôt que de compter les diviseurs.
Pour n donné, il suffit plutôt de calculer la somme pour i=0..racine(n) de E(racine(n))E(racine(i))

 #17 - 12-10-2018 08:11:37

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

Nombers a²+b²

Ton graphique ne convient pas, ce ratio ne tourne pas aux environs de 2.

Je me demande si tu as bien compris l'énoncé ?

 #18 - 12-10-2018 12:12:42

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

Nombres ²a+b²

la densité des nombres < n donné,  qu'on peut écrire sous la forme a² + b² augmentait ou diminuait avec n.....

On comptera pour 2 fois ( ou plus) un nombre qui s'écrit de 2 ( ou plus ) façons
différentes, par exemple 25 = 5² + 0² = 3² + 4² .


Je comprends:

- pour n donné, je cherche le nombre de paires (a,b) tels que a²+b²<n
je prends des paires puisque on compte pour x fois les x écritures d'un même nombre

- du coup, comme on compare des paires par rapport à des nombres, oui la densité peut être supérieure à 1.

- et comme rien n'indique a > 0 ou b > 0 ou a < b, chaque paire compte pour 8 fois : (+/-a,+/-b) et (+/-b,+/-a)

pour n=6 par exemple, j'ai
0 = 0²+0²   ------> 1
1 = (+/-)1²+0² = 0²+(+/-)1²  --------> 4
2 = rien
3 = rien
4 = (+/-)2²+0²=0²+(+/-)2² -------->4
5 = (+/-)1²+(+/-2)² etc... ------->8
6 = rien
total : 17/6

si j'ai raté quelque chose, j'ai beau relire je vois pas quoi...

 #19 - 12-10-2018 16:28:29

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

Nombres ²a+b²

Bon allez, j'ai retrouvé le 0.39... en ne considérant qu'une seule solution là où je pouvais en avoir 8. Et j'ai aussi fait un bout de code basé sur mon (incompréhensible - même pour moi) post #16

Bref, donc je trouve en quasi instantané
1: 1.0
10: 0.5
100: 0.41
1000: 0.398
10000: 0.3942
100000: 0.39321
1000000: 0.39284
10000000: 0.3927466
100000000: 0.39271346
1000000000: 0.392703682
10000000000: 0.3927005327
100000000000: 0.39269954312
1000000000000: 0.39269922765
10000000000000: 0.3926991279607
100000000000000: 0.3926990963329
1000000000000000: 0.392699086329615
10000000000000000: 0.3926990831628172
100000000000000000: 0.3926990823437512
1000000000000000000: 0.3926990819764462

 #20 - 12-10-2018 16:30:39

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

Nmbres a²+b²

Accessoirement, je suis ébahi par 8x cette valeur: 3.141592655
Etant donné que ça signifie : "tous les points du plan à coordonnées entières, positives, et x<y, dans le disque de rayon n" (soit un 8e du disque), je pense qu'il y a un lien tongue

 #21 - 12-10-2018 17:56:55

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

Nombrres a²+b²

C'est bien cela Scarta !

Reste maintenant à tenter de répondre à la question posée sur la tendance de la densité. Tu y réponds déja en partie avec les données que ton ami t'a fournies, pourras tu le prouver ?

 #22 - 14-10-2018 11:57:16

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

nimbres a²+b²

Ce temps là est au fond du seau.

Valeurs numériques et modèles ont été donnés, il ne restait plus qu' à conclure en s'efforçant de donner un intervalle de densité max et min.

_____________________________________________________________
La densité des nombres somme de 2 carrés parfaits < n donné grandit t-elle avec n ?

On comptera pour k les nombres qui sont somme de 2 carrés parfaits de k façons différentes.

Ce problème revient à compter les points à coordonnées entières à l'intérieur du secteur angulaire de rayon Vn entre l'axe Ox et la droite d :  y = x

Aire du secteur As = Pi / 8. On note son point le plus haut H = Vn V2 / 2

On dessine à l'intérieur du secteur le polygone qui contient toutes les cases " aire unité " entières (entre 4 points en carré), c'est à dire non tronquées par le contour du secteur.

Aire du secteur hors polygone le long de la droite y = x............... Ad = H / 2 ( à l'unité près, nota général pour tout ce qui suit)

Aire du secteur hors polygone le long de l'arc de cercle Ac :........ ( H - H1 ) / 2 < Ac < H + ( Vn - H ) = Vn     
H1 : hauteur max où l'arc, en partant du bas, coupe la 1ère droite x = entier. H1 = V ( 2 Vn - 1 )
H + ( Vn - H) = Vn : l'ensemble des cases traversées par l'arc.

Aire du polygone Ap = As - Ad - Ac.

Ap max = ( Pi / 8) n  - H + H1 / 2 = ( Pi / 8 ) n - Vn V2 / 2 + V ( 2 Vn - 1 )
Ap min = ( Pi / 8 ) n - H / 2 - Vn = ( Pi / 8 ) n + Vn ( 1 - V2 / 2 )

Nombres de points :
A chaque case du polygone, on attribue son point en bas à droite.

Points hors Polygone :
Le long de la droite d : 2 H -1   
Le long de l'arc : autant que de franchissements par l'arc des droites x = entier, soit Vn ( 1 - V2 / 2 ) 

Nombre de points :

Pmax : 2H -1 + Vn ( 1 - V2 / 2 ) + Ap max = ( Pi / 8 ) n + Vn + V ( 2 Vn -1 ) - 1   

Pmin : 2H - 1 + Vn ( 1 - V2 / 2 ) + Ap min = ( Pi / 8 ) n + Vn ( V2 / 4 ) - 1 

Densité dn = P / (n+1)

dn max = ( Pi / 8 ) ( n / ( n + 1) ) + Vn / ( n + 1) + V( 2 Vn - 1 ) / ( 2 ( n + 1 ) ) - 1 / ( n + 1 )

dn min = ( Pi / 8 ) ( n / ( n + 1 ) ) + ( V2 / 4)  Vn / ( n + 1)  - 1 / ( n + 1)

Pour n < 20, calcul réel :  dn > Pi / 8  ( dn <= 1/2 seulement à partir de d33 )

Pour n  > 20, d min > Pi / 8

Or d max -------> Pi / 8 quand n -------> oo. Donc il existe m tel que dm max < dn min

Conclusion : la densité est globalement décroissante en ayant pour limite Pi / 8.

 

Réponse rapide

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

Répondez à la devinette suivante : 

Le père de toto a trois fils : Tim, Tam et ?

Sujets similaires

Sujet Date Forum
P2T
30-04-2009 Enigmes Mathématiques
P2T
Mere et fils par pollux6
06-09-2010 Enigmes Mathématiques
P2T
Papertron par Ebichu
03-04-2016 Enigmes Mathématiques
P2T
Cercle de la mort! par Kiko25
15-10-2018 Enigmes Mathématiques
P2T
24 avec 1,3,4,6 par RumKisser
05-12-2009 Enigmes Mathématiques
P2T
21-03-2008 Enigmes Mathématiques
P2T
Pliage en carré par nodgim
16-06-2013 Enigmes Mathématiques
P2T
Tableau maudit par carole085
18-08-2010 Enigmes Mathématiques
P2T
Combien de zéros? par papiauche
01-09-2008 Enigmes Mathématiques

Mots clés des moteurs de recherche

Mot clé (occurences)

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