A different way to find the highest power

For a prime p>np>n for nNn\in\mathbb{N}, you've probably seen this formula somewhere for the highest power of pp dividing n!n!:

i1npi\displaystyle \sum _{ i\ge 1 }^{ \quad }{ \left\lfloor \frac { n }{ { p }^{ i } } \right\rfloor }

In fact, there's a much more surprising formula (let's face it, this one isn't that hard to derive): suppose n=(b0b1b2...br)pn={ ({ b }_{ 0 }{ b }_{ 1 }{ b }_{ 2 }...{ b }_{ r }) }_{ p }, or

n=b0pr+b1pr1...+brn={ b }_{ 0 }{ p }^{ r }+{ b }_{ 1 }{ p }^{ r-1 }...+{ b }_{ r }

and let δ(n)\delta (n) be the digit sum of nn base pp. Then the highest power of pp dividing n!n! is

nδ(n)p1\displaystyle \frac { n-\delta (n) }{ p-1 }

Wow. That's a heck of a lot shorter, isn't it? But why does this even work? Let's prove it below...

nδ(n)p1=n(b0+b1+...br)p1=k=0rbk(prk1)p1\frac { n-\delta (n) }{ p-1 } = \frac { n-({ b }_{ 0 }+{ b }_{ 1 }+...{ b }_{ r }) }{ p-1 } =\frac { \displaystyle \sum _{ k=0 }^{ r }{ { b }_{ k }({ p }^{ r-k }-1) } }{ p-1 }

Then factor prk1{p}^{r-k}-1 (by difference of nth powers) and cancel the p1p-1 in the denominator. This results in

k=0rbk(1+p+p2...prk1)=br1+(br2p+br2)\displaystyle \sum _{ k=0 }^{ r }{ { b }_{ k }\left( 1+p+{ p }^{ 2 }...{ p }^{ r-k-1 } \right) } = b_{r-1}+(b_{r-2}p+b_{r-2}) \dots

Now write this sum out - term by term - in columns (not a typo, I mean columns - there's a trick here):

k=0rbk(j=0rk1pj)=(br1+br2p++b0pr1)\displaystyle \sum _{ k=0 }^{ r }{ { b }_{ k }\left( \sum _{ j=0 }^{ r-k-1 }{ { p }^{ j } } \right) } =({ b }_{ r-1 }+{ b }_{ r-2 }p+\dots+ { b }_{ 0 }{ p }^{ r-1 }) +(br2++b0pr2)\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad+(b_{r-2}+ \dots + b_0 p^{r-2}) \quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\vdots +b0\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad +b_0

Okay, while each term was written by column before, let's look at the rows now. In fact, each row is equal to a term in this familiar expression:

k=1rnpk\displaystyle \sum _{ k=1}^{ r }{ \left\lfloor \frac { n }{ { p }^{ k } } \right\rfloor }

because each time you divide by pp again one term in the base pp expansion vanishes (that associated with p0p^0) and the others go down an exponent of pp. So, we have

k=1rnpk=nδ(n)p1\displaystyle \sum _{ k=1}^{ r }{ \left\lfloor \frac { n }{ { p }^{ k } } \right\rfloor } = \displaystyle \frac { n-\delta (n) }{ p-1 }

Note by Dylan Pentland
4 years, 1 month ago

No vote yet
1 vote

</code>...<code></code> ... <code>.">   Easy Math Editor

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

  • bulleted
  • list

1. numbered
2. list

  1. numbered
  2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1

paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
    # 4 spaces, and now they show
    # up as a code block.

    print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in </span>...<span></span> ... <span> or </span>...<span></span> ... <span> to ensure proper formatting.
2 \times 3 2×3 2 \times 3
2^{34} 234 2^{34}
a_{i-1} ai1 a_{i-1}
\frac{2}{3} 23 \frac{2}{3}
\sqrt{2} 2 \sqrt{2}
\sum_{i=1}^3 i=13 \sum_{i=1}^3
\sin \theta sinθ \sin \theta
\boxed{123} 123 \boxed{123}

Comments

Sort by:

Top Newest

Wow! Nice, let me see whether I can apply to this question.

Pi Han Goh - 4 years ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...