0
$\begingroup$

This question is doable if you can calculate the number by multiplying f(n-1) and f(n-2).

Is it possible to do this question if we entirely want to skip multiplying these 2 numbers and still be able to calculate say the number of trailing zeros in f(20).

Why do I want to skip multiplying these two numbers?
Because as this function grows exponentially, so does the value. We might get an integer overflow on some languages. Hence.
Also, our aim is to calculate the number of trailing zeros and not calculate the number itself.

What I tried. To try and calculate trailing zeros and f(n-1) and f(n-2), So that I deduce the number of trailing zeros in f(n) and go on from there.

But to calculate trailing zeros in f(n-1), I need to know what f(n-1) is? Which is where my whole approach fails.

$\endgroup$
  • $\begingroup$ If you're a tad clever you can reduce this to a Fibonacci like problem. The result will be a power of 2. What happens if you try and calculate log2(f(n)) instead of calculating f(n)? Also zeros in what base? base 10? $\endgroup$ – Jake Jun 13 '18 at 13:06
  • $\begingroup$ Yes, zeros in base 10. The numbers are also, in base 10. $\endgroup$ – Saras Arya Jun 13 '18 at 13:49
  • $\begingroup$ Your editing makes existing answer invalid. I think it is better to ask a new question instead of editing. $\endgroup$ – xskxzr Jun 14 '18 at 3:32
  • $\begingroup$ To have a trailing zero you need a 5 factor for every 2 factor. This will never have any 5 factors and will thus never have any trailing zeros. This problem can be solved in constant time by returning zero. $\endgroup$ – Jake Jun 17 '18 at 14:59
4
$\begingroup$

Assuming f(0) and f(1) are integers, find which powers of two and of five are factors of f(0) and f(1). The powers in f(n) can be calculated like a Fibonacci sequence and the number of trailing zeroes is the smaller of both sequences.

The Fibonacci series is defined by $fib(0)=0$, $fib(1)=1$, and for $n≥2$ we have $fib(n) = fib(n-2)+fib(n-1)$, so the series starts (0, 1, 1, 2, 3, 5, 8, 13 ...). If we start with different values and use the same recursion formula, we get for example the sequence (1, 0, 1, 1, 2, 3, 5, 8, 13...). If we define $fib(-1)=1$, then the n-th element of this sequence equals $fib(n-1)$.

The sequence starting with (x, y) and the same recursion formula (x, y, x+y, x+2y, 2x + 3y ...) equals $x \cdot fib(n-1) + y \cdot fib (n)$.

Let $f(0)$ have the factor $2^x$ and $f(1)$ the factor $2^y$ and no higher power of two, then $f(n)$ has the factor $2^z$, where $z = x \cdot fib(n-1) + y \cdot fib (n)$.

Likewise, let $f(0)$ have the factor $5^a$ and $f(1)$ the factor $5^b$ and no higher power of five, then $f(n)$ has the factor $5^c$, where $c = a \cdot fib(n-1) + b \cdot fib (n)$.

The number of trailing zeroes in $f(n)$ is

    $min(z_n, c_n)$ where 

    $z_n = x \cdot fib(n-1) + y \cdot fib (n)$
    $c_n = a \cdot fib(n-1) + b \cdot fib (n)$
$\endgroup$
2
$\begingroup$

You can prove by induction that your sequence is actually f(n) = $2^{u_n}$ with $u_n$ the n-th term of the fibonacci sequence. The number of trailing zeroes in base 2 is thus $u_n$.

In base 10 however, the number of trailing zeroes will always be 0, because for any n, there is no 5 in the prime decomposition of f(n).

$\endgroup$
  • $\begingroup$ Can we generalize this? say f(0) = 2 and f(1) = 5. Would our answer completely change? Or does it scale for different input? f(2) = 10 f(3) = 50 f(4) = 500 $\endgroup$ – Saras Arya Jun 13 '18 at 14:25
  • $\begingroup$ the answer would completely change. with f(0)=2 and f(1)=5, you can prove by induction that from 1 on, the numbers are of the form $5^k\cdot 10^x$, then you just need to analyse $x$, which is $u_{n-1}$, so the number of trailing zeros are the number in the fibonacci sequence. I'd that that in general, it will be either part of the fibonacci sequence, possibly shifted, or always 0. $\endgroup$ – Florian Bourse Jun 14 '18 at 8:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.