נוסחת לז'נדר – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
אין תקציר עריכה |
|||
שורה 19:
:<math>\left \lfloor \frac{n}{p^k} \right \rfloor = \left \lfloor \frac{a_r p^r + \ldots + a_0}{p^k} \right \rfloor = \left \lfloor a_r p^{r-k} + \ldots + a_k + a_{k-1}p^{-1}\ldots + a_0 p^{-k} \right \rfloor = a_r p^{r-k} + \ldots + a_k</math>
זאת מכיוון ש-<math> a_{k-1}p^{-1}\ldots + a_0 p^{-k}<1</math>. מכאן לפי נוסחת לז'נדר החזקה הגבוהה ביותר של <math>p</math> המחלקת את <math>n!</math> היא:
:<math>\sum_{k=1}^{\infty} \left \lfloor \frac{n}{p^k} \right \rfloor = \sum_{k=1}^{\infty} (a_r p^{r-k} + \ldots + a_k) = </math>
נבחין כי בטור האחרון לכל <math>1\le i \le r</math>, המקדם <math>a_i</math> מופיע פעם אחת בדיוק כמקדם של כל אחד מבין <math>1, p,\ldots, p^{i-1}</math>. לכן נוכל לסדר מחדש את הטור האחרון בצורה:
:<math>=\sum_{i=1}^r {a_i(1+p+\ldots+p^{i-1})} = \sum_{i=1}^r {a_i\left(\frac{p^i-1}{p-1}\right)} = \frac1{p-1}\left(\sum_{i=1}^r {a_ip^i} - \sum_{i=1}^r {a_i}\right) = \frac{(n-a_0)-(S_p(n)-a_0)}{p-1} = \frac{n-S_p(n)}{p-1}</math>
במעבר הראשון עשינו שימוש בנוסחה לסכום [[טור הנדסי]].
==דוגמה==
| |||