mersenneforum.org  

Go Back   mersenneforum.org > Fun Stuff > Puzzles

Reply
 
Thread Tools
Old 2003-08-14, 09:25   #1
graeme
 
graeme's Avatar
 
Jul 2003

41 Posts
Default 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
graeme is offline   Reply With Quote
Old 2003-08-14, 13:26   #2
Uncwilly
6809 > 6502
 
Uncwilly's Avatar
 
"""""""""""""""""""
Aug 2003
101×103 Posts

11×13×67 Posts
Default

At least 106.

Rough calculation. 534/10=53 10's plus 53 5x2 pairs. 8)
Uncwilly is online now   Reply With Quote
Old 2003-08-14, 14:26   #3
Orgasmic Troll
Cranksta Rap Ayatollah
 
Orgasmic Troll's Avatar
 
Jul 2003

641 Posts
Default

131
Orgasmic Troll is offline   Reply With Quote
Old 2003-08-14, 14:31   #4
jflin
 
Aug 2003

5 Posts
Default 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.
jflin is offline   Reply With Quote
Old 2003-08-14, 15:01   #5
Uncwilly
6809 > 6502
 
Uncwilly's Avatar
 
"""""""""""""""""""
Aug 2003
101×103 Posts

225558 Posts
Default

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.
Uncwilly is online now   Reply With Quote
Old 2003-08-14, 15:06   #6
zacksg1
 
Aug 2002
Cincinnati

510 Posts
Default

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.
zacksg1 is offline   Reply With Quote
Old 2003-08-18, 09:00   #7
graeme
 
graeme's Avatar
 
Jul 2003

2916 Posts
Default

131 is the right answer

Graeme
graeme is offline   Reply With Quote
Old 2003-08-19, 20:40   #8
Maybeso
 
Maybeso's Avatar
 
Aug 2002
Portland, OR USA

1000100102 Posts
Default

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.
Maybeso is offline   Reply With Quote
Reply

Thread Tools


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

All times are UTC. The time now is 00:53.

Sun May 16 00:53:38 UTC 2021 up 37 days, 19:34, 0 users, load averages: 1.52, 1.63, 1.68

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.