Σειρά pop

Συντονιστής: Demetres

Άβαταρ μέλους
Tolaso J Kos
Δημοσιεύσεις: 4117
Εγγραφή: Κυρ Αύγ 05, 2012 10:09 pm
Τοποθεσία: Λάρισα, Βαρκελώνη
Επικοινωνία:

Σειρά pop

#1

Μη αναγνωσμένη δημοσίευση από Tolaso J Kos » Πέμ Σεπ 27, 2018 12:28 am

Ας μετράει το {\rm pop} τον αριθμό των bits του '1' στη δυική αναπαράσταση του n. Υπολογίσατε τη σειρά

\displaystyle{\mathcal{S} = \sum_{n=1}^{\infty} \frac{{\rm pop}(n)}{n(n+1)}}


Η φαντασία είναι σημαντικότερη από τη γνώση !
\displaystyle{{\color{blue}\mathbf{Life=\int_{birth}^{death}\frac{happiness}{time}\Delta time} }}

Λέξεις Κλειδιά:
dement
Διευθύνον Μέλος
Δημοσιεύσεις: 1405
Εγγραφή: Τρί Δεκ 23, 2008 10:11 am

Re: Σειρά pop

#2

Μη αναγνωσμένη δημοσίευση από dement » Πέμ Σεπ 27, 2018 11:49 am

Καλό. Μετακινούμαστε από δεξιά προς αριστερά στο δυαδικό.

Οι περιττοί αριθμοί έχουν το ψηφίο των μονάδων 1. Το αντίστοιχο μερικό άθροισμα είναι \displaystyle \frac{1}{1\cdot 2} + \frac{1}{3 \cdot 4} + ... = \ln 2.

Οι αριθμοί με υπόλοιπο 2 ή 3 ως προς 4 έχουν το ψηφίο των δυάδων 1. Το αντίστοιχο μερικό άθροισμα είναι \displaystyle \frac{1}{2 \cdot 3} + \frac{1}{3 \cdot 4} + ... = \frac{1}{2} - \frac{1}{4} + \frac{1}{6} - ...  = \frac{1}{2} \ln 2

Ομοίως για το ψηφίο των τετράδων \displaystyle \frac{1}{4} \ln 2 και ούτω καθεξής.

Τελικά το άθροισμα είναι \displaystyle \ln2 \sum_{k=0}^{\infty} \frac{1}{2^k} = 2 \ln 2


Δημήτρης Σκουτέρης

Τα μαθηματικά είναι η μοναδική επιστήμη που θα μπορούσε κανείς να εξακολουθήσει να ασκεί αν κάποτε ξυπνούσε και το σύμπαν δεν υπήρχε πλέον.
Άβαταρ μέλους
Tolaso J Kos
Δημοσιεύσεις: 4117
Εγγραφή: Κυρ Αύγ 05, 2012 10:09 pm
Τοποθεσία: Λάρισα, Βαρκελώνη
Επικοινωνία:

Re: Σειρά pop

#3

Μη αναγνωσμένη δημοσίευση από Tolaso J Kos » Πέμ Σεπ 27, 2018 2:43 pm

2η λύση

Η ακολουθία a_n που ορίζεται αναδρομικά ως

\displaystyle{a_{2n}=a_n \quad  , \quad a_{2n+1}=a_n+1  \quad , \quad n \geq 1}
και a_0=0 , a_1=a_2=1 μετράει τον αριθμό των 1 στη δυική αναπαράσταση του n. Τότε:

