Factoring added factorials

Question

How do I facilitate prime factorization without brute-forcing the 600+ digit number?

For example, how would I factor (82! + 83! + 84!) ?

Answer 1

If you write it out, you will see that $82!+83!+84!=82\cdot 81\cdot 80\dots \cdot1+83\cdot 82\cdot 81\dots\cdot 1+84\cdot 83\cdot 82\cdot \dots\cdot 1$. You can factor $82!$ out, which leaves us with $82!(1+83+83\times 84)$. You can simplify this further. $$82!(1+83+83\cdot 84)$$ $$=82!(84+83\cdot 84)$$ $$=82!(1\cdot 84+83\cdot 84)$$ $$=82!(84\cdot 84)$$ $$=82!(84)^2$$ $$\color{green}{\boxed{82!+83!+84!=82!(84)^2}}$$ To prime factorize $82!$, we cannot actually expand $82!$ and prime factorize that; it would take way too long. We need a better way to do this. $82!$ is equal to the product of every integer from $2$ to $82$. How many factors of $2$ are in $82$? Every multiple of $2$ in $82!$ counts for $1$ for the exponent (remember,the prime factorization should look like $2^a\cdot 3^b\cdot 5^c\dots$). Every multiple of $4$ counts for one more. Every multiple of $8$ counts for yet another one toward the exponent. There are $\left\lfloor\frac{82}{2}\right\rfloor=41$ multiples of $2$ between $2$ and $82$ (note: $\lfloor x \rfloor$ means "the greatest integer of $x$ that is $\leq x$). There are $\left\lfloor\frac{81}{4}\right\rfloor=20$ multiples of $4$, $\left\lfloor\frac{81}{8}\right\rfloor=10$ multiples of $8$, $\left\lfloor\frac{81}{16}\right\rfloor=5$ multiples of $16$, $\left\lfloor\frac{81}{32}\right\rfloor=2$ multiples of $32$, and $\left\lfloor\frac{81}{64}\right\rfloor=1$ multiple of $64$. Add all of these up to get $41+20+10+5+2+1=79$ multiples of $2$ in $82!$. Therefore $2^{79}$ is a factor of $82!$. There is a shortcut for this. Repeated division of $2$ (discarding any remainder) can give us the number of factors of $2$ in $82!$ like so:

$2|\underline{82}$
$2|\underline{41}$
$2|\underline{20}$
$2|\underline{10}$
$2|\underline{5}$
$2|\underline{2}$
$\ \ \ 1$

$41+20+10+5+2+1=79$, which is the number of factors of $2$ that are in $82!$.

We need to do this for all the primes below $\left\lfloor\frac{82}{2}\right\rfloor=41$.

For the factors of $3$:

$3|\underline{82}$
$3|\underline{27}$
$3|\underline{9}$
$3|\underline{3}$
$ \ \ \ 1$

Number of factors of $3$: $27+9+3=39$.

$5|\underline{82}$
$5|\underline{16}$
$\ \ \ 3$

Number of factors of $5$: $16+3=19$

$7|\underline{82}$
$7|\underline{11}$
$ \ \ \ 1$

Number of factors of $7$: $11+1=12$

$11|\underline{82}$
$\ \ \ \ \ \ 8$

Number of factors of $11$: $8$

$13|\underline{82}$
$\ \ \ \ \ \ 6$

Number of factors of $13$: $6$

$17|\underline{82}$
$\ \ \ \ \ \ 4$

Number of factors of $17$: $4$

$19|\underline{82}$
$\ \ \ \ \ \ 4$

Number of factors of $19$: $4$

$23|\underline{82}$
$\ \ \ \ \ \ 3$

Number of factors of $23$: $3$

$29|\underline{82}$
$\ \ \ \ \ \ 2$

Number of factors of $29$: $2$

$31|\underline{82}$
$\ \ \ \ \ \ 2$

Number of factors of $31$: $2$

$37|\underline{82}$
$\ \ \ \ \ \ 2$

Number of factors of $37$: $2$

$41|\underline{82}$
$\ \ \ \ \ \ 2$

Number of factors of $41$: $2$

The rest of the prime numbers after $41$ will only occur once in the prime factorization of $82!$. Therefore the prime factorization of $82!$ is: $$82!=2^{79}\cdot 3^{39}\cdot 5^{19}\cdot 7^{12}\cdot 11^8\cdot 13^6\cdot 17^4\cdot 19^4\cdot 23^3\cdot 29^2\cdot 31^2\cdot 37^2\cdot 41^2\cdot 43\cdot 47\cdot 53\cdot 59\cdot 61\cdot 67\cdot 71\cdot 73\cdot 79$$

Hope I helped!

Answer 2

$$82! + 83! + 84!=82!(1+83+83\cdot84)$$

Now $\displaystyle1+n+n(n+1)=(n+1)^2$

Clearly, here $\displaystyle n=83$

Answer 3

$82!+83!+84!=82!(1+83+83\cdot84)$