Άπειροι φυσικοί...

Αρχιμήδης 6 · #1

Να αποδείξετε ότι υπάρχουν άπειροι φυσικοί αριθμοί που δεν είναι της μορφής 2^a+2^b+p

όπου

φυσικοί αριθμοί διαφορετικοί μεταξύ τους και

-πρώτος.
Καλή τύχη!

(Το λάθος διορθώθηκε. Συγγνώμη)

AlexandrosG · #2

Καλησπέρσ.

Σίγουρα θες να είναι οι αριθμοί γενικά φυσικοί?

Τότε οι αριθμοί $\displaystyle{2^a+2+3}$ είναι της ζητούμενης μορφής για όλα τα $\displaystyle{a>1}$ .

Αρχιμήδης 6 · #3

Το λάθος της εκφώνησης διορθώθηκε! Ευχαριστώ για την παρατήρησή σου Αλέξανδρε.

Ilias_Zad · #4

Στους φυσικούς θεωρείται ότι περιέχεται το μηδέν;

Αρχιμήδης 6 · #5

Φυσικά.

#6

Έχω βρει μια λύση αλλά αρκετά μη στοιχειώδη.

Θα δείξουμε ότι υπάρχουν άπειρα πολλαπλάσια του 510 τα οποία δεν είναι αυτής της μορφής.

Για να είναι το 2^a + 2^b + p

πολλαπλάσιο του 2, πρέπει είτε p = 2

, είτε

. (Υποθέτουμε χωρίς βλάβη της γενικότητας ότι a = b

.)

Παίρνουμε τώρα ένα

αρκετά μεγάλο και κοιτάμε όλα τα πολλαπλάσια του 510 τα οποία είναι μικρότερα ή ίσα του

. Υπάρχουν ακριβώς $\lfloor n/510 \rfloor$ πολλαπλάσια. Από αυτά το πολύ $(\log_2(n))^2$ μπορούν να γραφτούν στην μορφή 2^a + 2^b + 2

αφού πρέπει $2^a \leqslant n$ και $2^b \leqslant n$ .

Ας δούμε τώρα πόσα μπορούν να γραφτούν στην μορφή 1 + 2^b + p

, όπου

πρώτος. Το 2^b

είναι ισότιμο με 2,4,8,16,32,64,128

ή $256 \bmod 510$ . Αν $2^b \equiv 2,8,32,128 \bmod 510$ , τότε για να είναι το 1 + 2^b + p

πολλαπλάσιο του 510 θα πρέπει το

να είναι πολλαλάσιο του 3 και άρα να ισούται με 3. Ομοίως αν $2^b \equiv 4,64 \bmod 510$ τότε p=5

και αν $2^b \equiv 16 \bmod 510$ τότε p = 17

. Για όλες τις υπόλοιπες λύσεις πρέπει να έχουμε $2^b \equiv 256 \bmod 510$ (το οποίο δίνει $b \equiv 0 \bmod 8$ ) και $p \equiv 253 \bmod 510$ .

Επομένως για το

υπάρχουν το πολύ $\log_2(n)/8$ επιλογές ενώ για το

από το θεώρημα των πρώτων αριθμών για τις αριθμητικές προόδους (*) υπάρχουν το πολύ $\displaystyle{ \frac{1.1n}{\phi(510)\log{n}} = \frac{1.1n}{128\log{n}}}$ επιλογές αρκεί το

να είναι αρκετά μεγάλο. (Εδώ ο λογάριθμος είναι φυσικός.)

Άρα υπάρχουν το πολύ $\displaystyle{ (\log_2(n))^2 + 3\log_2(n) + \frac{1.1n}{128\log{n}} \frac{\log_2(n)}{8} < \frac{0.4n}{510}}$ διαφορετικά πολλαπλάσια του 510 τα οποία είναι μικρότερα του

και μπορούν να παρασταθούν στην μορφή 2^a + 2^b + p

. Άρα τα υπόλοιπα 0.6n/510

πολλαπλάσια δεν μπορούν να γραφτούν σε αυτήν την μορφή.

------------------
(*) Για το θεώρημα των πρώτων αριθμών σε αριθμητικές προόδους, δείτε την παράγραφο «The prime number theorem for arithmetic progressions» εδώ.