\displaystyle{\begin{aligned}  
\sum_{n=1}^{\infty} \frac{ {\rm pop}(n)  }{n(n+1)} = \sum_{n = 1}^{\infty} \frac{a_n}{n(n+1)} &= \sum_{n=1}^{\infty} \frac{a_{2n}}{2n(2n+1)} + \sum_{n = 0}^{\infty} \frac{a_{2n+1}}{(2n+1)(2n+2)} \\  
&= \sum_{n=1}^{\infty} \frac{a_{n}}{2n(2n+1)} + \sum_{n = 0}^{\infty} \frac{a_{n} + 1}{(2n+1)(2n+2)} \\  
&= \frac{1}2 + \frac{1}2 \sum_{n = 1}^{\infty} \frac{a_n}{n(2n+1)} + \frac{1}2 \sum_{n=1}^{\infty} \frac{a_n}{(n+1)(2n+1)} + \frac{1}2 \sum_{n=1}^{\infty} \frac{1}{(n+1)(2n+1)} \\  
&= \frac{1}2 + \frac{1}2 \sum_{n=1}^{\infty} a_n \left( \frac{1}{n(2n+1)} + \frac{1}{(n+1)(2n+1)} \right) + \frac{1}2 \sum_{n=1}^{\infty} \frac{1}{(n+1)(2n+1)} \\  
&= \frac{1}2+ \frac{1}2 \sum_{n=1}^{\infty} \frac{a_n}{n(n+1)} + \frac{1}2\sum_{n=1}^{\infty} \frac{1}{(n+1)(2n+1)} 
\end{aligned} }
και το αποτέλεσμα έπεται.


Η φαντασία είναι σημαντικότερη από τη γνώση !
\displaystyle{{\color{blue}\mathbf{Life=\int_{birth}^{death}\frac{happiness}{time}\Delta time} }}
Άβαταρ μέλους
Tolaso J Kos
Δημοσιεύσεις: 4117
Εγγραφή: Κυρ Αύγ 05, 2012 10:09 pm
Τοποθεσία: Λάρισα, Βαρκελώνη
Επικοινωνία:

Re: Σειρά pop

#4

Μη αναγνωσμένη δημοσίευση από Tolaso J Kos » Πέμ Σεπ 27, 2018 2:52 pm

3η λύση


Για k \in \mathbb{N}, θεωρούμε τη συνάρτηση
\displaystyle{\theta_k(n) = \left\{\begin{matrix} 
1 & , & \text{if k-th bit of n is set} \\ 
0 & , & \text{otherwise} 
\end{matrix}\right.}
Τότε,

\displaystyle{\sum_{n=1}^{\infty} \frac{{\rm pop}(n)}{n(n+1)} = \sum_{n=1}^{\infty}\sum_{k=0}^{\infty} \frac{\theta_k(n)}{n(n+1)} =  \sum_{k=0}^{\infty}\sum_{n=1}^{\infty} \frac{\theta_k(n)}{n(n+1)}}
Μπορούμε να κάνουμε την εναλλαγή στο διπλό άθροισμα αφού όλοι οι όροι είναι μη αρνητικοί. Παρατηρούμε επίσης ότι \theta_k(n) = 1 αν-ν (2\ell+ 1)2^k \leq n < (2\ell+2)2^k για κάποιον \ell \in \mathbb{N}. Συνεπώς,

\displaystyle{\begin{aligned} 
\sum_{k=0}^{\infty}\sum_{\ell=0}^{\infty} \sum_{n=(2\ell+1)2^k}^{(2\ell+2)2^k-1} \frac{1}{n(n+1)} 
&= \sum_{k=0}^{\infty}\sum_{\ell=0}^{\infty} \left(\frac{1}{(2\ell+1)2^k} - \frac{1}{(2\ell+2)2^k}\right)\\ 
&= \left(\sum_{k=0}^{\infty}2^{-k}\right)\sum_{\ell=0}^{\infty} \left(\frac{1}{2\ell+1} - \frac{1}{2\ell+2}\right) \\ 
&= \frac{1}{1-2^{-1}}\log 2 \\ 
&= 2\log 2 
\end{aligned}}
Σημείωση: Ουσιαστικά αυτή είναι η λύση του Δημήτρη. :( :(


Η φαντασία είναι σημαντικότερη από τη γνώση !
\displaystyle{{\color{blue}\mathbf{Life=\int_{birth}^{death}\frac{happiness}{time}\Delta time} }}
Απάντηση

Επιστροφή σε “Διαγωνισμοί για φοιτητές”

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

Μέλη σε αυτήν τη Δ. Συζήτηση: Δεν υπάρχουν εγγεγραμμένα μέλη και 1 επισκέπτης