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.

Sunday, January 3, 2021

Googol, Google and Isaac Asimov

I have been a huge fan of Isaac Asimov's fiction since I was a youngster. I have read all his Robot series and Foundation series books and many of his short stories. I was fortunate enough to hear him speak at our university when I was an undergraduate student. In one of his (many) non-fiction books he wrote that 

"For instance, in a book entitled Mathematics and the Imagination (published in 1940) the authors, Edward Kasner and James Newman, introduced a number called the `googol,' which is good and large and which was promptly taken up by writers of books and articles on popular mathematics. Personally, I think it is an awful name, but the young child of one of the authors invented it, and what could a proud father do? Thus, we are afflicted forever with that baby-talk number."

Asimov passed away in 1992, 6 years before Google was founded and before the internet is woven into the fabric of our lives, ranging from communication to entertainment to commerce. As is well known, Google chose the name as a play-on-words of the word googol. I wonder what Asimov would have thought of the fact that a word derived from the "baby-talk" word is the name of one of the largest technology companies on the planet and is also used to denote the act of finding out information via the vast information source that is the World Wide Web, technological developments that I am sure he would have love to see.


Saturday, December 26, 2020

Harmonic mean of integers

The harmonic mean of a set of $n$ numbers $x_i$ is defined as $\frac{n}{\sum_{i=1}^n x_i^{-1}}$. While investigating the number of subsets of $\{1,...,n\}$ such that the harmonic mean is an integer (OEIS sequence A339453), I formulated and proved the following result, which states that for $n >1$ positive integers whose maximum is a prime power that is attained by a single element, their harmonic mean is not an integer:

Theorem: Let $x_i$ be a finite set of positive integers such that $x_j = \max_i x_i = p^k$ for some prime $p$ and positive integer $k$ and all other numbers $x_i$ are strictly less than $p^k$, then the harmonic mean of $\{x_i\}$ is not an integer.

Proof: Let $M$ be the least common multiple of $\{x_i\}$. Assume that $x_i$ are sorted in nondecreasing order. Thus $x_n = p^k$ and $x_i < p^k$ for all $i<n$ . Then $M = Wp^k$ where $p$ does not divide $W$. Let $Q_i = M/x_i$ and $Q = \sum_i Q_i$. This implies that $Q_n = W$ and $p$ divides $Q_i$ for $i <n$.

The harmonic mean $H$ can then be written as $nM/Q$. Since $p$ does not divide $W$, this implies that $p$ does not divide $Q$. Suppose $H$ is an integer. Then this implies that $Q$ divides $nM/p^k = nW$.

As $x_i < x_n$ for $i < n$, this implies that $Q_i > W$ for $i < n$, i.e. $Q > nW$, and this contradicts the fact that $Q$ divides $nW$ and thus $H$ is not an integer.