Why? (Big numbers)

060119 Thu 2330 Prime factors of factorials

I. Originally, I sent this challenge: How many 2s are among the prime factors of 10 factorial; i.e., how many times can 10 factorial be evenly divided by 2?
10! = 3628800
/2 = 1814400 (1)
/2 = 907200 (2)
/2 = 453600 (3)
/2 = 226800 (4)
/2 = 113400 (5)
/2 = 56700 (6)
/2 = 28350 (7)
/2 = 14175 (8)

Now compare this shortcut (when dividing, ignore fractional part):
10/ 2 = 5
10/ 4 = 2+
10/ 8 = 1+
10/16 = 0+
10/32 = 0+ etc.
----
total 8

This works for counting any prime factor p of any factorial N! Why?

II. Thank you for your replies. The reason I'm fond of this trick is a simple proof embodying one of the archetypes found throughout the deductive network of mathematics: in counting the dots of a matrix of dots and spaces, or in summing a matrix of numbers, it does not matter whether you first take columns and finally the subtotals row, or first take rows and finally the subtotals column; the result is of course the same. Do you see the proof in this matrix (p=2, N=10)?

0 1 0 1 0 1 0 1 0 1 5
0 0 0 1 0 0 0 1 0 0 2
0 0 0 0 0 0 0 1 0 0 1
0 0 0 0 0 0 0 0 0 0 0
0 1 0 2 0 1 0 3 0 1 8

III. Further investigations: Let's try prime factors p of a really big factorial.

1000! ˜ 4.02*10^2567 is big--much, much bigger, for example, than any number needed to count any collection of physical entities.

Writing "N#p" for the number of times p occurs as a prime factor of N, plot p:1000!#p -

p 1000!#p d
--- -------------- ---
2 994 ? 1000 6 (Here we use "?" for "approximately equal to")
3 498 ? 1000/2 2
5 249 ? 1000/4 1
7 164 ? 1000/6 2
11 98 ? 1000/10 2
13 81 ? 1000/12 2
17 61 ? 1000/16 1
19 54 ? 1000/18 1
...
97 10 ? 1000/96 0
101 9 ? 1000/100 1
...
991 1 ? 1000/990 0
997 1 ? 1000/996 0

Where the deficit d = 1000/(p-1) - 1000!#p (using integer division).

IV. Let's plot N!#p:d for some representative N,p -

N!#p d
-------------------------- ---
(7^1!= 7!)# 2 = 4 3
(7^2!= 49!)# 2 = 46 3
(7^3!= 343!)# 2 = 337 6
(7^4!= 2401!)# 2 = 2396 5
(7^5!= 16807!)# 2 = 16800 7
(7^6!=117649!)# 2 = 117640 9
(7^7!=823543!)# 2 = 823532 11

N!#p d
-------------------- ---
1!# 2 = 0 0
10!# 2 = 8 2
100!# 2 = 97 3
1000!# 2 = 994 6
10000!# 2 = 9995 5
100000!# 2 = 99994 6
1000000!# 2 = 999993 7
1!# 3 = 0 0
10!# 3 = 4 1
100!# 3 = 48 2
1000!# 3 = 498 2
10000!# 3 = 4996 4
100000!# 3 = 49995 5
1000000!# 3 = 499993 7
1!# 5 = 0 0
10!# 5 = 2 0
100!# 5 = 24 1
1000!# 5 = 249 1
10000!# 5 = 2499 1
100000!# 5 = 24999 1
1000000!# 5 = 249998 2
1!# 7 = 0 0
10!# 7 = 1 0
100!# 7 = 16 0
1000!# 7 = 164 2
10000!# 7 = 1665 1
100000!# 7 = 16662 4
1000000!# 7 = 166664 2
1!#11 = 0 0
10!#11 = 0 1
100!#11 = 9 1
1000!#11 = 98 2
10000!#11 = 998 2
100000!#11 = 9997 3
1000000!#11 = 99998 2
1!#13 = 0 0
10!#13 = 0 0
100!#13 = 7 1
1000!#13 = 81 2
10000!#13 = 832 1
100000!#13 = 8331 2
1000000!#13 = 83332 1
1!#17 = 0 0
10!#17 = 0 0
100!#17 = 5 1
1000!#17 = 61 1
10000!#17 = 624 1
100000!#17 = 6249 1
1000000!#17 = 62497 3
1!#19 = 0 0
10!#19 = 0 0
100!#19 = 5 0
1000!#19 = 54 1
10000!#19 = 554 1
100000!#19 = 5554 1
1000000!#19 = 55553 2

Why does N!#p approximate N/(p-1)?

Sorry about the formatting.