factorial puzzle (requires maths)

graeme · 2003-08-14, 09:25

For math's puzzle affectionados only, since I guess that your favourite large number program could give you the answer quite quickly. See if can do it without resorting to such new-fangled techniques.

How many trailing zeros are there in 534! (that's factorial (534) )

Graeme

Uncwilly · 2003-08-14, 13:26

At least 106.

Rough calculation. 534/10=53 10's plus 53 5x2 pairs. 8)

Orgasmic Troll · 2003-08-14, 14:26

131

jflin · 2003-08-14, 14:31

Find all factors that will multiply by 10, 0-9

e.g. 2/5 = 10
4/5 = 20
6/5 = 30
8/5 = 40

So out of every 10 numbers, there are 5 that will give a trailing 0.

534 / 10 is about 53 complete series of 10 numbers.

Since each series will hit every other series, and 2 out of 10 give 0's (0 and 5), each set of 10 numbers should give about 10 (Any * 0 is 0) + 4 (non-0 even * 5 = 0) 0's per series.

so a rough guess would be 14^53 0's.

Uncwilly · 2003-08-14, 15:01

Quote:

Find all factors that will multiply by 10, 0-9

e.g. 2/5 = 10
4/5 = 20
6/5 = 30
8/5 = 40

So out of every 10 numbers, there are 5 that will give a trailing 0.

But, once you have used the 5 by multipling it by a 2, you effictively remove the five from availablity.

zacksg1 · 2003-08-14, 15:06

to solve this you need to count total pairs of 5's and 2's. since there are quite a few mroe 2's than 5's you need to count the total number of 5's in the factorization of this number.

534/5=106
534/(5^2)=21
534/(5^3)=4
534/(5^4)=0

adding... we get 106+21+4=131 so there are 131 trailing zeroes.

graeme · 2003-08-18, 09:00

131 is the right answer

Graeme

Maybeso · 2003-08-19, 20:40

I wrote a program in college that asked for a number n < 2^32, and spat out the prime factorization of n! almost as fast as they'd entered the number. (This was in 1986.)

First they said it was faked, I couldn't possibly calculate or store n!, until they checked random entries.

Then they said I had a table of every kth one up to the max they could verify and an exact interpolation method.

Then for a while they were really impressed,
;) until I showed them the code.

The trick was I never had to deal with n!, just n. I used zacksg1's idea recursively for all primes p < n.[list]534/5 = 106, total = 106
106/5 = 21, total += 21
21/5 = 4, total += 4 ... = 131[/list:u]This requires only log_p(n) integer divisions (+ the sum) for each prime.

The second trick was I sieved my primes and printed out the primes & exponents as I went along. So there was literally no delay before it started printing.

It's actually easier to factor n! than a number of similar size, because you're not factoring -- you know all the factors, you're just adding up the exponents.

2003-08-14, 09:25	#1
graeme Jul 2003 41 Posts	factorial puzzle (requires maths) For math's puzzle affectionados only, since I guess that your favourite large number program could give you the answer quite quickly. See if can do it without resorting to such new-fangled techniques. How many trailing zeros are there in 534! (that's factorial (534) ) Graeme

2003-08-14, 14:31	#4
jflin Aug 2003 5₁₆ Posts	Method Find all factors that will multiply by 10, 0-9 e.g. 2/5 = 10 4/5 = 20 6/5 = 30 8/5 = 40 So out of every 10 numbers, there are 5 that will give a trailing 0. 534 / 10 is about 53 complete series of 10 numbers. Since each series will hit every other series, and 2 out of 10 give 0's (0 and 5), each set of 10 numbers should give about 10 (Any * 0 is 0) + 4 (non-0 even * 5 = 0) 0's per series. so a rough guess would be 14^53 0's.

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Factorial puzzle	henryzz	Puzzles	5	2015-04-02 12:58
Factorial	mfgoode	Puzzles	6	2007-07-24 14:24
MATHS MUSINGS -I-Maths & Teaching Kung-Fu	devarajkandadai	Miscellaneous Math	0	2004-09-16 04:27
Perfect shuffling puzzle (requires programming)	NickGlover	Puzzles	18	2003-07-26 01:10
Factorial problem	xilman	Puzzles	12	2003-07-20 20:22

2003-08-14, 13:26	#2
Uncwilly 6809 > 6502 """"""""""""""""""" Aug 2003 101×103 Posts 2×3×7×233 Posts	At least 106. Rough calculation. 534/10=53 10's plus 53 5x2 pairs. 8)

2003-08-14, 14:26	#3
Orgasmic Troll Cranksta Rap Ayatollah Jul 2003 1010000001₂ Posts	131

2003-08-14, 15:06	#6
zacksg1 Aug 2002 Cincinnati 5₁₀ Posts	to solve this you need to count total pairs of 5's and 2's. since there are quite a few mroe 2's than 5's you need to count the total number of 5's in the factorization of this number. 534/5=106 534/(5^2)=21 534/(5^3)=4 534/(5^4)=0 adding... we get 106+21+4=131 so there are 131 trailing zeroes.

2003-08-18, 09:00	#7
graeme Jul 2003 41 Posts	131 is the right answer Graeme

2003-08-19, 20:40	#8
Maybeso Aug 2002 Portland, OR USA 112₁₆ Posts	I wrote a program in college that asked for a number n < 2^32, and spat out the prime factorization of n! almost as fast as they'd entered the number. (This was in 1986.) First they said it was faked, I couldn't possibly calculate or store n!, until they checked random entries. Then they said I had a table of every kth one up to the max they could verify and an exact interpolation method. Then for a while they were really impressed, ;) until I showed them the code. The trick was I never had to deal with n!, just n. I used zacksg1's idea recursively for all primes p < n.[list]534/5 = 106, total = 106 106/5 = 21, total += 21 21/5 = 4, total += 4 ... = 131[/list:u]This requires only log_p(n) integer divisions (+ the sum) for each prime. The second trick was I sieved my primes and printed out the primes & exponents as I went along. So there was literally no delay before it started printing. It's actually easier to factor n! than a number of similar size, because you're not factoring -- you know all the factors, you're just adding up the exponents.