3

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.

Ioannes
  • 386
  • 1
    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

2 Answers2

10

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.

ajotatxe
  • 65,084
  • 2
    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
  • @mjqxxxx Oh, yes. You have a point :) – ajotatxe Oct 20 '14 at 15:37
  • 1
    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
  • 1
    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
  • 1
    @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
  • 3
    @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
  • @DavidK Right. My program was looking for the smallest number. Tweaking it, it has found a lot with no palindrom. – A. Breust Oct 21 '14 at 07:26
1

First, if any digit is a zero, it in itself is a square. Thus, let’s assume that there are no zero digits.

Now look at all products of digits starting from the first digit to either itself or some later digit. There are $16$ of those products: if the digits are $a_1,a_2,\ldots,a_{16}$, we are here looking at the products: $p_1=a_1, p_2=a_1a_2, p_3=a_1a_2a_3,\ldots,p_{16}=a_1a_2\cdots a_{16}$. Notice all those products have, as prime factors, only $2$,$3$,$5$ and $7$.

Recall that a number is a square if all prime factors of it have even powers. Thus, let’s watch the parities of the powers of $2,3,5,7$ (in that order) in $p_1,p_2,\ldots,p_{16}$. Obviously, each of them can be “odd” or “even” - two choices, so all four parities give you $2^4=16$ choices/quadruplets for the four parities. For example: (even, even, even, even), (even, even, even, odd), ..., (odd, odd, odd, odd).

Now, there are only two possibilities:

  • All $p_1,p_2,\ldots,p_{16}$ have different (quadruplets of) parities. Thus, one of them (say $p_i$) must have the parities (even, even, even, even). Thus, $p_i=a_1a_2\cdots a_i$ is a square.
  • Two of $p$’s have the same (quadruplets of) parities. If, say, $p_i$ and $p_j$ have the same parities, for $i<j$, then $\frac{p_j}{p_i}=a_{i+1}a_{i+2}\cdots a_j$ is a square.