3
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – vadim123 Oct 20 '14 at 15:10
  • $\begingroup$ 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. $\endgroup$ – A. Breust Oct 20 '14 at 15:13
  • $\begingroup$ @A.Breust You can use as many times as you want any digit. $\endgroup$ – Ioannes Oct 20 '14 at 15:16
  • $\begingroup$ Oh, the Milly comment about "sequence" meaning "consecutive" makes me realized I misunderstood, sorry. $\endgroup$ – A. Breust Oct 20 '14 at 15:17
9
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ Tiny point: I think you want $p(1,m)/p(1,n)=p(n+1,m)$ for $n<m$. Nice answer. $\endgroup$ – mjqxxxx Oct 20 '14 at 15:34
  • 1
    $\begingroup$ 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? $\endgroup$ – A. Breust Oct 20 '14 at 16:21
  • 1
    $\begingroup$ I think the point was that $16$ digits is the minimal number that forces a perfect square. $\endgroup$ – David K Oct 20 '14 at 17:40
  • 1
    $\begingroup$ @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. $\endgroup$ – ajotatxe Oct 20 '14 at 17:46
  • 3
    $\begingroup$ @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? $\endgroup$ – David K Oct 20 '14 at 17:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.