Αρχιμήδης 6 · #7

Δημήτρη αν δεν κάνω λάθος το ζητούμενο το απέδειξες από την αρχή που λες <<Παίρνουμε τώρα ένα

αρκετά μεγάλο...........αφού πρέπει $2^a \leqslant n$ και $2^b \leqslant n$ >>.
Kάνω λάθος?

#8

Αρχιμήδης 6 έγραψε:Δημήτρη αν δεν κάνω λάθος το ζητούμενο το απέδειξες από την αρχή που λες <<Παίρνουμε τώρα ένα αρκετά μεγάλο...........αφού πρέπει $2^a \leqslant n$ και $2^b \leqslant n$ >>.
Kάνω λάθος?

Όχι, δεν είναι εκεί η χρήση του "αρκετά μεγάλου

". Αλλά ξεκινά από μεγάλο

και κάνει εκτιμήσεις του πλήθους των αριθμών κάτω του

που γράφονται στη ζητούμενη μορφή. Σε ένα βήμα γίνεται χρήση του Θεωρήματος Πρώτων Αριθμών (εδώ χρησιμοπιοείται μεγάλο

) για να καταλήξει ότι όσοι γράφονται είναι το πολύ 0.4n/510

.

M.

Αρχιμήδης 6 · #9

Στο τέλος που αθροίζει τις λογαριθμικές συναρτήσεις αναφέρεται στην περίπτωση της μορφής 1+2^b+p

η στην περίπτωση 2^a+2^b+p

?

Αρχιμήδης 6 · #10

Κατάλαβα. Απλά στην αρχή υπολογίζει το πλήθος των αριθμών με την ιδιότητα αυτή για την περίπτωση 2^a+2^b+1

χωρίς το ενδεχόμενο a=1

και έτσι του επιτρέπει να λειτουργήσει η συνθήκη a=b

χωρίς κανένα πρόβλημα. Στην συνέχεια οι υπολογισμοί απασχολούν την περίπτωση όπου a=1

και μετά αθροίζει τις λογαριθμικές συναρτήσεις. (Θα ήθελα και επιβεβαίωση από κάποιον).
Πάντως η λύση σου Δημήτρη είναι πολλή καλή, διδακτική και μη στοιχειώδης, όπως μ' αρέσει!

Αρχιμήδης 6 · #11

ΕΡΩΤΗΣΗ
Μπορούμε να βρούμε κάποια ακολουθία αυτών των αριθμών με την ιδιότητα που έχει αναφερθεί ? (Φυσικά και μια δεύτερη απόδειξη στην αρχική μας άσκηση θα ήταν δεκτή. )

#12

Δημήτρη

Το $(\log_2(n))^2$ είναι άνω φράγμα για το πλήθος των πολλαπλασίων του 520 τα οποία είναι μικρότερα ή ίσα με

και γράφονται στην μορφή 2^a + 2^b + 2

.

To $3(\log_2(n))$ είναι άνω φράγμα για το πλήθος των πολλαπλασίων του 520 τα οποία είναι μικρότερα ή ίσα με

και γράφονται στην μορφή 1 + 2^b + p

με $p \in \{3,5,17\}$ .

Ο τελευταίος όρος είναι άνω φράγμα για το πλήθος των πολλαπλασίων του 520 τα οποία είναι μικρότερα ή ίσα με

και γράφονται στην μορφή 1 + 2^b + p

με $p \notin \{3,5,17\}$ .

-----------

Για την τελευταία ερώτηση η απόδειξή μου δείχνει μόνο την ύπαρξη της ακολουθίας και δεν την κατασκευάζει. Δεν αποκλείεται βέβαια να υπάρχει άλλη απόδειξη που να δίνει μια τέτοια ακολουθία.

#13

Αρχιμήδης 6 έγραψε:Να αποδείξετε ότι υπάρχουν άπειροι φυσικοί αριθμοί που δεν είναι της μορφής
όπου φυσικοί αριθμοί διαφορετικοί μεταξύ τους και -πρώτος.

Μετά από πολύ κόπο, να μια στοιχειώδης απόδειξη.

