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 ∑n−1i=0aini where ai are the n-ary digits of m. Next, note that
m−n−1∑i=0ai=n−1∑i=0ai(ni−1)=n−1∑i=1ai(ni−1).
For a pandigital number ∑iai=n(n−1)/2. Since ∑iai is divisible by n−12 and ni−1=(n−1)(1+n+...+ni−1) is divisible by n−1 for i>0, the number m can be factored as
m=n−12(n+2n−1∑i=1ai(1+n+...+ni−1))
If n is odd and n−1 has an even 2-adic valuation, then the term n+2∑n−1i=0ai(1+n+...+ni−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 a0, the least significant digit. Of course, a0 does play a role since the pandigital property implies that ai≠a0 for all i>0 and a0 can be obtained from the other digits via a0=n(n−1)/2−∑n−1i=1ai.
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 ∑iai=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, ∑iai=(n−1)(n−2)/2 and
m=n−12(n−2+2n−2∑i=1ai(1+n+...+ni−1))
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≤j≤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=∑n−1i=2i×ni−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