# Proof that for any $16$ digit number there is at least one sequence of $1$ or more digits which its product is a perfect square

I came across this problem where one is asked to proof that, for any $16$ digit number there is at least a sequence of $1$ or more digits which its product is a perfect square.

For example, in the number

$$4,562,348,973,245,984$$

The product of $$6·2·3=36$$ and $$\sqrt{36}=6$$ (third, fourth and fifth digit) is a perfect square.

I've been trying for a while now but haven't been able to come up with anything interesting.

I tried to approach the problem from a pigeon hole perspective, trying to prove that the number of perfect squares that can be made with the product of $1$ to $n$ digits, were each digit ranges from $0$ to $9$ is bigger or equal that the amount of perfect squares a $16$ digit number can hold by the number of $16$ digit numbers. Although I think this approach should work, I had a lot of trouble when trying to figure out the numbers (total number of perfect squares, perfect squares a $16$ digit number can have in the terms expressed above) in order to do the calculations.

So then I took a different approach which was trying to prove that for any $16$ digit number there was at least one product of $n$ (from $1$ to $16$) digits which its square root was an integer, but I don't know how to formulate this idea.

Obviously brute forcing it by hand its not an option as numbers and combinations are quite big.

How can I prove the statement to be true?

And on a more general topic,what goes through your mind when having to prove something? Which should be the steps taken?

As far as I see it there are some steps which are unavoidable:

1- Come out with some effects/requisites that derive from the assumption that the statement you want to prove ( the cause) is true or false.

2- Mathematicaly formulate them.

3- See if the expected effects/requisites are true and from that conclude that tge cause/the original statement has also to be true.

• Note: If any of the digits are $0,1,4,9$, then that alone is a perfect square. So you may assume without loss that the number is built from the remaining six digits. – vadim123 Oct 20 '14 at 15:10
• Can you use twice the same digits if it appears more than once? If so, the theorem can be shrunk to a 7-digit-number. – A. Breust Oct 20 '14 at 15:13
• @A.Breust You can use as many times as you want any digit. – Ioannes Oct 20 '14 at 15:16
• Oh, the Milly comment about "sequence" meaning "consecutive" makes me realized I misunderstood, sorry. – A. Breust Oct 20 '14 at 15:17

We can assume that the number does not have any digit equal to $0$. For if it has, then the statement is obvious. Note that the prime factors of the remaining digits are $2$, $3$, $5$ and $7$.

Now, for a given number whose prime factors are among ${2,3,5,7}$ define the function $$f(2^{a_2}3^{a_3}5^{a_5}7^{a_7})=(g(a_2),g(a_3),g(a_5),g(a_7))$$

Where $g(k)$ is $1$ if $k$ is odd and $0$ if $k$ is even. Consider the image as a vector of $\Bbb Z_2^4$.

This function takes $2^4=16$ possible values.

Now, lets write $p(n,m)$ for the product of the digits from $n$th to $m$th. Note that $f$ are defined for this values since their prime factors are always among $2,3,5$ and $7$. If some of the values $$f(p(1,m))$$ is $(0,0,0,0)$ then $p(1,m)$ is a square. If not, the set $\{f(p(1,1)),f(p(1,2)),\ldots,f(p(1,16))\}$ has at most $15$ different elements. So there are two equal values, say $p(1,n)$ and $p(1,m)$. Then $$f(p(n+1,m))=f\left(\frac{p(1,m)}{p(1,n)}\right)=f(p(1,m))-f(p(1,n))=(0,0,0,0)$$ so $p(n+1,m)$ is a square, q.e.d.

• Tiny point: I think you want $p(1,m)/p(1,n)=p(n+1,m)$ for $n<m$. Nice answer. – mjqxxxx Oct 20 '14 at 15:34
• Info. I made a program. For a 15-digit number, it found 232523272325232 with no subsequences as defined by the OP. Please note the palindromic effect, anybody knows where it comes from? – A. Breust Oct 20 '14 at 16:21
• I think the point was that $16$ digits is the minimal number that forces a perfect square. – David K Oct 20 '14 at 17:40
• @A.Breust Note the values that $f(p(1,1)),f(p(1,2)),\ldots,f(p(1,15))$ have. They are the binary representations of the numbers $1$ to $15$, read from right to left. – ajotatxe Oct 20 '14 at 17:46
• @A.Breust In your 15-digit number, each digit is prime. The middle digit $7$ occurs only once, so a square can only occur within one of the seven-digit subsequences before or after $7$. But each of those subsequences has only one $5$, leaving three digits on each side where we might still look for a square. But in each of those groups of three the middle digit occurs just once. This seems to require some symmetry. But I think your program's search strategy is responsible for the full palindromic effect; wouldn't $232532373532535$ also have no square subsequence? – David K Oct 20 '14 at 17:50