The previous post discussed what the periodic table would look like if it could be extended indefinitely and if certain patterns in the actual table continued to hold. In particular, the last element of each period would have atomic number

and so we could call the Z_n in the equation above noble numbers, atomic numbers of noble gases.

We could then look at the generating function for the noble numbers by multiplying each Z_n by xⁿ and summing.

There’s no practical reason I can imagine for computing this other than it provides an excuse to play around with generating functions.

Does the series above converge? For some purposes it doesn’t matter. Generating functions are often useful as formal sums even if if they do not converge as analytic functions.

However, this function does converge. The Z_n grow like a polynomial function of n, and for |x| < 1, the xⁿ terms decrease exponentially as a function of n, so the series converges. The series has radius of convergence 1 because it clearly diverges for |x| > 1.

We can do better than saying the series converges: we can find the sum in closed form. We’ll use Mathematica to do the calculation for us.

    Sum[((-1)^n (3 n + 6) + 2 n^3 + 12 n^2 + 25 n - 6 ) x^n, 
        {n, 1, Infinity}]/12

This returns the following rational function:

Note that the generating function has singularities at -1 and 1. This confirms our argument above that the radius of convergence should be 1.

We can use Mathematica to expand the generating function as a series, and we should recover the atomic numbers of the noble gases.

    Series[g[x], {x, 0, 7}]

And indeed we do:

More on generating functions

• Moment generating functions
• Making change
• Hypergeometric distribution and series

A couple weeks ago I wrote a post about the year share component of calculating the day of the week. To calculate the day of the week, you need to add the day of the week, a constant for the month, and the year share. Calculating year share is not that hard, but it’s the hardest step to carry out in your head.

The year share of a date y is

⌊5y/4⌋ % 7

where y is the last two digits of a year. There’s no need to multiply by 5, since you could compute

(y + ⌊y/4⌋) % 7

but this still takes some effort if y is large.

The earlier post gave nine different ways to compute the year share, and the easiest in my opinion is method #6:

1. Round y down to the most recent leap year and remember how much you had to round down. Call that amount r.
2. Let t be the tens value and u the units value.
3. Return (2t – u/2 + r) % 7.

In symbols,

1. Let y‘ = 4 ⌊y/4⌋ and r = y – y‘.
2. Let t = ⌊y’/10⌋ and u = y‘ % 10.
3. Return (2t – u/2 + r) % 7.

This method has a longer description but is easier to carry out mentally as the following examples illustrate.

Examples

Let y = 97. Here are the calculations required by the direct method.

1. ⌊y/4⌋ = 24
2. 97 + 24 = 121
3. 121 % 7 = 2

Here are the calculations required by the second method.

1. y‘ = 96 and r = 1.
2. t = 9 and u = 6.
3. (2*9 – 3 + 1) % 7 = 2

The former requires adding two 2-digit numbers. The latter requires doubling a single digit number and subtracting another single digit number.

The former requires reducing a 3-digit number mod 7 and the latter requires reducing a 2-digit number mod 7. Furthermore, the 2-digit number is never more than 18.

Proof

To prove that the two methods are equivalent we have to prove

⌊5y/4⌋ ≡ 2t – u/2 + r mod 7

which is kinda messy. The way t, u, and r are defined prevent this from being a simple algebraic calculation.

We can verify that

⌊5y/4⌋ ≡ 2t – u/2 + r mod 7

for y = 0, 1, 2, … 19 by brute force then prove the rest by induction. We’ll show that if the congruence holds for y then it holds for y + 20.

Suppose you increase y by 20. Then ⌊5y/4⌋ increases by 25. The value of t increases by 2, and the values of u and r remain unchanged, so the right side increases by 4. Since 25 % 7 = 4, the congruence still holds.

The previous post looked at the tetrahedral numbers:

1, 4, 10, 20, 35, …

We could invert the process of creating tetrahedral numbers and ask for what n is a given number the nth tetrahedral number. So the inverse of 1 is 1, the inverse of 4 is 2, the inverse of 10 is etc.

