# Determine if a positive integer $x$ is a product of a power of 2 and a power of 5. $f(x) = 2^n \cdot 5^n$

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.

• Thanks for pointing that out. Editing the question to reflect them being NOT the same. – Raheel Khan Mar 9 '15 at 15:23
• 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{}$ – Michael Hardy Mar 9 '15 at 15:49
• MichaelHardy: Thank you. These edits are very helpful in learning/using Latex. – Raheel Khan Mar 9 '15 at 15:50

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.
• 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$? – Raheel Khan Mar 9 '15 at 15:32
• 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$. – mvw Mar 9 '15 at 15:39
• 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. – sranthrop Mar 9 '15 at 15:41
• 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}$