# Language of decimal encodings of cubes is not regular

Prove that the language that consists of cube numbers as strings is not regular.

I wanted to use pumping lemma but couldn't $$0, 1, 8, 27, 64, 125, 216, \dots$$

• Hm. { iⁱⁱⁱ, iiⁱⁱⁱ, iiiⁱⁱⁱ, iiiiⁱⁱⁱ, … } Apr 4 at 16:15
• Please don't roll back edits that others make to your question. See cs.stackexchange.com/help/editing.
– D.W.
Apr 5 at 4:51

Denote your language by $$L$$. Suppose that the pumping length is $$p$$. Consider $$N = (10^{p+1} + 1)^3 = 10^{3p+3} + 3 \cdot 10^{2p+2} + 3 \cdot 10^{p+1} + 1,$$ whose decimal encoding is $$w = 1 0^p 3 0^p 3 0^p 1 \in L.$$ According to the pumping lemma, we can write $$w = xyz$$ so that $$|xy| \leq p$$, $$y \neq \epsilon$$, and $$xz \in L$$. Since $$|xy| \leq p$$, the part $$xy$$ lies within the prefix $$10^{p-1}$$. If $$y$$ contains $$1$$ then $$xz$$ has a leading zero, which is impossible (if you allow leading zeroes, consider $$L \cap (1+9)(0+9)^*$$ instead), so $$y$$ consists only of zeroes. Hence $$xz = 10^q 30^p 30^p 1,$$ for some $$q < p$$, which encodes the number $$n = 10^{2p+q+3} + 3 \cdot 10^{2p+2} + 3 \cdot 10^{p+1} + 1.$$ If $$xz \in L$$ then $$n$$ is a cube. Since $$n$$ ends with $$1$$, necessarily $$n = 10m + 1$$ (you can check this directly by considering $$0^3,1^3,\dots,9^3$$), and so $$10^{2p+q+3} + 3 \cdot 10^{2p+2} + 3 \cdot 10^{p+1} + 1 = 1000 m^3 + 300 m^2 + 30m + 1,$$ which implies that $$(10^{p+q+2} + 3 \cdot 10^{p+1} + 3) 10^p = (100 m^2 + 30 m + 3) m.$$ Clearly $$100m^2 + 30m + 3$$ is divisible by neither $$2$$ nor $$5$$ (its units digit is $$3$$), and so $$10^p$$ must divide $$m$$. In particular, $$m \geq m_0 := 10^p$$. However, this is impossible, since $$N = (10m_0 + 1)^3$$, and $$n < N$$.
• @user15550465 The decimal encoding of a number is its encoding in base 10. For example, the decimal encoding of 81 is 81 (its hexadecimal encoding, in contrast, is 51). Your language consists of all decimal encodings of cubes (with or without leading zeroes — you haven't made that clear). Apr 4 at 19:41