Loading [MathJax]/extensions/TeX/AmsMath.js

Saturday, April 5, 2025

Oblong pandigital numbers

In this blogpost, I wrote about pandigital numbers (numbers in base n>1 that uses the numbers 0 to n-1 exactly once) that are also squares and a nice result of Adam Partridge that showed such square pandigital numbers do not exist if n is odd and n-1 has an even 2-adic valuation. A different approach to prove this result can be found in this article. It turns out that a similar result exists for oblong (or pronic) pandigital numbers.

Theorem: There are no oblong pandigital numbers in base n if n ≡ 3 (mod 4). 

Proof: Since nᵃ ≡ 1 (mod n-1), k ≡ m (mod n-1), where m is the digit sum of k in base n. Thus for a number k with every digit exactly once, k ≡ n(n-1)/2 (mod n-1).

Suppose n ≡ 3 (mod 4), i.e. n=2q+1 for some odd q. Then n(n-1)/2 = 2q²+q. Since n-1 = 2q, this means that n(n-1)/2 ≡ q (mod n-1). As q is odd, m(m+1) is even and n-1 is even, this implies that m(m+1) ≠ q (mod n-1) and thus m(m+1) is not a number with every digit exactly once and the proof is complete.

Conjecture: There are oblong pandigital numbers in base n if n !≡ 3 (mod 4).

Nearest integer with the same Hamming weight

Theorem: For a positive integer n, the nearest integer not equal to n with the same Hamming weight as n is larger than n if and only if n is odd.

Proof: If n is of the form 2ᵏ-1, then n is odd and there are no smaller positive integers with the same Hamming weight as n and the nearest integer not equal to n with the the same Hamming as n is equal to (3n+1)/2 > n.

Let us denote a(n) as the smallest integer > n with the same Hamming weight as n. For n not of the form 2ᵏ-1, let us denote b(n) as the largest integer < n with the same Hamming weight as n. Let us denote c(n) as the nearest integer not equal to n with the same Hamming weight as n.

If n is of the form (2ᵏ-1)*2ᵐ for some k, m>0, then n is even and in binary is of the form 11..1100..00 and a(n) = 2ᵏ⁺ᵐ+2ᵏ⁻¹-1, i.e. 100..0011..11 in binary. On the other hand, b(n) = (2ᵏ⁻¹-1)*2ᵐ⁺¹+2ᵐ⁻¹, i.e. 11..110100..00 in binary. Thus a(n)-n = 2ᵏ⁻¹-1+2ᵐ ≥ 2ᵐ and n-b(n) = 2ᵐ⁻¹ < 2ᵐ. Therefore c(n) = b(n).

If n is not of the form (2ᵏ-1)*2ᵐ, then n in binary is of the form xxx...xxx0yyy...yyy, where xxxxxx and yyyyy are both not all zeros. If yyy...yyy is of the form 2ʳ-1, then b(n) must flip one of the '1' bit in xxx...xxx whereas a(n) leaves xxx...xxx unchanged. Thus n-b(n) > a(n)-n. Otherwise a(n) and b(n) will not change the bits xxx...xxx and reduces to the problem for yyy...yyy and thus the result follows by induction.

In particular, this proof shows that c(n) = a(n) if n is odd and c(n) = b(n) if n is even. It also shows that a tie never occurs in determining c(n), i.e. a(n)-n is not equal to n-b(n) for all n>0.

In The On-Line Encyclopedia of Integer Sequences (OEIS), a(n) is given by sequence A057168, b(n) is given by A243109 and c(n) is given by A381764.


Thursday, February 29, 2024

Happy Leap Day 2024 and a modest proposal of determining leap years.

Today is February 29, 2024, a leap day. It occurs once during leap years once every 4 years when the year is divisible by 4, with some exceptions. Every 400 years, 3 of these years are not leap years. In particular, every century year (e.g. 1800, 1900, ...) that is not divisible by 400 is not a leap year. So there are 97 leap years every 400 years. 

The reason for that is that the mean tropical year which describes a complete cycle of seasons is the basis of the Gregorian calendar.  Currently (as the mean tropical year drifts over thousands of years), the mean tropical year is about 365 days, 5 hours, 48 minutes, 45 seconds = 365.2421875 days. Therefore 97/400 = 0.2425 approximates well the fraction 0.2421875 thus the current rule of leap years. However, there is a small mismatch which might needs to be compensated over hundreds of years.

