# Help with counting factors

Can someone help me prove that the product below has $(\large\frac{10^{100}}{6}-\frac{17}{3})$ factors of $7$?

$$\large\prod_{{k}={1}}^{{{10^{100}}}}({4k}+1)$$

-
Note that among the terms given, only those of the form $k=7r-2$ contain 7 as a factor. There will be roughly $10^{100}/7$ such terms ($\pm1$). Each of these terms looks like $7(4r-1)$. Removing all these 7, you have a similar product again $\prod (4r-1)$ over $r$ from 1 to $10^{100}/7$ (roughly). These will again have around $10^{100}/49$ terms containing 7 as a factor. Repeating this gives the required value as roughly $\sum {\frac {10^{100}}{7^i}}$, which is close to $10^{100}/6$. Handling all the $\pm 1$ above might give the exact expression you need ($\frac{10^{100}}{6} - \frac{17}{3}$). –  polkjh Jan 1 '13 at 6:29

Let $S_n = \displaystyle \prod_{k=1}^n(4k+1)$.

Number of multiples of $7$ in $S_n$ is $\left \lfloor \dfrac{n +2}7 \right\rfloor$

Number of multiples of $7^2$ in $S_n$ is $\left \lfloor \dfrac{n +37}{49} \right\rfloor$

Number of multiples of $7^3$ in $S_n$ is $\left \lfloor \dfrac{n +86}{343} \right\rfloor$

Number of multiples of $7^{2k}$ in $S_n$ is $$\left \lfloor \dfrac{n + 7^{2k} - (7^{2k}-1)/4}{7^{2k}} \right\rfloor = \left \lfloor \dfrac{4n + 3\cdot 7^{2k} + 1}{4 \cdot 7^{2k}} \right\rfloor$$

Number of multiples of $7^{2k+1}$ in $S_n$ is $$\left \lfloor \dfrac{n + 7^{2k+1} - (3 \cdot 7^{2k+1}-1)/4}{7^{2k+1}} \right\rfloor = \left \lfloor \dfrac{4n + 7^{2k+1}+1}{4 \cdot 7^{2k+1}} \right\rfloor$$

Hence, the highest power of $7$ dividing $S_n$ is $$\sum_{k=1}^{\infty} \left(\left \lfloor \dfrac{4n + 7^{2k-1}+1}{4 \cdot 7^{2k-1}} \right\rfloor + \left \lfloor \dfrac{4n + 3\cdot 7^{2k} + 1}{4 \cdot 7^{2k}} \right\rfloor \right)$$

I computed the sum above using WolframAlpha and it agrees with $\dfrac{10^{100}}6 - \dfrac{17}3$

-
How did you figure out how many multiples of 7 were in the first 1 –  Ethan Jan 1 '13 at 6:30
Does this reduce the problem to a double summation where the second sigma raises over from n=1 to 10^100 –  Ethan Jan 1 '13 at 6:32
@Ethan $21 = 4 \times 5 + 1$ is the first number of the form $4k+1$ which gets divided by $7$. Hence, whenever $k = 5+7 m$ it gets divided by $7$. Similarly for other powers of $7$. –  user17762 Jan 1 '13 at 6:33
@Ethan There is no summation over $n$. Just plug in $n=10^{100}$ to get the answer. –  user17762 Jan 1 '13 at 6:33
@Ethan I new that it should be similar to finding the highest power of a prime dividing $n!$. –  user17762 Jan 1 '13 at 6:44