Number Of Trailing Zeros Is Divisible By 2015

Number Theory Level 5

Find the minimum integer $n$ such that the number of trailing zeroes of $(n+20)! \times (n + 15)!$ is divisible by 2015.

The answer is 4020.

2 solutions

Jake Lai
Jan 3, 2015

Let the trailing zeros of $m!$ be $f(m)$ ; the exact formula is given by Lengendre's formula

$f(m) = \sum_{k=1}^{\infty} \lfloor \frac{m}{5^{k}} \rfloor$

We can approximate our desired $n$ by ignoring the floor function:

$\sum_{k=1}^{\infty} \frac{n+20}{5^{k}}+\frac{n+15}{5^{k}} = \left( \frac{1}{1-\frac{1}{5}}-1 \right)(n+20+n+15) = \frac{2n+35}{4} > 2015a$

Now, testing with $a = 1$ , we get $n \geq 4013$ . Plugging in $n = 4013$ , $f(4013+20)+f(4013+15) = 2011$ . Increasing by $2 \times 5$ to $n = 4023$ gives $f(4013+20)+f(4013+15) = 2015$ for an upper bound; we know also now that $n$ exists for $a = 1$ .

Finally, after a while, after looking at smaller and smaller $n$ (or alternatively, by noting that $5 | 4020$ ), we see that $n = \boxed{4020}$ is our desired minimum.

I think for n=2480, the statement holds true

Pooja Vadiraj - 5 years, 10 months ago

Then we'll get only $624+620=1244$ trailing zeroes.

MD Omur Faruque - 5 years, 9 months ago

Vincent Miller Moral
Aug 3, 2015

def trailing_zeroes(n):
    i = 5
    ans = 0
    while i <= n:
        ans += n/i
        i *= 5
    return ans    

n = -15
while True:
    temp = trailing_zeroes(n+20) + trailing_zeroes(n+15)
    if temp % 2015 == 0:
        print n
        break
    n += 1

Even it is not allowed to solve it with code, the code is not short neither effective.

def lead(a, b = 0):
while a:
a//=5
b+=a
return b
n=0
while (lead(n+15)+lead(n+20))%2015 != 0:
n+=5

Alexey Kononenko - 5 years, 10 months ago

Or:

    n = -15
    total=1
    partial=1
    while (total % 2015 != 0):  
        n += 5
        total += partial
        partial=0
        while ((n+20)%(5**(partial+1))==0):
               partial += 1
        total+=partial
    print (n)

Peter Byers - 5 years, 9 months ago

I dont know. I've remembered the reason why I used dynamic programming in here - it was used in original code and I decided to do it shortly. Technically, python is quite bad with recursion, so it is much more efficient to use direct way. Also, (total%2015 !=0) equals to (not (total%2015)) and I am not sure which one is faster. in second while where you have ==0 you can just delete it - it will mean the same, the * thing is quite slow in python too - you could save the temporary result of powering. Also you can divide n by 5 strictly, cause n will be divided by 5 and have (n//5+4)%(5 *partial). In fact, the time for optimizing could be pretty long, but nobody wants to spend unnecessary time on polishing code for 1 time, which runs faster than a sec.

Alexey Kononenko - 5 years, 9 months ago

You are right, I think there could be some improvments in actually both. Can you explain how you did the python code tag? I used python and nothing happend. Time of your code on 10**5 repeats - 0.0010250341749191284. My code - 0.0014282305192947387 .

Alexey Kononenko - 5 years, 9 months ago

Number Of Trailing Zeros Is Divisible By 2015

The answer is 4020.

2 solutions

0 pending reports