0
$\begingroup$

Determine if a positive integer $x$ is a product of a power of $2$ and a power of $5$.

$f(x) = 2^m \cdot 5^n$
where $0 < x < 32$
and $0 < m < 32$ and $0 < n < 32$

This has to do with computational efficiency so I want to know if the decimal or binary representations of $x$ can answer the question rather than having to extract factors by brute force as follows:

Iterate $i$ from $2$ to $\operatorname{ceiling}(\sqrt n)$ where $i$ is a power of $2$ or a power of $5$ or a product of either.

Brute force performance is acceptable for 32-bit integers but slows down exponentially as the size of the integers increase. I will be dealing with numbers around the order of $2^{1,024}$.

NOTE: I do not need the actual factors.

$\endgroup$
  • $\begingroup$ Thanks for pointing that out. Editing the question to reflect them being NOT the same. $\endgroup$ – Raheel Khan Mar 9 '15 at 15:23
  • 1
    $\begingroup$ You can write $2^m\cdot 5^n$ or $2^m\times 5^n$. Writing $2^m*5^m$ is a workaround for situations where one is restricted to the characters on the keyboard. I changed that and I also changed $ceiling(sqrt(n))$ to $\operatorname{ceiling}(\sqrt n)$. ${}\qquad{}$ $\endgroup$ – Michael Hardy Mar 9 '15 at 15:49
  • $\begingroup$ MichaelHardy: Thank you. These edits are very helpful in learning/using Latex. $\endgroup$ – Raheel Khan Mar 9 '15 at 15:50
0
$\begingroup$

If the exponents are $2^n$ and $5^m$ then the number $2^n 5^m$ will have $\min\{m,n\}$ trailing zero digits in decimal (base 10) representation.

$\endgroup$
  • $\begingroup$ Can I also assume the inverse? That is if $x$ in base 10 has a minimum of or exactly $min(m,n)$ trailing zeros, then $x$ is definitely a product of $2^m5^n$? $\endgroup$ – Raheel Khan Mar 9 '15 at 15:32
  • $\begingroup$ That is a consequence of the prime factorization. Every trailing zero needs one factor $2$ and one factor $5$. So $5000$ must have at least the factor $2^3 5^3$. $\endgroup$ – mvw Mar 9 '15 at 15:39
  • $\begingroup$ No: $10=2\cdot5$ has one trailing zero, but so does $30=3\cdot 2\cdot 5$, which is not a product of only 2s and 5s. $\endgroup$ – sranthrop Mar 9 '15 at 15:41
0
$\begingroup$

One of the fastest ways is:

  • Write $x$ as the product of a power of $2$ and a power of $5$ : $x = 2^{m} 5^{n}$

  • Check if $m,n\in\mathbb{N}$

$\endgroup$

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.