Since 2421875/10000000 = 31/128, it might be better to have 31 leap years every 128 years, but the resulting rule might be too complicated for years written in decimal. However, if we represent years in binary (which how it is represented in modern computers anyway), then a possible rule is relatively simple. We could define a leap year as a year where in binary, the least significant 2 bits is 0, and the least significant 7 bits are not all 0.  Under this scheme, years divisible by 4 are leap years, except for a year that is divisible by 128. For instance, 1920 and 2048 will not be leap years in this scheme.

Looking at the continued fraction convergents (which describe the best rational approximations) of 2421875/10000000: 1/4, 7/29, 8/33, 31/128, there are other rules possible, but besides 1/4 (once every 4 years) none of the other intermediate convergents lead to an interesting rule.

Monday, February 26, 2024

Python module implementing various classes of graphs for networkx

 I have recently uploaded a python module to pypi:

  1. graph-generators: Python functions to compute various classes of networkx graphs. Available at: graph-generators · PyPI Some of the graphs include Keller graphs, Antelope graphs, Prism graphs, Lucas cube graphs, etc.

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.

Sunday, August 7, 2022

Songs with a single rhyme

I was listening to some Mandarin Chinese songs and noticed that the song "絲路" (Silk Road) by 梁靜茹 (Fish Leong) and the song 陪我看日出 (Watching the Sunrise With Me) by 蔡淳佳 (Joi Chua) share something interesting. All the rhymes in both songs end with the same vowel (the vowel u in IPA). Is this common in Mandarin Chinese songs? Does it occur frequently in other languages as well?

Friday, July 22, 2022

Happy π approximation day 2022!

Today is π approximation day (also known as casual π day). I talked about this 2 years ago in this blog post.

I first learned about the approximation 22/7 of π as a child and was fascinated with such approximations. I remember using a handheld calculator to find fractions that better approximates π by multiplying π with larger and larger integers and check when the result is close to an integer. This of course is a tedious process, but I was able to find some good approximations. A much better approach is to use continued fractions. The continued fraction expansion of π produces convergents which are the best rational fractions that approximates π. 

In countries using YY/MM, this whole month is π approximation month!

Monday, January 24, 2022

 I have recently uploaded 2 python modules to pypi:

  1. OEISsequences: Python functions to generate The On-Line Encyclopedia of Integer Sequences (OEIS) sequences. Available at: OEISsequences · PyPI. Functions are available to compute the n-th term of a sequence or generate subsequence terms (and sometimes both) depending on what is more efficient.

  2. algebraic-connectivity-directed: Python functions to compute various notions of algebraic connectivity of directed graphs. Available at: algebraic-connectivity-directed · PyPI. I defined an extension of Fiedler's seminal algebraic connectivity concept (1973) to directed graphs in a 2005 Linear and Multilinear Algebra paper and have refined the concept in subsequent papers over the years to better capture the connectivity of directed graphs especially when they are "far" from being undirected. More information on these various notions of algebraic connectivity of directed graphs can be found in the following references:

    1. C. W. Wu, "Synchronization in coupled arrays of chaotic oscillators with nonreciprocal coupling", IEEE Transactions on Circuits and Systems-I, vol. 50, no. 2, pp. 294-297, 2003.

    2. C. W. Wu, "Algebraic connecivity of directed graphs", Linear and Multilinear Algebra, vol. 53, no. 3, pp. 203-223, 2005.

    3. C. W. Wu, "On Rayleigh-Ritz ratios of a generalized Laplacian matrix of directed graphs", Linear Algebra and its applications, vol. 402, pp. 207-227, 2005.

    4. C. W. Wu, "Synchronization in networks of nonlinear dynamical systems coupled via a directed graph", Nonlinearity, vol. 18, pp. 1057-1064, 2005.

    5. C. W. Wu, "Synchronization in Complex Networks of Nonlinear Dynamical Systems", World Scientific, 2007.

    6. C. W. Wu, "Synchronization in dynamical systems coupled via multiple directed networks," IEEE Transactions on Circuits and Systems-II: Express Briefs, vol. 68, no. 5, pp. 1660-1664, 2021.



Sunday, December 26, 2021

OEIS Explorer

I created a visualization tool for The On-Line Encyclopedia of Integer Sequences (OEIS) using Streamlit. It has an interface to gplearn to use symbolic regression to get the equation describing the sequence. It is still very rudimentary, but was able to find the correct equation for simple sequences like the oblong numbers (https://oeis.org/A002378) and fourth powers (https://oeis.org/A000583)

The tool is accessible via this link.



Sunday, November 7, 2021

Chaotic Attractor Explorer with Streamlit (ChAES)

Following up on the following post, I have added a Streamlit web application to visualize various chaotic attractors (link).

It is still a very rudimentary app. I hope to be able to add more features in the future.