Να βρεθεί το πλήθος ακεραίων

Ορέστης Λιγνός · #1

Για πόσες θετικές ακέραιες τιμές του $x \leqslant 1000$ , έχει η εξίσωση $\sqrt{x}=\sqrt{a}+\sqrt{b}$ μία τουλάχιστον ακέραια λύση, με τους a,b

επίσης θετικούς ακεραίους;

nikkru · #2

Ορέστης Λιγνός έγραψε: Παρ Αύγ 31, 2018 8:40 pm Για πόσες θετικές ακέραιες τιμές του $x \leqslant 1000$ , έχει η εξίσωση $\sqrt{x}=\sqrt{a}+\sqrt{b}$ μία τουλάχιστον ακέραια λύση, με τους επίσης θετικούς ακεραίους;

ΕΜΦΑΝΙΣΗ ΚΕΙΜΕΝΟΥ

min## · #3

ΕΜΦΑΝΙΣΗ ΚΕΙΜΕΝΟΥ

min## · #4

Θα μετρηθούν οι square-free από το

μέχρι το

.
Θεωρώ σύνολα $S_{i}=\left \{ \right.p_{i}^2,2p_{i}^2,3p_{i}^2,...,\left \lfloor 1000/p_{i}^2 \right \rfloor\left. \right \}$ ,με $p_{1}=2,p_{2}=3,...$ και έστω $p_{m}$ ο τελευταίος πρώτος το τετράγωνο του οποίου δεν υπερβαίνει το 1000

(δηλαδή το

).Από αρχή εγκλεισμού,αποκλεισμού,είναι : $\left | S_{1}\cup S_{2}\cup ...S_{m} \right |=\sum_{1\leq i\leq m}^{.}\left | S_{i} \right |-\sum_{1\leq i< j\leq m}^{.}\left | S_{i}\cap S_{j} \right |+...$ , όπου το αριστερό μέλος μετράει όλους τους αριθμούς μικρότερους του 1000 που διαιρούνται με τετράγωνο πρώτου.Άρα οι square-free είναι
$x-\left | S_{1}\cup S_{2}\cup ...S_{m} \right |=x-\sum_{1\leq i\leq m}^{.}\left | S_{i} \right |+\sum_{1\leq i< j\leq m}^{.}\left | S_{i}\cap S_{j} \right |-...$ .
Παρατηρώ ότι το $S_{i}\cap S_{j}$ π.χ. αποτελείται από στοιχεία της μορφής $k\cdot p_{i}^2p_{j}^2$ ,οπότε αν ορίσω $r_{i,j}=p_{i}p_{j}$ ,θα ισχύει $\left | S_{i}\cap S_{j} \right |=\left \lfloor x/r_{i,j}^2 \right \rfloor$ .Έτσι,ψάχνω το $x-\left | S_{1}\cup S_{2}\cup ...S_{m} \right |=x-\sum_{1\leq i\leq m}^{.}\left | S_{i} \right |+\sum_{1\leq i< j\leq m}^{.}\left | S_{i}\cap S_{j} \right |-...=x-\sum_{1\leq r_{i}\leq \sqrt{x})}^{.}\left \lfloor \frac{x}{r_{i}^2} \right \rfloor+\sum_{1\leq r_{i,j}\leq \sqrt{x}}^{.}\left \lfloor \frac{x}{r_{i,j}^2} \right \rfloor-...$ .

Με άλλα λόγια,αν ξεχάσω για λίγο τα πρόσημα,για κάθε αριθμό-square-free $1\leq n\leq \sqrt{x}$ αυτό που κάνω είναι να υπολογίζω το $\left \lfloor \frac{x}{n^2} \right \rfloor$ .
Παρατηρώ ότι το πρόσημο είναι θετικό για κάθε τέτοιο αριθμό που έχει άρτιο αριθμό πρώτων στην παραγοντοποίησή του και αρνητικό για κάθε τέτοιον αριθμό που έχει περιττό αριθμό πρώτων στην παραγοντοποίησή του.Για να γενικεύσω για κάθε αριθμό,θέλω μια συνάρτηση που όταν δέχεται non-square-free αριθμούς να επιστρέφει 0.Η παραπάνω περιγραφή είναι της συνάρτησης mobius,και ο τύπος παίρνει την τελική του μορφή: $SqFr(x)=\sum_{k=1}^{\sqrt{x}}\mu (k)\left \lfloor \frac{x}{k^2} \right \rfloor$ .
Τώρα μένει να υπολογιστεί αυτό:
$SqFr(1000)=\sum_{k=1}^{\left \lfloor \sqrt{1000} \right \rfloor}\mu (k)\left \lfloor \frac{1000}{k^2} \right \rfloor=1000-250-111-40+27-20+10-8-5+5+4-3-2+2+2-1+1-1-1-1=608$

(Για τον υπολογισμό χρησιμοποίησα πίνακα με τις τιμές της mobius-φτιάχνεται εύκολα).Άρα ο ζητούμενος αριθμός είναι ο 1000-608=392

.

Ορέστης Λιγνός · #5

Για να μην ''φοβηθεί'' κανένας Junior από την λύση του Μίνωα, υπάρχει και πιο απλή λύση.

nikkru · #6

nikkru έγραψε: Παρ Αύγ 31, 2018 9:56 pm
Ορέστης Λιγνός έγραψε: Παρ Αύγ 31, 2018 8:40 pm Για πόσες θετικές ακέραιες τιμές του $x \leqslant 1000$ , έχει η εξίσωση $\sqrt{x}=\sqrt{a}+\sqrt{b}$ μία τουλάχιστον ακέραια λύση, με τους επίσης θετικούς ακεραίους;
Πόσοι θετικοί ακέραιοι που δεν υπερβαίνουν το διαιρούνται με τετράγωνο πρώτου;

.
Για να ισχύει για θετικούς ακέραιους $\sqrt{x}=\sqrt{a}+\sqrt{b}$ ή θα είναι και οι τρεις τετράγωνα ακεραίων ή μπορούν να γραφούν ως εξής:

$\sqrt{a}+\sqrt{b}=\sqrt{x}\Leftrightarrow \sqrt{k^2a_1}+\sqrt{m^2b_1}=\sqrt{x}\Leftrightarrow \sqrt{k^2x_1}+\sqrt{m^2x_1}=\sqrt{(k+m)^2 x_1}$ με k,m,x_1

ακέραιοι.

Επομένως ζητάμε το πλήθος των θετικών ακεραίων που δεν υπερβαίνουν το 1000

και διαιρούνται με τετράγωνο πρώτου, δηλαδή ζητάμε τα

πολλαπλάσια των: 2^2,3^2,5^2,7^2,11^2,13^2,17^2,19^2,23^2,29^2,31^2

από

έως και

.Το πλήθος τους είναι 392

.

Η ιδέα της λύσης είναι ίδια με του min

με χρήση γνώσεων Α Λυκείου (παρόμοια άσκηση η 5 της Β ομάδας στην παραγρ. 5.2 του σχολικού βιβλίου).

Να βρεθεί το πλήθος ακεραίων

Να βρεθεί το πλήθος ακεραίων

Re: Να βρεθεί το πλήθος ακεραίων

Re: Να βρεθεί το πλήθος ακεραίων

Re: Να βρεθεί το πλήθος ακεραίων

Re: Να βρεθεί το πλήθος ακεραίων

Re: Να βρεθεί το πλήθος ακεραίων

Μέλη σε σύνδεση