Έχει το πλεονέκτημα ότι δίνει τύπο για άπειρους περιττούς αριθμούς που δεν γράφονται στην παραπάνω μορφή, αλλά δεν έχει το
πλεονέκτημα (όπως η καταπληκτική λύση του Δημήτρη) να δείξει ότι οι "περισσότεροι" αριθμοί δεν γράφονται.

Θα δείξουμε ότι κανένας αριθμός της μορφής $\displaystyle 2^{2^n}-1, \, n\ge 3$ δεν γράφεται ως $2^a+2^b+p, \, a \ne b, \, p$ πρώτος.

Έστω $\displaystyle 2^{2^n}-1 = 2^a+2^b+d, \, a > b$ όπου

κάποιος αριθμός. Θα δείξουμε ότι ο

είναι σύνθετος.

Γράφουμε a-b= 2^mq

όπου

περιττός. Για αυτό το ίδιο

έχουμε $2^{2^m}+1 | 2^{2^mq}+1=2^{a-b}+1$ (*).

O αριθμός $F_m=2^{2^m}+1$ είναι το κλειδί της απόδειξης. Δεν είναι τυχαίος αλλά είναι αριθμός Fermat, για τον οποίο είναι

γνωστό ότι $\displaystyle \prod _{k=1}^{n-1}F_k = F_n -2 = 2^{2^n}-1$ (το γνωστό αυτό αποτέλεσμα αποδεικνύεται εύκολα με επαγωγή).

Το τελευταίο μαζί με την (*) δείχνει ότι $F_m | \left(2^{2^n} -1\right) - 2^b\left ( 2^{a-b}+1\right)=d$ .

(**) Η απόδειξη ότι ο

είναι σύνθετος θα τελειώσει αν δείξουμε ότι F_m<d

. Αυτό ισχύει καθώς από την $2^{2^n} -1= 2^a+2^b+d, \, b<a$ έχουμε b<a < 2^n

οπότε $2^a+2^b\le 2^{2^n-1} + 2^{2^n-2}=3\cdot 2^{2^n-2}$ . Άρα, για $n\ge 3$ έχουμε

$\displaystyle d = 2^{2^n} -1- 2^a-2^b\ge 2^{2^n} -1-3\cdot 2^{2^n-2}=$

$\displaystyle =2^{2^n-2}-1> 2^{2^{n-1}}+1 \ge 2^{2^{m}}+1= F_m$ , όπως θέλαμε.

Φιλικά,

Μιχάλης

(**) Edit: Συμπλήρωσα ένα κενό που είχα σε αυτό το βήμα.

Αρχιμήδης 6 · #14

Μπράβο!

Η δική μου ΄σκέψη είναι ίδια ΄με του κυρίου Λάμπρου όπότε δεν χρειάζεται.

greek_sorcerer · #15

Demetres έγραψε:Έχω βρει μια λύση αλλά αρκετά μη στοιχειώδη.

Θα δείξουμε ότι υπάρχουν άπειρα πολλαπλάσια του 510 τα οποία δεν είναι αυτής της μορφής.

πολύ έξυπνη λύση, αλλά με ποια λογική διαλέξατε το 510?

#16

greek_sorcerer έγραψε:
Demetres έγραψε:Έχω βρει μια λύση αλλά αρκετά μη στοιχειώδη.

Θα δείξουμε ότι υπάρχουν άπειρα πολλαπλάσια του 510 τα οποία δεν είναι αυτής της μορφής.
πολύ έξυπνη λύση, αλλά με ποια λογική διαλέξατε το 510?

Αρχικά ήθελα να χρησιμοποιήσω μόνο το θεώρημα των πρώτων αριθμών. Όμως το φράγμα που παίρνουμε για τους αριθμούς που μπορούν να παρασταθούν στην μορφή 1 + 2^b + p

είναι (περίπου) $\frac{n}{\log{2}}$ το οποίο είναι μεγαλύτερο του n/2

.

Η επόμενη παρατήρηση είναι αντί modulo 2 να δουλέψουμε modulo 6. Το 2^b

είναι 2 ή $4 \bmod$ 6 μισές μισές φορές και το