We can find the nth tetrahedral number by evaluating a cubic polynomial in n

and so we could invert this for a given x by solving p(n) = x for n. The result is complicated, but it can be written in closed form:

We could do the same for generalized tetrahedral numbers. The nth tetrahedral number of dimension d is given by a polynomial in n of degree d, and so in principle we could look for the roots of these polynomials, though we shouldn’t expect closed forms expressions for the roots in general.

Now if x is a tetrahedral number, i.e. x is an integer such that p(n) = x for some positive integer n, then this value of n is unique as far as positive integers go. The sequence of tetrahedral numbers is increasing, so it has a unique inverse, if it has an inverse at all.

Now suppose x is not a tetrahedral number, and maybe not even an integer. We can still solve the equation p(n) = x. And if x > 0 then there is a real root given by the equation above. What are the other roots like?

We can find out by computing the discriminant of the equation p(n) – x = 0, which works out to be

When the discriminant is positive, there are three real roots. When the discriminant is negative, there is one real root and two complex roots.

So, for example, the tetrahedral inverse of 10 is 3, but you could say that -3 ± √11 i are also inverses.

For another example, the real tetrahedral inverse of 7 is 2.57189… and there is also a conjugate pair of complex inverses.

You might think that if zip codes are close, then the regions they represent are close. Or that if zip codes are consecutive, then their regions touch. Neither of these are true. I explore how far they are from being true in the next post.

But these statements could have been true [1]. It’s possible to lay a grid on a region and number the squares in the grid in such a way that consecutive numbers correspond to contiguous squares, and nearby numbers correspond to nearby squares. There are geocoding systems that accomplish this using Hilbert curves. For example, Google’s S2 system is based on Hilbert curves.

A Hilbert curve is a curve that winds through a square, coming arbitrarily close to every point in the square. A Hilbert curve is a fractal, defined as the limit of an iterative process. We aren’t concerned with the limit because we only want to carry out a finite number of steps in the construction. But the fact that the limit exists tells us that with enough steps we can get any resolution we want.

To illustrate Hilbert curves and how they could be used to label grids, we will use a Hilbert curve to tour a chessboard. We will number the squares of a chess board so that consecutive numbers correspond to neighboring squares.

Here’s Python code to produce our numbering.

    from hilbertcurve.hilbertcurve import HilbertCurve

    p = 3 # 2^3 squares on a side
    n = 2 # two dimensional cube, i.e. square

    hc = HilbertCurve(p, n)

    for row in range(2**p):
        for col in range(2**p):
            d = hc.distance_from_point([row, col])
            print(format(d,"2d"), " ", end="")
        print()

This produces the following output.

     0   1  14  15  16  19  20  21  
     3   2  13  12  17  18  23  22  
     4   7   8  11  30  29  24  25  
     5   6   9  10  31  28  27  26  
    58  57  54  53  32  35  36  37  
    59  56  55  52  33  34  39  38  
    60  61  50  51  46  45  40  41  
    63  62  49  48  47  44  43  42  

Here’s Python code to draw lines rather than print numbers.

    N = (2**p)**n
    points = hc.points_from_distances(range(N))

    for i in range(1, N):
        x0, y0 = points[i-1]
        x1, y1 = points[i]
        plt.plot([x0, x1], [y0, y1])
    plt.gca().set_aspect('equal')    
    plt.show()

This produces the following image.

There’s a small problem. Following the square numberings above produces a Hilbert curve, and the plotting code produces and Hilbert curve, but they’re not the same Hilbert curve. The implicit axes created by our sequence of print statements doesn’t match the geometry in the plotting code. To get the curves to match we need to do a sort of change of coordinates. We can do this by changing the call to plt.plot to

    plt.plot([y0, y1], [8-x0, 8-x1])

This produces the following plot, matching the numbering above.

Related posts

• Maidenhead geocode system
• Decoding a grid square
• Mathematics and radio

[1] It could have been true in the sense that it was theoretically possible. It might not have been practically possible. Postal codes have different design constraints than geocodes.