Monday, February 26, 2024

Square pandigital numbers

Let a pandigital number in base $n$ be defined as a number that uses the digits from $0$ to $n-1$ exactly once. See OEIS sequence A050278 for pandigital numbers in base 10 (This is called pandigital version 1 in OEIS. Pandigital version 2 are numbers that uses the digits from $0$ to $n-1$ at least once). Adam Partridge gave a wonderful proof of why no pandigital numbers in base 13 can be squares. In particular, he showed in his blog post that if $n$ is odd and $n-1$ has an even 2-adic valuation (OEIS A007814), then there are no pandigital squares in base n. His proof goes as follows: first write a number $m$ as $\sum_{i=0}^{n-1}a_i n^i$ where $a_i$ are the $n$-ary digits of $m$. Next, note that 

$$m-\sum_{i=0}^{n-1}a_i=\sum_{i=0}^{n-1}a_i(n^i-1)=\sum_{i=1}^{n-1}a_i(n^i-1).$$ 

For a pandigital number $\sum_i a_i = n(n-1)/2$. Since  $\sum_i a_i$ is divisible by $\frac{n-1}{2}$ and $n^i-1 = (n-1)(1+n+...+n^{i-1})$ is divisible by $n-1$ for $i>0$, the number $m$ can be factored as

$$m=\frac{n-1}{2}\left(n+2\sum_{i=1}^{n-1} a_i(1+n+...+n^{i-1})\right)$$

If $n$ is odd and $n-1$ has an even 2-adic valuation, then the term $n+2\sum_{i=0}^{n-1}a_i(1+n+...+n^{i-1})$ is odd (i.e. has zero 2-adic valuation) and $(n-1)/2$ has an odd 2-adic valuation, then $m$ has an odd 2-adic valuation and thus cannot be a square, which concludes the proof.

It is interesting to note that the equation of the factorization above does not include $a_0$, the least significant digit. Of course, $a_0$ does play a role since the pandigital property implies that $a_i\neq a_0$ for all $i>0$ and $a_0$ can be obtained from the other digits via $a_0=n(n-1)/2-\sum_{i=1}^{n-1}a_i$.

For an extension of this result, let's consider now zeroless pandigital number in base $n$, i.e. numbers that use the digits from $1$ to $n-1$ exactly once. Then again $\sum_i a_i = n(n-1)/2$ and the same argument shows that if $n$ is odd and $n-1$ has an even 2-adic valuation, then there are no zeroless pandigital square numbers in base $n$.

For numbers $m$ in base $n$ that uses the digits from $0$ to $n-2$ exactly once, $\sum_i a_i = (n-1)(n-2)/2$ and 

$$m=\frac{n-1}{2}\left(n-2+2\sum_{i=1}^{n-2} a_i(1+n+...+n^{i-1})\right)$$ 

and again this shows that if $n$ is odd and $n-1$ has an even 2-adic valuation, then there are no such square numbers in base $n$. Similarly, for such $n$, there are no such square numbers in base $n$ that uses the digits from $1$ to $n-2$ exactly once.

Consider next square numbers in base $n$ whose digits are taken from a range $[j,j+1,..., k]$ exactly once for some $0\leq j\leq k<n$ (the largest of which are listed in OEIS A370371).

If such numbers have $n$ digits, then the range must be of the form $[0,..,n-1]$. If such numbers have $n-1$ digits, then the range must be of the form $[1,..,n-1]$ or $[0,..,n-2]$. The above discussion shows that if $n$ is odd and $n-1$ has even 2-adic valuation, then such square numbers must have at most $n-2$ digits and they cannot be in the range $[1,..,n-2]$. The largest base $n$ number of $n-2$ digits that uses each digit exactly once has digits in the range $[2,...,n-1]$ and is equal to $a=\sum_{i=2}^{n-1} i\times n^{i-2}$ (OEIS A370671) and this is an upper bound of OEIS A370371 when $n$ is odd and $n-1$ has an even 2-adic valuation.

No comments:

Post a Comment