0

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.

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

3 Answers3

0

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.

mvw
  • 34,562
  • 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 09 '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 09 '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 09 '15 at 15:41
0

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

Joelafrite
  • 735
0

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.

vvg
  • 3,311