News

Loading...

Friday, August 11, 2006

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.

2 comments:

  1. This is by far the most numbers ever put in a Crash Landing post!

    ReplyDelete
  2. Anonymous8:30 PM

    Welcome to our company which sells all kinds of maple mesos, very cheap mesos, and the more cheap mesos. If you have to buy some maplestory mesos, please come to our company, we can give you the best maple story mesos and best service.

    ReplyDelete