είναι 1 ή $5 \bmod$ 6 πάλι μισές μισές φορές (περίπου). Επομένως μας συμφέρει να επικεντρωθούμε είτε στο $1 \bmod 6$ είτε στο $5 \bmod 6$ τα οποία εμφανίζονται από $\frac{n}{4\log{2}}$ φορές το οποίο όμως είναι πάλι μεγαλύτερο από το n/6

. Κερδίσαμε κάτι όμως και ο λόγος που κερδίσαμε είναι πως αποφύγαμε τα $3\bmod 6$ τα οποία εμφανίζονται διπλάσιες φορές από τα $1 \bmod 6$ .

Άρα αυτό που επιζητούμε είναι ένα άρτιο αριθμό

και ένα άρτιο αριθμό

ώστε:
Αν οι δυνάμεις του 2 modulo

είναι $x_1,\ldots,x_k$ και οι αριθμοί που είναι πρώτοι ως προς τον

και μικρότεροί του είναι οι $y_1,\ldots,y_{\phi(m)}$ τότε μπορούμε να γράψουμε τον

με λίγους τρόπους σαν $r \equiv 1 + x_i + y_j \bmod m$ όπου το λίγους σημαίνει το πολύ $\log_2 m/k\phi(m)$ .

Από εδώ και πέρα μπορούμε να ζητήσουμε και από ένα υπολογιστή να ψάξει να βρει παράδειγμα. (Κάτι που δεν έκανα) Μερικές όμως χρήσιμες παρατηρήσεις: Αν όλοι οι άρτιοι αριθμοί εμφανίζονταν στις δυνάμεις του 2 modulo

θα είχαμε πρόβλημα. Διότι μετά κάθε άρτιος αριθμός θα εμφανιζόταν ακριβώς με τον ίδιο αριθμό φορών σαν 1 + x_i + y_j

και δεν θα είχαμε κανένα κέρδος. Το ίδιο και αν όλοι (ή σχεδόν όλοι) οι περιττοί εμφανίζονταν σαν πρώτοι σχετικά με τον

.

Για να περιορίσουμε τις δυνάμεις του 2 συμφέρει να πάρουμε σαν

κάποια από τα 6,14,30,62

κ.τ.λ. Το 6 έχουμε ήδη δει πως δεν δουλεύει. Το 14 δεν είναι καλό επειδή όλοι οι μικρότεροι του περιττοί (εκτός από το 7) είναι πρώτοι σε σχέση με το 14. Το 30 ελέγχουμε και δεν δουλεύει. Το $62 = 2 \times 31$ δεν είναι καλό. Το $126 = 2 \times 7 \times 9$ ελέγχουμε και δεν μας κάνει. Το $254 = 2 \times 127$ δεν είναι καλό. Το επόμενο είναι το 510

το οποίο δουλεύει. Φυσικά, πρέπει να και πιο υπόλοιπο μας κάνει. Τα πολλαπλάσια του 3 και του 5 συμφέρουν διότι έτσι αποκλείουμε αρκετούς αριθμούς όπως και στην απόδειξη. Μετά δεν έχει και τόση σημασία πιο πολλαπλάσιο του 15 θα πάρουμε. Μπορούμε να διαλέξουμε κάποιο που θα αποκλείσει ακόμη ένα ζεύγος και το πιο εύκολο να διαλέξουμε είναι το 0.

#17

Αρχιμήδης 6 έγραψε: <...> Η δική μου σκέψη είναι ίδια <...>

Θα ήθελα να ρωτήσω ποιά είναι η πηγή της άσκησης.

Ενδεχομένως να έχω και άλλη λύση, πιο κοντά στου Δημήτρη. Θα το ελέγξω όταν βρω χρόνο (έχω τρεχάματα αυτό τον καιρό).

Ας προσθέσω ότι συμπλήρωσα ένα μικρό κενό στην παραπάνω λύση μου. Είναι κάπου προς το τέλος,

Φιλικά,

Μιχάλης

Αρχιμήδης 6 · #18

Στην βιβλιογραφία είναι γνωστό ως θεώρημα του A. Schinzel .

#19

