Trailing 0 0 s in ( 10 ! ) ! (10!)!

Find the number of trailing 0 0 s (zeros) in

( 10 ! ) ! \large \color{#3D99F6} (10!)!


The answer is 907197.

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

1 solution

Zach Bian
Dec 29, 2017

http://www.wolframalpha.com/input/?i=(10!)!

But if that's too cheaty: Algorithm explained here

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
# Ten factorial. Easily done with pen and paper. Or a calculator. Or google or...
# You get the picture:
tenFac = 3628800;
expo = 1
accumulator = 0

while True:
    cache = tenFac//(5**expo)
    if cache == 0:
        break
    accumulator += cache
    expo += 1

print(accumulator)

And if you still think that's too cheaty, here is the same thing in x86 Assembly Code. It's in 32-bit because my compiler is bugged and won't compile 64-bit code at the moment :\

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
// Compiles with `gcc -nostdlib`. On 64-bit machines, use the `-m32` flag also.
#define SYS_EXIT    $1
#define SYS_WRITE   $4

#define STDOUT      $1

#define TENFAC $3628800

.global _start
.text

/* void* itoa(int, char *) 
   - char * points to the *back* of the string. itoa writes from ls digit.
   - clobbers edi, eax, edx
   - returns pointer to beginning of string as eax
*/
itoa:
    pushl   %ebp
    movl    %esp, %ebp

    movl    8(%esp), %edi
    movl    12(%esp), %eax

    cycledigits:
        xorl    %edx, %edx
        divl    decimal
        addl    $48, %edx       // Add 48 to remainder, store digit
        movb    %dl, (%edi)     // Copy char
        decl    %edi            // Next digit
        cmpl    $0, %eax
        jg      cycledigits     // No more digits?

    leal    1(%edi), %eax       // return value

    popl    %ebp
    ret

_start:
    /* Entry Point: */
    movl %esp, %ebp         // Stack setup

    movl $5, %ebx           // Denominator
    movl $5, %edi           // multiply by this
    movl $0, %esi           // Accumulator

loopbody:
    xorl %edx, %edx
    movl TENFAC, %eax       // Dividend always ten factorial
    divl %ebx
    cmpl $0, %eax
    je display
    addl %eax, %esi
    movl %ebx, %eax
    mull %edi
    movl %eax, %ebx
    jmp loopbody

display:
    pushl %esi
    pushl $numstring
    call itoa
    addl $8, %esp
    movl %eax, %ecx         // Address of ptr
    subl $numstring, %eax
    negl %eax
    leal 2(%eax), %edx      // characters to display (including linefeed)
    /*
        Linefeed SHOULDN'T be necessary, but in case your terminal flushes the output line like mine does, we want it to display. Also, it looks cleaner.
    */
    movl STDOUT, %ebx
    movl SYS_WRITE, %eax
    int  $0x80

exit:
    movl    SYS_EXIT, %eax
    xorl    %ebx, %ebx              // The exit code.
    int     $0x80

.data
    /* Begin Data Section: */
    decimal:  // base 10
        .long 10
    buffer:
        .ascii "xxxxxxxxxx"
    numstring:
        .byte 'x
    linebreak:
        .byte '\n

Can we solve this problem without using computer assistance?

Pi Han Goh - 3 years, 5 months ago

Log in to reply

What? Without any computers? As in, pencil and paper only, no calculators or cell phones, good luck, you have 60 minutes? The answer is, of course, "yes," you could, but why? Once I have the algorithm, I don't see the point of spending disproportionately large amounts of time with its implementation. But if that's what you really wanted, I've modified my answer.

Zach Bian - 3 years, 5 months ago

Log in to reply

Well, this question is not marked as "Computer Science", but as "Number Theory", so I was wondering whether it could be done by hand or not

Pi Han Goh - 3 years, 5 months ago

You could easily do this in under an hour with a little bit of basic division and addition. As long as you can calculate 10! to be 3628800, then the algorithm is that you find the number of 5's, number of 25's, number of 125's, etc (powers of 5) that divide into this number (ignore the remainder), then add them all up.

One of my students discovered that if you start with 3628800, and then keep dividing by 5 each time, discarding the remainder, you will also arrive at the same answer. You don't even need to know your powers of 5 in that method, but I've included them here for everyone's enjoyment.

5's: 725760 25's: 725760/5 = 145152 125's: 145152/5 = 29030 (discard remainder) 625's: 29030/5 = 5806 3125's: 5806/5 = 1161 (discard remainder) 15625's: 1161/5 = 232 (discard remainder) 78125's: 232/5 = 46 (discard remainder) 390625's: 46/5 = 9 (discard remainder) 1953125's: 9/5 = 1 (discard remainder)

Total: 725760 + 145152 + 29030 + 5806 + 1161 + 232 + 46 + 9 + 1 = 907197 Took far less than an hour, and a calculator is not necessary.

j c - 3 years, 5 months ago

Log in to reply

An hour? Who’s got that kind of time? Oh, wait. I spent a couple writing that assembly file. The method your student found seems obvious in retrospect. Hard to believe I missed that one!

Zach Bian - 3 years, 5 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...