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$

Question

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.

Answer 1

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.

Answer 2

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}$

Answer 3

Given $x$ compute,

($x \mod 4$, $x \mod 25$)

If both are zero, then $x$ has $2^m$ and $5^n$ as factors for some $m >= 2, n >= 2$. Since you don't need the actual factors, this would be the fastest.