Αρχιμήδης 6 έγραψε:Στην βιβλιογραφία είναι γνωστό ως θεώρημα του A. Schinzel .

Συγνώμη που επανέρχομαι, αλλα δεν μπορώ να εντοπίσω το συγκεκριμένο θεώρημα του Schinzei. Καμιά βοήθεια;

Ο Andrej Schinzel (1937- ) είναι ή ήταν (δεν ξέρω αν ζει) σπουδαίος Πολωνός Αριθμοθεωρητικός. Το συλλογικό του έργο εκδόθηκε από την Αμερικανική Μαθηματική Εταιρεία, και αποτελείται από πάνω από 200 ερευνητικά άρθρα, 1417 σελίδων!

Στο ιντερνέτ βρήκα τις ακόλουθες πηγές:

http://www.ams.org/bookstore-getitem/item=EMSHEM-1

http://www.impan.pl/User/schinzel/

Θα χαρώ να δω την αρχική απόδειξη του ίδιου του Schinzel. Ίσως κάποιος με καλύτερη πρόσβαση στο ιντερνέτ μπορεί να βοηθήσει. Ο ίδιος δεν μπορώ να κατεβάσω αρχεία doc/pdf και λοιπά, λόγω αργής σύνδεσης εδώ που ζω (δεν έχω ούτε σταθερό τηλέφωνο! Στο ιντερνετ μπαίνω μέσω κινητού).

Φιλικά,

Μιχάλης

tbolis · #20

Επειδή έχω κοινή εργασία με τον Andrzej Schinzel σας πληροφορώ ότι τώρα είναι συνταξιούχος. Έχει έρθει στην Ελλάδα δυό φορές (Πανελλήνιο Συνέδριο Άλγεβρας και Θεωρίας Αριθμών, Πάτρα 2002, και Παν/μιο Ιωαννίνων, 2004) και έχει συγγράψει ένα εξαιρετικό βιβλίο με τίτλο Polynomials with special regard to reducibility, Campbridge University Press, 2000, 568 σελίδες. Ζούσε με τη μητέρα του, μετά μόνος, δεν παντρεύτηκε ποτέ, έχει ένα χαλασμένο μάτι και είναι υπερβολικά θρήσκος (καθολικός). Όταν με είχε επισκεφθεί, μέ ρωτούσε πού είναι η πλησιέστερη καθολική εκκλησία. Επειδή στο χωριό μου φυσικά δεν υπάρχει τέτοιο Ίδρυμα, πήγε στην εκκλησία του χωριού μου για να λειτουργηθεί την Κυριακή που βρέθηκε εκεί. Στην Αθήνα που βρεθήκαμε την επόμενη Κυριακή πήγε στον Άγιο Διονύσιο, αλλά πάλι στα Ελληνικά ήταν η λειτουργία! Το επώνυμό του είναι Αυστριακό. Ο παππούς του είχε μεταναστεύσει στην Πολωνία. Επειδή στα Πολωνικά κάθε ξένο επώνυμο γράφεται και προφέρεται όπως στη γλώσσα προέλευσης, το επώνυμό του προφέρεται όπως στα Γερμανικά, δηλ. Σίντσελ με παχύ το Σ. Αυτά επειδή το McTutor δεν έχει δημοσιεύσει ακόμα τη βιογραφία του.

Θ. Μπόλης

Άπειροι φυσικοί...

Άπειροι φυσικοί...

Re: Άπειροι φυσικοί...

Re: Άπειροι φυσικοί...

Re: Άπειροι φυσικοί...

Re: Άπειροι φυσικοί...

Re: Άπειροι φυσικοί...

Re: Άπειροι φυσικοί...

Re: Άπειροι φυσικοί...

Re: Άπειροι φυσικοί...

Re: Άπειροι φυσικοί...

Re: Άπειροι φυσικοί...

Re: Άπειροι φυσικοί...

Re: Άπειροι φυσικοί...

Re: Άπειροι φυσικοί...

Re: Άπειροι φυσικοί...

Re: Άπειροι φυσικοί...

Re: Άπειροι φυσικοί...

Re: Άπειροι φυσικοί...

Re: Άπειροι φυσικοί...

Re: Άπειροι φυσικοί...

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