Bowers Exploding Array Function discussion part 1: Linear and planar arrays

Well, it’s been another full year without me making a post about people’s attempts at formally defining Jonathan Bowers’ Exploding Array Notation. This post is the first in an attempted series to discuss the rules for some subsystems of BEAF and the various ways that people have interpreted Bowers’ unformalized ideas of “array spaces.”

I begin by introducing arrays in a somewhat non-traditional way, which is similar to the description from Bowers’ Spaces page (Some people have trouble loading the page so the Internet Archive link should also work: https://web.archive.org/web/20201102164403/https://www.polytope.net/hedrondude/spaces.htm). My goal is to emphasize the structure of the space the array lives in, rather than the array itself. I won’t spend much time going over example calculations to give a sense of how unimaginably large the numbers get, either. There is a good explanation on Googology Wiki of how BEAF easily creates numbers that surpass Graham’s number, as well as the most common large number generating functions, such as up-arrow notation and chained arrow notation: https://googology.wikia.org/wiki/Introduction_to_BEAF.

Linear arrays

To understand linear arrays, just imagine an infinite row of boxes where positive integers can be placed. The row has a beginning but no end. Each box is indexed by an integer, and for the purpose of this discussion we will say these indices start at 0. The default value for a box is 1, and all but finitely many boxes must contain the value 1. When we write an array like this: {a, b, c…}, the values in the brackets are in sequential positions starting from entry 0, and all remaining entries are 1, so the array is inside an infinite sea of 1’s. In general, an array can be considered a collection of numbers at various positions inside an infinite (hyper-)dimensional space of 1’s.

Bowers has a lot of terms for various entries in the array which he uses when he defines his rules.
Definitions:

• Entry 0 is called the base.
• Entry 1 is called the prime.
• The first entry after the prime that is not 1 is called the pilot.
• The entry right before the pilot is called the copilot.

The array is solved into an integer by means of applying a series of steps repeatedly until either the base rule or prime rule applies, and then a value is returned.

Rules

Let b be the base and p be the prime.

• Base rule: If every entry besides the base and the prime is 1, the array evaluates to b^p.
• Prime rule: If p = 1, the value b is returned.
• Catastrophic rule: If neither of the above rules apply, the array is changed in the following way:
• The pilot is decreased by 1.
• The copilot becomes the value of the original array, but with the prime decreased by 1.
• Besides the copilot, every entry before the pilot changes to b.

Planar arrays

The next step is to stack the numbers on top of each other. The array can be imagined as an infinite plane of boxes of positive integers. This time, the positions in the array can be described by two coordinates: (a, b) is the value in the a-th row and b-th column (and a and b both start from 0). 1’s are still the default value, so for a valid array, all but finitely many entries are 1’s.

Bowers still uses commas to separate the entries of the array, and uses the separator (1) to move to the first entry on the next row. Thus, an array such as {3, 3, 3 (1) 3, 4, 5, 6} means the following structure in space:

3   3   3   1   1   1…
3   4   5   6   1   1…
1   1   1   1   1   1…

…

Most of the rules and definitions we gave above still work. The base and prime are now the entries at positions (0, 0) and (0, 1) respectively (i.e., on the first row). The pilot may not be on the first row anymore; it may be on the second row, third row, or beyond. If the pilot is the first entry on its row, the copilot doesn’t even exist.

There are two important things to understand about the definition of the pilot: “The first entry after the prime entry that is not 1.” First, it requires that all the positions of space have an ordering. The ordering is just the standard top-to-bottom left-to-right reading order: (w, x) > (y, z) if w > y, or if w = y and x > z. Second, the entries must be well-ordered; that is, each non-empty set of space positions must contain one that comes first in the ordering. If the entries were not well-ordered (for example, if the second coordinate were always non-positive instead of non-negative), we would not be able to ensure that the set of entries after a certain position contains an earliest entry (for example, the position (1, 0)), and thus we could not speak of the first non-1 entry after the prime. This well-ordering requirement must apply to all extensions of BEAF and it will force the different levels of array space into a hierarchy that is unavoidable, up to isomorphism.

The only rule that needs to change is the catastrophic rule. First, we need a minor tweak to the second part of the rule in case the copilot doesn’t exist:

• The copilot (if it exists) becomes the value of the original array, but with the prime decreased by 1.

The third part of the rule no longer works either:

• Besides the copilot, every entry before the pilot changes to b.

This is because, if the pilot is on the second row or beyond, an infinite number of entries on the first row must become b. This violates the requirement that only a finite number of entries can be non-1. Instead, Bowers decides that for all rows above the pilot, the first p entries change to b. The rest of the rows’ entries (which are all 1’s anyway) stay the same.

This means that if the pilot is at (y, z), a chunk of y*p + z prior entries take on the value b. Bowers calls the p entries on each row the prime block of the row. However, we can speak of the prime block of any position in array space as all of the entries that would be filled if the pilot or copilot was at that space (Bowers also calls these entries the “airplane”). Because the size of the prime block is a linear polynomial of p, the positions themselves are often expressed as polynomials, with position (y, z) described as y*X + z. The prime block itself can be represented by [y*X + z](p).

In fact, if the pilot is 2, and every other entry besides the base and prime is 1, the array evaluates into just a prime block and nothing else (besides trailing 1′s). This is how Bowers constructs many of his larger named numbers, which are usually written as {b, p (separator) 2} or as f(p) & b (where f is a function identifying a space by the size of its prime block, and & means “array of”).

Pandigital minutes

In 2015, I (re?) discovered an interesting calendar curiosity: a minute that uses all 10 digits exactly once when written down as a date.

To be precise, I was looking for times when the following 10 digits were all distinct:

• The last two digits of the year
• The two digits of the month number, from 01 (January) to 12 (December)
• The two digits of the day number, from 01 to 31
• The two digits of the hour in military time, from 00 to 23
• The two digits of the minute, from 00 to 59

It is easy to see that the same dates are pandigital minutes in every century. There are also the same number of pandigital minutes in each century, since the only date whose existence varies between centuries uses repeating digits (00/02/29) and cannot be part of a pandigital minute.

There have been no pandigital minutes so far this century. The digits 0, 1, and 2 must be used for the 10s places of the month, day, and hour in some order, meaning that the next occurrence cannot happen earlier the 2030s. In fact, as I write this, the next pandigital minute will be in exactly 14 years minus one day: June 27, 2034 at 6:59 PM, or 34/06/27 18:59.

The total number of pandigital minutes in each century is not too hard to calculate by hand. The trick is to keep track of all the values each digit can take and observe the one with the fewest possibilities. Let the date be 20y₁y₀/M₁M₀/d₁d₀ and the time be h₁h₀:m₁m₀. The digit M₁ must be in the range 0..1, and similarly h₁ in 0..5, d₁ in 0..3, and m₁ in 0..5. The other six digits can take on any value from 0 to 9 in general, but these choices can be restricted by the values of other digits.

Note: The following list contains indented sublists which do not display correctly on the Tumblr dashboard.

• Let M₁ = 0.
  • h₁ must be in 1..2.
  • Let h₁ = 1.
    • d₁ must be in 2..3.
    • Let d₁ = 2.
      • m₁ must be in 3..5.
      • For each choice of m₁, the remaining six digits can be freely assigned in any order.
      • This gives 6!*3 = 2160 pandigital minutes.
    • Otherwise, d₁ = 3.
      • The day can be only 30 or 31, so d₀ must be in 0..1.
      • But this is impossible because 0 and 1 have already been used.
  • Otherwise, h₁ = 2.
    • The maximum hour is 23, so h₀ must be in 0..3.
    • 0 and 2 have been used, so h₀ must be 1 or 3.
    • Let h₀ = 1.
      • d₁ must be 3.
      • But then d₀ is in 0..1.
      • This is impossible because 0 and 1 have already been used.
    • Otherwise, h₀ = 3.
      • d₁ must be 1.
      • m₁ must be in 4..5.
      • For each choice of m₁, the remaining five digits can be freely assigned in any order.
      • This gives 5!*2 = 240 pandigital minutes.
• Otherwise, M₁ = 1.
  • M₀ must be 0 or 2.
  • Let M₀ = 0.
    • h₁ must be 2.
    • h₀ must be in 0..3. The only possible value for h₀ is 3.
    • d₁ must also be in 0..3, but all those digits have been taken.
  • Otherwise, M₀ = 2.
    • h₁ must be 0.
    • d₁ must be 3.
    • But then d₀ is in 0..1.
    • This is impossible because 0 and 1 have already been used.

This brings us to a total of 2400 pandigital minutes in each century, from 34/06/27 18:59 to 98/07/26 15:43. They happen in every decade from the 30s to the 90s, and always in the months March through September. 2160 of them happen between 14:00 and 20:00 while the other 240 happen between 23:00 and 0:00.

Updated Bowers Exploding Array Function program

In preparation for my upcoming posts where I discuss the task of formally defining Bowers Exploding Array Function, I have just made an update to my 2016 Python program displaying the steps of evaluating an array. The current version is available on my GitHub here. It is currently written in Python 2, but I plan to rewrite it in Python 3 soon.

I plan to update it a lot more in the coming weeks. As of March 26, 2020, I have made the following changes:

• Updated notation for the planar arrays to match what Bowers writes (e.g. {3, 3, 3(1)2})
• Added a class “Bowersarray” so the arrays are treated as their own type of object in the code, with special functions for evaluation.
• Made a special function for the “canonization” step (removing 1′s from the end of rows and rows from the end of the array).
  

Here are some updates I have planned for the future:

• Support higher dimensional arrays and beyond.
• Allow the user to skip to the end of long, predictable sequences of steps.
• Add code to support numbers too large for all digits to be stored, so that the program can go a little longer before freezing when encountering a number too large.
  
• Allow the user to skip to the end of the evaluation of some intermediate array, even if they don’t understand the immensity of the resulting value, and have the program describe the next steps of the evaluation in terms of that value.
  

Bowers Exploding Array Function revisited

Today (November 27) is Jonathan Bowers’ 50th birthday! In 2016, I made a post about his legendary function for generating large numbers, Bowers Exploding Array Function (or BEAF for short). I wrote Python code to solve the first few steps of a 2D Bowers array, to show how the function was defined recursively. I promised updates to my code but I never delivered. However, within the next few days (or weeks, or months…) I think I will do just that.

First, I would like to present an overview of the different array structures of BEAF arrays. These are the most confusing part of BEAF; the recursive rule is quite easy to apply once the array structures are known.

Linear arrays: these are vectors of a finite number of positive integers, which can be indexed from 0 to some positive integer n.

Planar arrays: these are vectors of linear arrays, which can be of different lengths (or empty). Each entry can be indexed by a linear polynomial with non-negative coefficents, a*X + b.

Dimensional arrays: each entry can be indexed by a polynomial of arbitrary degree with non-negative coefficients, a*X^n + b*X^(n - 1) + … + k. Polynomials are ordered by comparing the most significant coefficients that are different.

Tetrational arrays: these are indexed by “hypernomials”; the exponents are allowed to be polynomials themselves (and, recursively, they are allowed to be earlier-constructed hypernomials). After the ordering of the exponents is established, one can compare hypernomials by size. Thus, by induction, all hypernomials can be ordered. These correspond to transfinite ordinals below epsilon_0. An example is 3*X^X^(X+2)+2*X^X^X+X^(X^3+X)+X^X+X^5+3*X+4.

Pentational arrays: the idea of hypernomials is extended by allowing the height of the tower of X’s to be a hypernomial. Using ^^ for tetration, we can define X^^X, X^^(X + 1), X^^X^2, X^^X^^X, …. Unfortunately, the rules for these expressions were never formalized and it is unknown what kind of expressions come between X^^X and X^^(X + 1), for example.

Hexational arrays and beyond: these are even less obvious to work with. When fully formalized (and I do believe it will happen some day), the expressions will be things like X^^^X, {X, X, X}, {X, X (1) 2}, tetrational arrays of X’s, pentational arrays of X’s, etc.

Legion arrays and beyond: Bowers develops a new kind of recursion for legion arrays – adding an argument to his function to denote the number of times an array is filled with X’s and used to make the space for a larger array. Unfortunately, there is no formal definition of these, despite toiling efforts of many parties on Googology Wiki. Jonathan Bowers used legion arrays to “define” his legendary number “meameamealokkapoowa oompa.”

Detailed list of attributions

When I first started this blog, I was 15 and homeschooled and had no sense of academic honesty. All I knew was that after reading books about math from big names such as John Conway and David Wells and thinking deeply about numbers, ideas came into my mind. These ideas were sometimes interesting enough that I thought it would do good to publish them, even though I didn’t always remember where the thoughts came from or how much I had to read before I thought of the rest myself.

As I went on and gained more of a sense of how others would view my blog, I began to notice that there were very glaring omissions of any attribution from most of my posts. I was writing as if all my ideas were coming straight from my brain, which was true for some but not all of my posts. When I transitioned straight from homeschool into college in 2017, the most common reaction people had when hearing about my mathematical interests was “Did you come up with this yourself or find it somewhere?” I often could not answer because I had spent almost no time paying attention to where my ideas came from. Sometimes I had actually forgotten where I learned an advanced mathematical topic because I had known about it for so long, almost 10 years. Once I memorized the proof of an interesting phenomenon I saw, the conclusion seemed self-evident. Until then, as far as I was aware what I was learning was simply a refinement of my everyday thought and none of my posts needed attributions because everything that I didn’t discover was assumed to be common mathematical knowledge.

Right before leaving for college I wrote the following disclaimer in my “About” page to try to demystify the origin of many of my ideas:

First, not everything I post here is one of my recent thoughts. Sometimes I decide to post an idea that I have had for up to ten years (I have 18). I don’t post every idea I have either; quite often, a post is so long that I started working on it only a few days after I finished the previous post.

As of this writing (August 17, 2017), I am not in college yet, though I will be going to New Mexico Tech in a few days, probably before anyone reads this.

Finally, I do not claim to be the first to discover any of the things I post here. (If I am though, it would be awesome.) Except where otherwise stated, the ideas in this blog were thought of by me, even though they sometimes build off of others’ ideas.

I still stand by everything I wrote. I wish I could have left it at that because it is not exactly fun for me to look up one of my “discoveries” and find that the exact same thing has been discovered by someone else in the past. But after years of hearing about the dangers of plagiarism and the importance of citing my sources, combined with the increasing popularity of my blog as I put it on my résumé to advertise my mathematical talent to potential employers, I think that it is time for a more comprehensive list of my sources of knowledge.

I’ll go through my posts chronologically, recalling as best I can my knowledge for each of them.

• Multiples of 37 and its sequel

To the best of my knowledge, I got the idea for this question by looking at a graph of the number of palindromes divisible by each prime, from Giovanni Resta’s site Numbers Aplenty, and noticed that significantly more than 1/37 of all palindromes were divisible by 37. I knew that this was because 37*3 = 111, but to my surprise I couldn’t find a single palindrome divisible by 37 but not 111 for a long time (well, a few hours or days). The first one I found was 808808838808808, which quickly led to 191191161191191. Eventually I convinced myself that 5009009009005 was the smallest, but I don’t remember how rigorous my proof was. At some time in the future I will do an exhaustive computer search, unless someone else does it first, and post the result.

• List of uniform honeycombs

This list is not only outdated and errored, as explained in the heading, but it contains very specific unexplained jargon. The post was written to parallel the research Jonathan Bowers was doing on higher-dimensional uniform polytopes and apply the same methods to search for 3D tesselations. The mysterious names given, such as “chon”, “octet”, and “squat” are nicknames invented by Jonathan Bowers to describe polytopes and tessellations, formed by contracting the full name down to its initials and adding vowels. These names are commonly called Bowers Style Acronyms and Dr. Richard Klitzing’s site here gives a long list of these acronyms with their meanings.

The few exceptions are nicknames invented by me when I stumbled across configurations that were, to my knowledge, new. These nicknames are Goccoticpidsith for “Great cubicuboctahedral tomocubic prismatic disquare tiling honeycomb,” Gotactictosquath for “Great tetrahedral cubic tomocubic tomosquare tiling honeycomb,” and Wavaccocotsoth (I don’t remember what that stood for because I already replaced the name with Wavicoca in one place). All these shapes have now been given better names by Jonathan Bowers, and the list updates are available on this hi.gher.space forum thread (my username is polychoronlover).

• Cheryl’s Birthday and my solution

Self-explanatory. I thought of the solution in my head and was surprised that everyone else thought it was so hard. Obviously I overestimated the average person’s intelligence.

The picture of the problem on paper is from the Guardian article, which in turn got it from Kenneth Kong on Facebook. I don’t know if the picture is copyrighted. (I will gladly remove it if I learn that it is.)

• How to calculate exact trig values, a post about radical expressions for roots of unity with an unsuspecting title, and its sequels [1], [2]

Ooh, here goes. The first in a series of posts where I did what is in my opinion my most impressive and mysteriously learned work. If only I had given them titles describing what I was actually doing.

I have made several more interesting findings in regards to this topic since making this post, described at the bottom of this section. So, there could be no better time to explain exactly where I learned such a specific way to calculate roots of unity in the first place.

In 2012, I was well aware from my math textbook that cos(45°) = sqrt(2)/2, cos(60°) = ½, and cos(30°) = sqrt(3)/2. I had also recently learned that cos(36°) = (1 + sqrt(5))/4 and cos(72°) = (-1 + sqrt(5))/4 from a statement on page 146 of the Penguin Dictionary of Curious and Interesting numbers by David Wells. (The book said that -2 cos(666°) was a good approximation for the golden ratio, but I verified the equation to be accurate to 14 decimals with my calculator. I was starting to suspect the values were actually equal. Later, I proved their equality myself by measuring various lengths in a pentagram.) When I learned the identities cos(a + b) = cos(a)*cos(b) - sin(a)*sin(b) and sin(a + b) = sin(a)*cos(b) + cos(a)*sin(b) (part of a normal high school trigonometry curriculum) I was able to find radical expressions for cosines of every multiple of 6°. On some website that I can’t remember, possibly this Wikipedia article, I found the identity cos(15°) = (sqrt(6) + sqrt(2))/4, which allowed me to find a radical expression for the cosine of every angle that was a multiple of 3°. Here are pictures of the paper where I recorded the results: i.imgur.com/wjjEIzP.jpg, i.imgur.com/xWNmrla.jpg.

Around the same time, I was also hearing about how Gauss had proved that the cosine of 17ths of a circle had expressions in square roots, and so did the 257ths and 65537ths of a circle. I was also starting to think less of these calculations in terms of cosines and sines and instead in terms of roots of unity (complex numbers of the form cos(2*pi/n) + i*sin(2*pi/n), in radians of course). Near the end of 2012, I heard of a method to calculate 17th roots of unity by starting with the sum of all 16 primitive roots and solving quadratic equations repeatedly to find the sum of fewer and fewer roots. I learned this method from the book The Book of Numbers by John Conway and Richard Guy. Seeing this derivation, I started to wonder if the cosine of every rational fraction of a circle was expressible using radicals.

I also heard (from the same book? Or maybe Wikipedia?) that the 7th and 9th roots of unity required cube roots when expressed in radicals, and that cos(2*pi/7), cos(4*pi/7), and cos(6*pi/7) were all roots of the same cubic equation with rational coefficients. Using a desk calculator, I found the three elementary symmetric polynomials of these three values, from which I found the coefficients of the cubic equation. Then I used the cubic formula to solve the equation. The resulting radical expression for cos(2*pi/7) matched the expression given on this Wikipedia page and indeed the expression now in my blog post, even though that expression was calculated using a different and more extensible method. I found an expression for cos(2*pi/9) the same way, and even found an expression for 2*cos(2*pi/13) (as x^1 + x^12, where x is a 13th root of unity) by solving a quadratic equation for the sum of six 13th root of unity and solving a cubic equation to break the sum into three pieces. I noticed the similarity between this method and Gauss’s method to calculate 17th roots of unity. In general, it seemed that to calculate the pth roots of unity, where p was prime, I needed to start with the sum of p - 1 pth roots of unity (which was always -1). Then I needed to repeatedly break the sum into q smaller sums, where q was a prime factor of p - 1, and find their values by solving a q-th degree polynomial. The coefficients, symmetric polynomials of the sums of roots of unity, could always be expressed in terms of previous sums whose values were already determined.

This method did not suffice to calculate the 11th roots of unity. I would have to solve a quintic equation, because 5 is a factor of 10, but I knew that there was no general quintic formula by the Abel-Ruffini theorem. I knew there was a radical expression for the 11th roots of unity because by then I had read somewhere that roots of unity could always be expressed in radicals. After thinking for a few weeks or months, in early 2013 I came up with a new way, based on the discrete Fourier transform of the roots. This method gave me a new way to find the 7th and 13th roots, and also allowed me to find the 11th roots by avoiding the problem of having to solve a quintic equation. This is the method I describe in my blog posts.

In January 2013, before I knew how to compute expressions for the 11th roots of unity, I found an expression for cos(2*pi/11) on a website called Literka. I was unable to compute the values myself for a long time even after I learned the method described in my posts, because the calculations were too intense (they involved taking a ten-term expression to the fifth power), although I made several close calls. In 2017 I learned enough shortcuts and perserverance skills to compute the values and promptly wrote a post about it, and I am happy to see that the values I found, with the -979, 275, and 220, match the values given on Literka.

But now all these advancements in my knowledge have been outdated by my recent research on the matter. Now I have:

• A Python program that finds root-of-unity expressions using the same method that I used,
• A “refinement” of this method that gave shorter expressions for the 11th roots of unity,
• Another Python program that finds expressions using the refined method,
• Lots more root-of-unity expressions, some very long, that are numerically verified to be accurate,
• A formula to approximate the average “length” of a root-of-unity expression before I calculate it.

The Python programs can, in theory and assuming arbitrary precision floating point values, calculate the radical expression for the p-th roots of unity where p is any prime. In reality, they tend to falter for most cases past 60th roots; the expressions become impressively long. The lengths vary a lot between consecutive primes, sometimes by orders of magnitude.

I can’t wait to make another post presenting all these things!

• Unusual number bases

The bases described in this post are base 37, centered nonary, double-digit base 120, base ϕ, definite length base 10, and a “base” based on the prime factors of a number.

Base 37 is a base that I haven’t seen anyone else but me take an interest in. It is quite an arbitrarily chosen base, and I chose it just because 37 is my favorite number.

I think I got the idea for centered nonary from a post about centered ternary on the XKCD forums (or was it the hi.gher.space forums?). I probably chose base 9 just because 9 was close to 10. Unfortunately, I can’t find the post.

I first heard of base 120 from this page of Wendy Krieger, a mathematician who uses it extensively on her website. I discovered her website from my interest in higher-dimensional geometry. She calls the base “twelfty.” Much of what I posted about base 120 came from her website, with some notation changed, most notably to use commas to group digits into pairs of super-digits.

Base ϕ is rather well-known. It is mentioned on Wikipedia, Ron Knott’s site, and this hi.gher.space post, for example. I first heard of it when I was playing with the cellular automata simulator Golly written by Andrew Trevorrow and Tomas Rokicki. There was a pattern called “alien counter” and the description said that Adam P. Goucher (also known as Calcyman, the creator of apgsearch and Catagolue) thought the simulation was counting in base ϕ but no one was really sure. I didn’t actually learn how base ϕ worked for several more years.

I haven’t heard of definite-length bases anywhere else, although I’m sure someone else has come up with them. I first thought of the idea when I was young and wanted to use base 26 to assign each word in English a unique number. I numbered A-Z as 1-26, then realized that base 26 would require them to be 0-25. But to my surprise, my numbering scheme still assigned each string of letters to a unique positive integer. Definite-length base n, made from powers of n and the digits 1-n rather than 0-(n - 1), was born.

Even though I independently discovered the prime-factor “base” representation of numbers, the same system appears in OEIS entry A054841 and was called “Exponential Prime Power Representation” by Walter Nissen. The idea of representing a number in terms of its prime factors is very old. In fact, Gödel encoding is a way to map strings of characters to integers in much the same way as exponential prime power representation. Each character position gets assigned a unique prime number and each character gets assigned a unique exponent of that number. Unlike definite-length bases described above, Gödel encoding works for a language with an infinite set of characters.

• The Starter Constant Mystery saga: [0], [1], [2], [3]

These are the posts that I feel the most personal connection to. They involve my findings about the following triangle of numbers:

1
0 1
0 1 2
0 1 6 6
0 1 14 36 24
0 1 30 150 240 120
...

These numbers are generated from the nth powers x^n in a way that I now know is called the inverse binomial transform. My posts call them the starter constants. The OEIS calls them numbers of the form k!*Stirling2(n, k).

These numbers have been studied before. They appear in many entries on the OEIS, under many different descriptions: [0], [1], [2], [3], [4]

In my posts I prove two main things about these numbers: that they can be generated by an inductive formula similar to Pascal’s triangle (idea 1), and that they relate to the number of strings of given length using every type of character from a given set (idea 2). All the proofs are my own, and I felt greatly accomplished when I made them. The same proofs may have been found by other people, but they are the pride of my mathematical life right now. The major things I found from outside sources are attributed in the posts. Notably, idea 2 described above came from the description of OEIS post [4]. I was amazed when I read that description, when I had only known the starter constants as relating to powers. Rather than looking at the post to see a proof, I felt challenged to prove the connection myself, which I did and detailed in my first post.

• When does n have the same digits as 2n?

In this post I describe an algorithm for finding numbers n that are anagrams of their doubles, 2*n, in base 10. The algorithm was developed by me around May 2015. I was inspired to do it after finding, and skimming, but not reading, this post: https://blog.plover.com/math/dd.html, which I found from the OEIS entry for the sequence: A023086. In fact, my own technique of finding cycles of digits is very similar to what the post describes, and the post goes into more detail on the constraints of the digits.

As you probably can tell, I had a tendency when I was younger to find interesting mathematical facts online, attempt to prove them myself rather than looking at someone else’s proof, and post them to my blog without attribution if successful.

• Unnamed post about the coordination numbers of hyperbolic tilings and its sequel

In these posts, I discuss regular hyperbolic order-3 p-gonal tilings and the sequences arising when counting the number of polygons a given number of steps from a center polygon.

This sequence is called the tiling’s coordination sequence, even though I didn’t use that term until nearly the end of the second post. I was inspired to study coordination sequences after seeing a post on Adam P. Goucher’s blog that said that the coordination sequence for the heptagonal tiling was 7 times alternate Fibonacci numbers. As usual, I skimmed Goucher’s post without trying to find a proof of this phenomenon and proved it myself in my post.

There is also the issue of how I created the images for my posts. The images were created using Paint.NET and the font used for the layer numbers was Frente H1, which I downloaded from a site called Font Squirrel. If I remember correctly, Times New Roman was used for the colored numbers in the first post and Arial was used for the colored numbers in the second post.

The post contains two types of images of tilings. One type gives the entire tiling in red and the other gives each layer in a successive rainbow color. For the first type, I used these public domain images [1] [2] by Tom Ruen and Anton Sherwood, which were widely used on Wikipedia until they were replaced by SVGs. The second type of image was created by hand, although I sometimes used the two images given above to trace the edges on them. It also deserves mentioning that the rainbow palette that I used to color successive layers in my images was inspired by the image in Goucher’s post.

Here is a link to the OEIS entry for the coordination sequence of the order-3 heptagonal tiling (listed by them as the coordination sequence for the vertices of the dual tiling): A001354.

• Last digits of powers and its sequel

In these posts, I prove various theorems about patterns in the last digits of the decimal expansions of perfect powers. As far as I can remember, I thought up the proofs myself, using nothing more than algebraic manipulation and Fermat’s little theorem. Although I played with powers a lot as a kid, all of the results I derive are well-known and I only use basic methods from number theory to prove them. For example, see this brilliant.org post about last digits of powers.

The first post is about how x^n = x^(n + 4) (mod 10) when n ≥ 1 and the second is about how x^n = x^(n + 20) (mod 100) when n ≥ 2. I was going to make more posts about the equivalences of powers mod 1000, higher powers of 10, and eventually mod other bases, but I lost interest.

The “wonderful” theorem I mention in the second post says that if numbers a and b are coprime, then pairs of values (x mod a, x mod b) will only be the same for two different values of x when those two values are separated by a multiple of a*b. This is equivalent to saying that when a and b are coprime, a*b = LCM(a,b). This is simply another basic result of number theory.

• Irrational primes!

This post was an April Fool’s joke announcing a “mathematical breakthrough”: the discovery of irrational numbers that are prime! Obviously, this is absurd as all prime numbers are integers by definition. At the same time, I also intended to present an actual mathematical curiosity I had rediscovered: a set of real numbers containing all primes, no other integers, and infinitely many (probably irrational) non-integers.

The idea is that Wilson’s theorem, a common test for prime numbers named after John Wilson, says that an integer x is prime if and only if ((x - 1)! + 1)/x is an integer. Using the Gamma function, factorials can be defined for every positive real number, allowing for integer values of ((x - 1)! + 1)/x to exist for non-integer values of x. For the sake of a joke I called these numbers “irrational” despite not knowing that for sure.

In fact, the curiosity of non-integer solutions of Wilson’s congruence has been noticed by several people before, such as in this college math test from 1999.

• Lychrel numbers and its sequel

In these posts, I discuss Lychrel numbers, numbers that never reach a palindrome when iterating the process of reversing the digits and adding to the original number: why we think they exist, why we haven’t proved they exist in base 10 although we have proved they exist in base 2, and a heuristic argument suggesting there are infinitely many Lychrel numbers in every base. The first post is the first one that I can remember where I only talk about things other people have discovered instead of presenting my own findings, even if they are rediscoveries or trivial corollaries of others’ discoveries. The binary Lychrel number mentioned in the second post I found on Wikipedia. The only insights that were my own were the heuristic argument and the connection to cellular automata.

• Unnamed post with a proof about geometry

In this post, I prove that removing four non-adjacent vertices of a cube results in the vertices of a regular tetrahedron. This fact may be useful in chemistry as an aid to drawing molecules with tetrahedral structure, such as methane. In fact, as I mention in the post, I got the idea after watching a chemistry video on Khan Academy with a proof of the same fact. I think the video was this one: https://www.khanacademy.org/science/organic-chemistry/gen-chem-review/hybrid-orbitals-jay/v/tetrahedral-bond-angle-proof.

Even though I was quite proud of it at the time, I now think that my proof was trivial and was presented in an overly long fashion. I don’t actually know why I needed to mention the coordinates of a cube (let alone one rotated 45 degrees from the standard coordinate-parallel orientation!). I should have just said that choosing alternate vertices produced four vertices such that every pair lay on opposite ends of a square, and thus the distances between all pairs of vertices was equal, and it followed that the vertices produced four equilateral triangles which were the faces of a regular tetrahedron.

• Jonathan Bowers’ birthday, plus a program

This post discusses more of the work of Jonathan Bowers, the same guy whose shape names I used back in my “List of Uniform Honeycombs” post. In particular, it talks about Bowers Exploding Array Function (BEAF for short, also called Array Notation), a notation that represents enormous numbers as multidimensional arrays (and beyond) of positive integers. This post may be the most interesting to readers of the blog because BEAF has gained a cult following around the Internet, and is an inspiration for many modern large number notations found on the Googology Wiki, such as Bird’s array notation, Hyp Cos’s Strong array notation, and Sbiis Saibian’s Hyper-Extended Cascading-E Notation.

In my post, I present a Python program that I wrote to “evaluate” Bowers arrays into large numbers, one step at a time. In reality, the program usually either ends up repeatedly decrementing a number larger than one million, but still small enough to be expressible directly as a binary integer inside the computer’s memory, until the maximum recursion depth is reached, or otherwise ends up crashing trying to evaluate an expression with such a number in the exponent. This was deliberate; as the post states, the results of evaluating most Bowers arrays are numbers too large to fit in the universe! Even an array as small as {3, 3, 3} evaluates to a number equal to 3^3^3…^3^3, with 7,625,597,484,987 threes. This number couldn’t fit in the observable universe if written out in full, and its number of digits couldn’t fit, and the number of digits in its number of digits couldn’t fit… in fact, you could take the number of digits over seven trillion times and the resulting number would still be too large to write out in full! I mostly wrote the program to showcase the fact that BEAF is a recursive function, and thus computable. Even though BEAF produces numbers so large they have no uses outside of pure mathematics, the arrays can be evaluated step-by-step with a computer. In fact, a computer with infinite memory and time could evaluate any Bowers array all the way down to the final mind-boggling result!

Unfortunately, I abandoned work on the program soon and never got beyond implementing the rules for 2-dimensional arrays. However, I may update it when Bowers’ 50th birthday arrives later this November.

I first learned of Bowers Exploding Array Function in 2011 after discovering Bowers’ work with polytopes. I learned about linear arrays through Bowers’s own web page describing his notation, and I learned about multidimensional arrays from a post on qntm.org and its sequel on everything2.com. But Bowers’ notation goes way beyond multidimensional arrays, into super-dimensional arrays (don’t ask) and tetrational arrays. I slowly learned how these worked through immersion and from Googology Wiki; it became easier after I learned that each level of tetrational space corresponds to an ordinal number below ε₀. Bowers’ notation goes even further, into pentational arrays, hexational arrays and beyond. In 2014, I learned that no one understood how these worked, besides possibly Bowers; his webpage never accurately defined them. However, much work has been done on the Googology Wiki about proposing various formal definitions for the various array structures beyond tetrational arrays, a topic that relates to the wild world of ordinals beyond ε₀. I will probably discuss these formalizations in a future post some day. In fact, earlier in 2019 Bowers announced that he was planning to make a video series about higher level array structures, so we can still look forward to an official definition of BEAF.

• Unnamed post about 2D lattices of points

This post is about 2D lattices of points generated by a pair of basis vectors, where the basis vectors have integer coordinates. In it, I proved that the fraction of all points in Z^2 that are in the lattice is 1/|D|, where D is the determinant of the matrix whose columns are the basis vectors. In the proof, I use the well-known fact from vector calculus that the area of a parallelogram in 3-space is equal to the absolute value of the cross product of its edge vectors (although I mistakenly leave out the absolute value sign). I also write an overly long alternate proof that every point in Z^2 is in the lattice if and only if |D| = 1. Interestingly, I had never taken linear algebra when I made this post (I only knew about determinants and matrix inverses through Khan Academy videos), and I ended up rediscovering by myself the fact that the determinant is a scaling factor of the transformation.

In this post, I use an image that I created with the Khan Academy Processing.js programming tool: https://www.khanacademy.org/computer-programming/new/pjs. The image of the matrix equation was made using Microsoft’s Math Input Panel for Windows 8 (however, most equations in later posts were made using latex2png.com).

• Higher-dimensional Pascal’s Triangle and its sequel

In these posts, I consider how the trinomial coefficients, quadrinomial coefficients, and beyond can be arranged into higher-dimensional generalizations of Pascal’s triangle, which are called Pascal’s simplices (plural of simplex). I investigate several properties of the simplices, including:

• How the numbers can be derived from counting combinations of objects into multiple groups
• How each layer of a simplex can be obtained by adding numbers in the layer above, similar to the rows of Pascal’s triangle
• How the entries on each row of the n-dimensional simplex sum to a power of n
• How each entry in the (n + 1)st row of a simplex counts the number of vertices of a uniform n-polytope with simplectic symmetry
• How the entries on the interior of each layer sum to one of the starter constants!

I rediscovered all of these properties by myself because I didn’t want to be disappointed if I learned that Pascal’s simplices had already been investigated. As it turns out, this was in fact the case. Almost every property I mention is described in two Wikipedia articles, Pascal’s pyramid and Pascal’s simplex. The article “Pascal’s pyramid” has references to the object going back to the 1970s. The earliest known publication of Pascal’s pyramid seems to be this paper by John and Larry Staib, who appear to be father and son. Even they believe, like I did, that the triangle is so elegant and easy to construct that it must have been discovered before.

The posts mention higher-dimensional simplices, hypercubic tessellations, simplectic tessellations, and partition numbers. I learned about all these topics on Wikipedia (except for partition numbers, which I learned about in The Book of Numbers by John Conway and Richard Guy, rather than being rediscovered by me. The “advanced polytope terminology” in the second post, such as “Biexipetirhombated dodecadakon,” is Jonathan Bowers’ nomenclature for kaleidoscopical convex uniform polytopes, described on these pages of Bowers and Richard Klitzing: [0], [1]. The textual representation of a Coxeter-Dynkin diagram (o3o3x3o3x3o3o3o3x3x3o) was also developed by Klitzing.

I created some of the illustrations in my post using the Khan Academy Processing.js programming tool and used paint.net to screenshotted and cropped (and in one case modify) them. The code to generate these illustrations is available here: [0], [1], [2]. The other images were created by cropping screenshots of Notepad.

• Cyclotomic polynomials and repeating decimals

This post came out of a lifelong interest in using repeating decimals to represent rational numbers. I was interested in this subject ever since my dad showed me how the decimal expansions of different multiples of 1/7 consisted of the same cyclic permutation of 6 digits.

In the post, I mention that in order for an integer p to be the period length of the base-b expansion of 1/a, a must divide b^p - 1. I made this connection myself as a child by studying the repeating decimals of 1/7. I also found out that if a is prime and not a factor of b, the period p must be a factor of a - 1 by considering the possible different cycles that can occur when taking different multiples of 1/a. All of these facts are well-known, and are mentioned on the Wikipedia article for repeating decimals.

I also mention that the primes a with period p are all factors of c_b(p), the bth cyclotomic polynomial evaluated at x = p. I learned this after investigating this page from Studio Kamada, which gives the known prime factors of c_b(10) for every value of b up to 300000 (!). I discovered the page when studying the factorization of repunits (for which there is a similar page on the same site) and trying to isolate the factors of (10^p - 1)/9 that had period length p rather than some proper divisor of p.

In the post, I mention Artin’s Constant and the related conjecture involving full-reptend primes in base b. I learned about these topics from The Book of Numbers by Conway and Guy. The images were created using latex2png.com.

LCM of binomial coefficients

A few months ago, when I was doodling in math class, I stumbled across a surprising formula for the least common multiple (LCM) of all terms in a row of Pascal’s triangle.

I wasn’t even looking for such a formula. I was just experimenting with numbers of the form LCM(1, 2, …, n). The formula for the LCM of all terms on the nth row of Pascal’s triangle (i.e. the one that starts 1, n…) is: LCM(1, 2, …, n + 1)/(n + 1).

Researching online, I found that this identity was proven in 2009 by Bakir Fahri (see [1]). The OEIS entry (A002944) links the proof, which is based on finding the p-adic valuations (exponent on the prime p in the prime factorization) of the left and right side of the identity for all primes p. However, the proof I found was quite different and I am not sure whether it has been found before.

First consider the harmonic triangle. The harmonic triangle, developed by Gottfried Leibniz, is like the reciprocal of Pascal’s triangle, except each term on the nth row is divided by n + 1:

Because the formula for the rth term on the nth row of Pascal’s triangle is nCr = n!/(r!(n - r)!), the rth term on the nth row of the harmonic triangle has the formula 1/((n + 1)(nCr)) = r!(n - r)!/(n + 1)!. Let us denote this value by F(n, r).

We know that each term in Pascal’s triangle is the sum of the two terms above it: nCr + nC(r + 1) = (n + 1)C(r + 1). Similarly, the following relation holds for the terms in the harmonic triangle: F(n, r) + F(n, r + 1) = (r!(n - r)! + (r + 1)!(n - r - 1)!)/(n + 1)! = r!(n - r - 1)!(n + 1)/(n + 1)! = r!(n - r - 1)!/n! = F(n - 1, r).

In other words, each term in the harmonic triangle is the sum of the two terms below it.

Now, consider the nth row for a particular value of n. To make the reasoning easier to understand, I will choose n = 7, but the logic is the same for all rows.

1/8, 1/56, 1/168, 1/280, 1/280, 1/168, 1/56, 1/8

What is the smallest value that we can multiply by all these terms to produce integers? Note that the reciprocals of the terms are just (n + 1) nCr. Thus, the question is the same as asking for the least common multiple of (n + 1) nCr for r from 0 to n. By factoring out n + 1, we see that this value is equal to m = (n + 1) LCM(nC0, nC1, …, nCn). In our example, m = 840. Let’s try multiplying every term by m:

105, 15, 5, 3, 3, 5, 15, 105

Because each term is the sum of the two below it, we can build 840 times the entire first eight rows of the triangle by adding from below and all the terms will be integers:

In general, if all the terms in a row are integers, all terms in the rows above will also be integers. Furthermore, because we multiplied by the least common multiple of the denominators, the numbers in the bottom row have 1 as their greatest common factor.

In fact, because the third of any three numbers in an upward pointing triangle can be determined from the other two, the left and right diagonal of the triangle also have 1 as their greatest common factor. If they didn’t and had some common factor of f > 1, all numbers in the first n + 1 rows of the triangle would have the same factor f. This is because the entire triangle can be constructed by subtracting adjacent terms in the left diagonal to form the next diagonal over, and then repeating for each subsequent diagonal. Then a smaller common multiple of all the numbers in the triangle would be m/f. But m is the least common multiple by definition, which is a contradiction.

In fact, the numbers down either outer diagonal are m, m/2, m/3, …, m/(n + 1). In our example, these are 840, 420, 280, 210, 168, 140, 120, 105. In trying to identify m, we see that it must be divisible by 1, 2, …, n + 1. Furthermore, if m were not the least common multiple of 1 through n + 1, then some factor m/k would be. Then m, m/2, …, m/(n + 1) would all be divisible by k, but we have just established that their greatest common divisor is 1. In conclusion, we must have m = (n + 1) LCM(nC0, nC1, …, nCn) = LCM(1, 2, …, n + 1). Therefore, LCM(nC0, nC1, …, nCn) = LCM(1, 2, …, n + 1)/(n + 1). QED.

An interesting consequence of this theorem is that the LCM of one row of Pascal’s triangle is usually less than the LCM of the previous row. This is because LCM(1, 2, …, k) = LCM(1, 2, …, k - 1) whenever k is not a prime power. However, the increases in the value of LCM(1, 2, …, k)/k that occur with increasing rarity, whenever k is a prime power, make up for the slight decreases caused by increasing k whenever k is not a prime power, and the sequence increases overall.

Here are the first few terms of the sequence, from n = 0 to n = 21:

• 1, 1, 2, 3, 12, 10, 60, 105, 280, 252, 2520, 2310, 27720, 25740, 24024, 45045, 720720, 680680, 12252240, 11639628, 11085360, 10581480

And here are the quotients when the terms in each row of Pascal’s triangle are divided into the corresponding multiple:

• 1
• 1, 1
• 2, 1, 2
• 3, 1, 1, 3
• 12, 3, 2, 3, 12
• 10, 2, 1, 1, 2, 10
• 60, 10, 4, 3, 4, 10, 60
• 105, 15, 5, 3, 3, 5, 15, 105
• 280, 35, 10, 5, 4, 5, 10, 35, 280
• 252, 28, 7, 3, 2, 2, 3, 7, 28, 252
• 2520, 252, 56, 21, 12, 10, 12, 21, 56, 252, 2520
• 2310, 210, 42, 14, 7, 5, 5, 7, 14, 42, 210, 2310
• 27720, 2310, 420, 126, 56, 35, 30, 35, 56, 126, 420, 2310, 27720
• 25740, 1980, 330, 90, 36, 20, 15, 15, 20, 36, 90, 330, 1980, 25740
• 24024, 1716, 264, 66, 24, 12, 8, 7, 8, 12, 24, 66, 264, 1716, 24024
• 45045, 3003, 429, 99, 33, 15, 9, 7, 7, 9, 15, 33, 99, 429, 3003, 45045
• 720720, 45045, 6006, 1287, 396, 165, 90, 63, 56, 63, 90, 165, 396, 1287, 6006, 45045, 720720
• 680680, 40040, 5005, 1001, 286, 110, 55, 35, 28, 28, 35, 55, 110, 286, 1001, 5005, 40040, 680680
• 12252240, 680680, 80080, 15015, 4004, 1430, 660, 385, 280, 252, 280, 385, 660, 1430, 4004, 15015, 80080, 680680, 12252240
• 11639628, 612612, 68068, 12012, 3003, 1001, 429, 231, 154, 126, 126, 154, 231, 429, 1001, 3003, 12012, 68068, 612612, 11639628
• 11085360, 554268, 58344, 9724, 2288, 715, 286, 143, 88, 66, 60, 66, 88, 143, 286, 715, 2288, 9724, 58344, 554268, 11085360
• 10581480, 503880, 50388, 7956, 1768, 520, 195, 91, 52, 36, 30, 30, 36, 52, 91, 195, 520, 1768, 7956, 50388, 503880, 10581480

References

1. Bakir Farhi, An identity involving the least common multiple of binomial coefficients and its application, arXiv:0906.2295
2. A002944 - Online Encyclopedia of Integer Sequences

Updates to blog layout and math expressions

I just made some updates to my blog CSS to ensure that the HTML subscripts and superscripts are formatted properly. This is one of a number of steps I plan to take to ensure that my inline math expressions are easily readable.

I constantly strive to integrate beautifully formatted expressions into my page and in my last post I took a big step in this direction by embedding my formulae as images created from LaTeX expressions, which I made using the site latex2png.com. Sometime in the future, I will be using a tool such as MathJax to embed this type of expression into posts more neatly. In the nearer future, however, I plan to create CSS for my own custom “math class”, mimicking LaTeX, to enclose simpler expressions while still using latex2png for multi-line or non-linear ones, such as those including fractions or sigma notation. By the time you read this, I may have already edited my last post to use this class for all the textual formulae. If will be used to prettify inline expressions ℒ(i)·k̂ + e^tħi_s.

(If the words “LaTeX” and “like this” above appear large and in a fancy Roman font, it means that the new math class is now up and working properly.

It should also be noted that I have had a less than pleasant experience trying to get my documents formatted properly on Tumblr. Considering Tumblr’s default settings are to not show subscripts and superscripts in HTML, this is not very surprising. As an example, there is no way to put an image inline without directly editing the code of a post, and switching back and forth between different text editors often butchers the code of a post, removing blockquotes and botching italicized characters that are next to non-italicized ones. For this reason, I may eventually abandon Tumblr entirely and move my blog to Wordpress or, more ideally, my own site.

Cyclotomic polynomials and repeating decimals

Ever since I was a small child I have been fascinated with repeating decimals, decimal expansions that end up repeating a sequence of digits indefinitely. For example:

, which repeats the four digits 2970 again and again. In this particular example, the digit string 2970 is called the reptend, and the decimal is said to have period length 4. Over the years, my intent shifted specifically to studying decimals between 0 and 1 whose digits started repeating right after the decimal point, and I started seeing the repeating digits more as their own separate entity with addition and multiplication rules that just happened to be isomorphic to the addition and multiplication of repeating decimals. In this post, I will attempt to explain some of the many discoveries and surprises I found when studying these numbers.

Rationality of Repeating Decimals

One of the first obvious things to notice about repeating decimals is that the numbers they describe are always rational. The proof of this fact is simple, and many readers have probably already seen it. It amounts to showing that each repeating decimal number x can be expressed as an infinite geometric series (1):

In this series, x₀ is the part of the decimal before the repeating digits, r is the reptend as an integer, p is the period length, and s is the number of digits after the decimal point before the reptend. Summing the series reveals that

. Because x₀ is rational (as it is a terminating decimal) and the numerator and denominator of the fraction are integers, it follows that the sum of the two is also rational. Based on the fact that the decimal expansion for x₀ terminates after s digits, we can rewrite this expression as (2)

In this expression, t is the integer formed from digits of the decimal before the beginning of the reptend. The numerator and denominator of each fraction are integers, so we have just expressed x as the sum of two rational numbers, which it itself a rational number. This shows that every repeating decimal is a rational number.

It is slightly harder to prove that every rational number is a repeating decimal. Let x be rational. It follows that

for some integers a and b. Now, consider the sequence of reals s defined by (3):

Let n be any positive integer. As s₁ is rational and s_n consists of an integer subtracted from an integer multiple of s_{n - 1}, it follows by induction that s_n is rational. Similarly, it follows by induction that b·s_n is an integer, and because each s_n is calculated by taking the fractional part of a real number, it follows that 0 ≤ s_n < 1.

Thus s_n must be equal to

for some integer a_n between 0 and b - 1. Since each term is calculated solely from the previous term, then if s_n = s_{n + p} for some positive integer p, it follows that s_k = s_{k + p} for all integers k greater than n. Because s_n can take on only a finite number of values, a duplicate term in the sequence like this must happen eventually. This reasoning suffices to show that the terms in s eventually enter into a cycle.

Now, it can be shown inductively that

for n > 1. Because the formula for the nth digit in the decimal expansion of x is

, the decimal expansion of x must also enter into a cycle. Thus, all rational numbers have repeating decimal expansions.

Unit fractions

Now, consider the decimal expansion of a number of the form

, where a is an integer. For this value of x,

, and in all following terms of the sequence, the numerator is made by multiplying the previous numerator by 10 and taking the result mod 2a. Thus, all terms after s₁ have even numerators, so s₁ does not appear again in the sequence and the first digit in the decimal expansion of x is not part of the reptend. The same logic holds for numbers of the form

, so it can be deduced that all unit fractions whose denominator is a multiple of 2 or 5 have non-repeating digits at the beginning of their repeating decimal expansions.

What about when the denominator is not a multiple of 2 or 5? As it turns out, in this case the reptend will always repeat from the beginning, regardless of the value of the numerator. However, to simplify our calculations, we will only prove this for unit fractions.

To see this, consider equation (2). If our fraction is

, where a is not divisible by 2 or 5, then the right side of equation (2) can be rewritten as a single fraction with integers as its numerator and denominator:

. Rearranging, we get

. Because a, not being divisible by 2 or 5, has no factors in common with 10^s, then (10^p - 1)t + r must be divisible by 10^s, and thus 10^s can be factored out of both the numerator and denominator. Therefore, x can be rewritten as

, where r’ is an integer less than 10^p - 1. This suffices to show that the reptend in the decimal expansion of x starts at the beginning.

An interesting consequence of this observation is that 10^p - 1 is a multiple of a. Furthermore, we see that the quotient of these two values, r’, is just the reptend of x. This gives a theorem:

Theorem 1a

For every a not divisible by 2 or 5, there exists a value p, equal to the length of the reptend of 1/a, such that a divides 10^p - 1. The value (10^p - 1)/a is the reptend of 1/a.

Because 10^p - 1 divides 10^kp - 1 for all k > 1, r divides 10^kp - 1 as well. But r does not divide 10ⁿ - 1 for any n not divisible by p. If it did, formula (2) with s = t = 0 could be used to show that 1/a repeated after n digits, contradicting our assumption that p did not divide n.

Theorem 1b

For every a not divisible by 2 or 5, there exists a value p, equal to the length of the reptend of 1/a, such that for every integer n, a divides 10ⁿ - 1 if and only if p divides n.

As an example, take a = 31:

In this case, the bar over the digits mean that the digits repeat; that is, they make up the reptend. The period length p is 15, and indeed, we see that

. We also can check that 9, 99, 999, 9999… 99999999999999 are not divisible by 31.

Generalization to arbitrary bases

All the logic so far in this post can be generalized straightforwardly from base 10 to any other (integer) base greater than 1; each repeating base-b expansion of digits corresponds to a rational number and vice versa. Unit fractions whose denominators a are coprime to b (not divisible by any prime factor of b; such as indivisibility by 2 or 5 in base 10) are precisely those unit fractions whose base-b expansions have no digits before the reptend begins, and it is those values of a that divide b^p - 1 for some value of p, and only multiples of that value, which is what Theorems 1a and 1b have already stated for b = 10:

Theorem 2

For every positive integer a coprime to a base b > 2, there exists a value p, equal to the length of the reptend in the base-b expansion of 1/a, such that for every integer n, a divides bⁿ - 1 if and only if p divides n. The value (b^p - 1)/a is the reptend of 1/a.

In the interest of abstraction, the rest of this post will generally speak of base b instead of base 10.

How to find the value of p?

It is an interesting problem to find the value of p corresponding to given a and b. The least trivial case happens when a is prime. From Fermat’s little theorem, it is known that when a is prime and coprime to b, a divides b^{a - 1} - 1. Therefore, p must divide a - 1.

When p = a - 1 for some prime a, a is called a long prime or full reptend prime to base b. The fraction of primes which are long primes to a base is not known, but for most bases it is thought to be equal to Artin’s constant, about 0.373956…. When b is a perfect square, no odd prime can be a long prime to base b because for any odd prime a = 2q + 1, b^q - 1 = (√b)^{a - 1} - 1 is divisible by a. In general, there is no way to see what the period length of 1/a will be without checking it.

Given p and b, how do we find a?

Continuing to talk of prime values of a, how would we find all the primes whose reciprocals had a given period length in a given base? Or, given p and b, how do we find a?

For p to be the period length, it is necessary that a divide b^p - 1. The simplest way to find these values is to check every prime factor of b^p - 1 as a possible value of a. We can check these contenders by defining a sequence t_n (4):

The resulting values are just a·s_{n + 1}, where s_n is defined as in (3) except the inductive step involves multiplication by b instead of 10. The index of the second occurrence of 1 is the length of the repeat, and we need to check that this index value is p.

Let’s use this method for an example where p = 8 and b = 31. We have b^p - 1 = 852891037440, which is 2⁸·3·5·13·37·409·1129. Checking each of these prime factors x, we get the sequences:

2: 1, 1, 1, 1, 1, 1, 1, 1, 1…

3: 1, 1, 1, 1, 1, 1, 1, 1, 1…

5: 1, 1, 1, 1, 1, 1, 1, 1, 1…

13: 1, 5, 12, 8, 1, 5, 12, 8, 1…

37: 1, 31, 36, 6, 1, 31, 36, 6, 1…

409: 1, 31, 143, 343, 408, 378, 266, 66, 1…

1129: 1, 31, 961, 437, 1128, 1098, 68, 692, 1…

We need to check the location of the first 1 in each sequence after the initial term. If the initial term is considered the 0th, only two numbers’ sequences have the second 1 at the 8th place, which is required for p to be 8. Only x = 409 and x = 1129 satisfy this property, so the only possible values of a are 409 and 1129.

Note that because the terms of t are formed by repeatedly multiplying by b mod x,

. Since x divides b^p - 1, t_p = 1 for each sequence t, but this is not always the first occurrence of 1 after t₀. Equivalently, the base-p expansion of 1/x always repeats after p digits, but it is not always the minimum repeat length.

We see many problems with this method. For one thing, it involves factoring a number whose length is proportional to the value of p. For another, we already showed that p must divide a - 1. This eliminates all values of x except 409 and 1129.

Let y be any factor of p other than p. As all primes whose reciprocals have period length y are factors of b^y - 1, all primes whose reciprocals have period length p are factors of the quotient (b^p - 1)/(b^y - 1). If we could divide b^p - 1 by the product of b^y - 1 for all factors y of p, the resulting number would still have all possible values of a in its prime factors.

Cyclotomic polynomials

Define a sequence of polynomials as follows (5):

The resulting polynomials will be:

We will now prove that each term of this sequence is a polynomial. Note that the zeroes of xⁿ - 1 are the nth roots of unity, n complex numbers all having 1 as their nth power. Based on the formula for these numbers as the exponential function of imaginary numbers, we can define a set of binomials B_n the product of whose members equals xⁿ - 1:

We can define another set of binomials S_n as follows:

We claim that: (6)

This is trivially true for n = 1. Now assume that it is true for all n < k. In particular, it holds true for all factors of k less than k, which we will call f₁, f₂…. The expression for each member p(x) of the set B_k contains a fraction k’/k (in the exponent of the constant term) where k’ is a non-negative integer less than k. If GCD(k’, k) ≠ 1, then this fraction can be reduced to f_z’/f_z, where f_z is some factor of k less than k. As the fraction has been reduced to lowest terms, GCD(f_z’, f_z) = 1. Thus, p(x) is a member of S_fz. In this way, every member of B_k where GCD(k’, k) ≠ 1 belongs to a unique set S_fz for some factor f_z of k. Also, every member of one of the aforementioned sets also belongs to B_k, as can be seen by multiplying the numerator and denominator of the member’s fraction by the factor required to make the denominator k. Thus, there is a one-to-one correspondence between B_k and the other sets.

The remaining members of B_k are those where GCD(k’, k) = 1, and their product is equal to

. By our assumption of (6), the denominator is equal to the product of c_f(x) for each given value of f. Thus, the product of the members of S_k can be written:

. By definition, this is equal to c_k(x). We have just verified (6) for n = k. By induction, (6) holds for all positive integer values of n. Furthermore, (6) defines c_n(x) as a polynomial while (5) shows, via polynomial long division, that the coefficients of c_n(x) are integers.

We have just proved that each c_n(x) is a polynomial with integer coefficients. Because the zeroes of this polynomial are roots of unity, which when plotted on the complex plane appear as points on the unit circle, the polynomials c_n(x) are known as cyclotomic polynomials.

Cyclotomic polynomials and repeating decimals

Let’s say we find the value of c_p(x) at the point x = b. If b is an integer, then c_p(b) is also an integer. Let P be the multiset of all prime factors of b^p - 1, let Q_n be the multiset of prime factors of c_n(b). Let f₁, f₂, f₃… be the proper divisors of p. Due to the factorization of b^p - 1, the multiset P can be partitioned into the multisets Q_f1, Q_f2 … Q_p.

Now let f be a proper divisor of p. Because c_f(b) is a factor of b^f - 1, any prime a from Q_f is a prime factor of b^f - 1 and hence is not a valid value of a corresponding to the given p and b. The only valid values of a must be in P but not in any Q_f. Therefore, they must be in Q_p, or equivalently factors of c_p(b).

This gives us an easy way to narrow down the possible values of a. The value c_p(b) often has fewer than half the number of digits of the value b^p - 1. However, we still don’t know if every prime factor of c_p(b) is a possible value of a. In particular, the only possible values of a are one more than multiples of p.

Let us assume that a divides c_p, and a = m·p + 1 for some integer m. Then a divides b^p - 1. If 1/a does not have a period length of p and instead has a period length that is some proper divisor k of p, then a divides b^k - 1. Since the factorization of b^p - 1 into cyclotomic numbers includes every cyclotomic number in the factorization of b^k - 1 in addition to c_p, we conclude that c_p divides

. Since each of the p/k terms on the right hand side is congruent to 1 mod a, a must divide p/k. But a = m·p + 1. This creates a contradiction, whereby a is both greater than and not greater than p. We conclude that the period length of 1/a being a proper divisor of p is impossible.

Theorem 3

The primes a such that 1/a has period length p in base b are precisely the factors of c_b one more than mutliples of p.

This is a follow-up to my previous post about higher-dimensional analogs of Pascal’s triangle. Here I will discuss more properties of this extension.

Connection to the binomial theorem

It is well known that the n-th row of Pascal’s triangle gives the coefficients for (x + y)^n. In fact, the term A(r, n - r) is the coefficient for the term x^r*y^(n - r).

This works because each term in the expansion of (x + y)^n is computed by taking the product of the members an ordered list of n x’s and y’s formed by selecting one term (either x or y) from each factor (x + y). This leads the creation of all 2^n possible lists of n x’s and y’s, leading to 2^n terms in total. However, many of these terms are the same due to multiplication being commutative. More specifically, two lists will have the same product if and only if they have the same number of x’s and y’s in them. For example, in the expansion of (x + y)^7, three of the 128 terms encountered will be x*x*x*x*y*y*y, x*y*x*y*x*y*x, and y*y*y*x*x*x*x. These all have the same value of x^4*y^3.

When expanding (x + y)^n, each term will be of the form x^r*y^(n - r) for some nonnegative integer r, r ≤ n. The number of copies of this term encountered, in terms of r, is equal to A(r, n - r) due to each copy coming from a list of r x’s and (n - r) y’s. This explains why the coefficient of each term (which is equal to the number of copies of that term in the expansion) is A(r, n - r) AKA the r-th member of the n-th row of Pascal’s triangle.

From this, it is easy to extend the idea to trinomials; expressions of the form (x + y + z)^n. In the expansion of this expression, each term is of the form x^r*y^s*z^(n - r - s) for some nonnegative integers r and s, r + s ≤ n. Before addition of alike terms, there is one term for each list of n x’s, y’s, and z’s, which get multiplied together. So, similar to the binomial theorem, the coefficient of x^r*y^s*z^(n - r - s) is the number of lists of r x’s, s y’s, and n - r - s z’s, equal to A(r, s, n - r - s). This number is the r-th number from the beginning, and the s-th number from the end, on the (n - r - s)-th row of the n-th layer of Pascal’s tetrahedron. Notice that r, s, and (n - r - s) are both the coordinates of the number and the exponents x, y, and z in the term. Also notice that the values r, s, and (n - r - s) can be permuted in any way and the value will be the same; this follows from the commutativity of the A function, but also can be easily derived by the fact that the expression (x + y + z)^n has symmetry between x, y, and z so permuting the exponents keeps the coefficient the same.

Of course, this also works in higher dimensions. In the expansion of (x0 + x1 + x2 … + xd)^n, the coefficient x0^r0*x1^r1*x2^r2*…*xd^rd = A(r0, r1, r2 … rd). The values r0 + r1 + r2 … + rd need to add to n, of course, meaning that this value occurs on the nth layer of Pascal’s simplex.

In summary, the coefficients of the nth power of a polynomial with d terms are the numbers from the nth layer of Pascal’s d-dimensional simplex!

Factors of factorials
or
how many distinct numbers can be on each layer?

You might have noticed that a formula for A(r, s, t…) is (r + s + t…)!/(r!*s!*t!…). That is, it is the factorial of the sum of the coordinates divided by the factorial of each of the coordinates themselves. What if we set the sum to a constant value? It is clear that on the nth layer, every number will be a factor of n!. This means that as we progress up the dimensions, from triangle to tetrahedron to pentachoron, etc., the values on the nth layer will never be higher than n! no matter what the dimension is. (More on this later.)

Which are the possible terms on the nth layer, for various values of n?

For n = 0 it’s trivial::

0! = 1

For n = 1 it’s still trivial:

1!/(1!) = 1

For n = 2 we have:

2!/(1!*1!) = 2
2!/(2!) = 1

For n = 3 there is:

3!/(1!*1!*1!) = 6
3!/(2!*1!) = 3
3!/(3!) = 1

For n = 4:

4!/(1!*1!*1!*1!) = 24
4!/(2!*1!*1!) = 12
4!/(2!*2!) = 6
4!/(3!*1!) = 4
4!/(4!) = 1

For n = 5:

5/(1!*1!*1!*1!*1!) = 120
5!/(2!*1!*1!*1!) = 60
5!/(3!*1!*1!) = 20
5!/(2!*2!*1!) = 30
5!/(4!*1!) = 5
5!/(3!*2!) = 10
5!/(5!) = 1

In general, these numbers can be found by dividing n! by the product of factorials of numbers that add up to n. This sequence is A036038 in the OEIS, and its name, “triangle of multinomial coefficients”, emphasizes the property we just found. For each n, there is one distinct term for each set of positive integers that adds up to n. This term is located at all the places whose coordinates are permutation of this set of numbers, plus an optional number of zeroes. For example, 2 + 3 + 5 = 10, and so the partition of 10 into 2, 3, and 5 produces the terms A(2, 3, 5), A(2, 5, 3), A(5, 3, 2), A(0, 3, 5, 2), A(0, 0, 5, 0, 2, 3, 0) and more, all on the tenth layer of various dimensional simplexes. In fact, all take places in the layer that are equivalent under symmetry. The number of nonzero numbers in this partition is the smallest dimension of simplex in which the term occurs. The total number of distinct terms that can appear on the nth layer is the nth partition number.

Since a limit exists to the number of distinct terms that appear on a single layer, regardless of dimension, there must be some dimension at which new terms just stop appearing. For example, the 5th layer of Pascal’s triangle contains 1, 5, and 10. Pascal’s tetrahedron adds 20 and 30. Pascal’s pentachoron (4-dimensional simplex) adds 60 to the list, and Pascal’s hexateron (5-dimensional simplex) adds 120. But after that, each new dimension adds no new terms to the 5th layer. In fact, as different copies of the same term are equivalent under symmetry, the only terms added to the 5th layer after 5 dimensions (4 dimensions for the layer itself) are symmetric transformations of the terms on one facet!

To see how this works, think about how the shape of each layer gets built when dimensions are added. The 5th layer of Pascal’s tetrahedron is a triangle, and each side of the triangle is just the 5th row of Pascal’s triangle. The 5th layer of Pascal’s pentachoron is a tetrahedron, and each of its four triangular faces is the 5th layer of Pascal’s tetrahedron. In general, in n dimensions, each layer is an (n - 1)D cross section of the figure itself. The shape of the layer is an (n - 1)-dimensional simplex, and it has n copies of the same layer one dimension lower as its (n - 2)-dimensional facets. Each term from one of these facets is only symmetric to terms on other facets, not on the simplex’s interior. But after n = 5 dimensions, all of the terms on its 5th layer are equivalent, meaning symmetric, to the terms on one of its facets. So they all appear on facets, which means that past 5 dimensions, every term on the 5th layer of Pascal’s simplex occurs on the outside. This property is independent of the numbers in the simplex and is still interesting when considering the geometry alone.

And this happens sooner or later for every layer. Which means that if you start  with a long line of objects, build it into a triangle with the original line as the base, make that into the base of a pyramid, make that pyramid into the base of a 4D pyramid, make that pyramid into the base of a 5D pyramid… past some dimension, all of the objects added to pyramid will appear on the outside, on the pyramid’s facets.

In fact, it’s pretty easy to tell when this will happen. Remember, the number of nonzero coordinates is the minimum dimension of the simplex the term appears in. For layer n, the maximum minimum dimension for a term–in other words, the largest dimension containing a term not in previous dimensions–occurs when n is partitioned into the most parts. This happens when n is partitioned into n copies of 1. The coordinates for the term are A(1, 1, …1, 1), with n 1s. This means that it occurs when Pascal’s simplex is n-dimensional. Also, since all the coordinates are identical, it is equidistant from each of its layer’s facets, meaning it is in the center of the nth layer. (It can also be proven to be in the center by the fact that it has no symmetric equivalents in the same dimension, again because the coordinates are identical.) This term is equal to n!.

New theorem:
Going up the dimensions, the nth layer of Pascal’s triangle stops getting new distinct terms after n dimensions, and every term in the layer thereafter is on the hypersurface. The final distinct term occurs in n dimensions (layers are (n - 1)-dimensional). It is in the center of the layer and equals n!.

Now you might be thinking, “Wait, are the values of all these terms actually different? You’ve been referring to them as ‘distinct terms’ when their coordinates come from different partitions of the layer number, but what’s to say no two distinct terms on the same layer have the same value?” This actually does happen. In fact, it happens every time n!/(r0!*s0!…z0!) = n!/(r1!*s1!…z1!); that is, when a number can be written in two different ways as a product of factorials of numbers that sum to the same value. In fact, even if they don’t sum to the same value, one of the them can be padded with 1′s until they do. So any two products of factorials with the same value will suffice.

The smallest such identity is 3!*5! = 1!*1!*6!, which leads to A(3, 5) = A(1, 1, 6) = 56. Thus, on the 8th layer of Pascal’s Tetrahedron, the number 56 appears on coordinates that are permutations of both (1, 1, 6) and (0, 3, 5). From this identity, both sides can be multiplied by any factorial product, leading to the following equivalences:

A(1, 3, 5) = A(1, 1, 1, 6) = 504
A(2, 3, 5) = A(1, 1, 2, 6) = 2520
A(1, 1, 3, 5) = A(1, 1, 1, 1, 6) = 5040
A(3, 3, 5) = A(1, 1, 3, 6) = 9240
A(1, 1, 1, 3, 5) = A(1, 1, 1, 1, 1, 6) = 55440
…

The number of distinct terms on each layer in n or more dimensions (or equivalently, on all dimensions taken together) is given by OEIS sequence A070289.

–

There are several other remarkable properties. Remember how I said that for each term A(r, s, t, … z), the terms given by permutations of (r, s, t, … z) are located at symmetrical positions under the layer’s simplectic symmetry? The number of these terms, since the layer has the shape and symmetries of a simplex, is just the number of ways to reflect or rotate a point to make distinct points using the symmetries of that simplex. But wait! This number is just the number of permutations of the coordinate–and what is a function that finds the number of permutations of a list of numbers? We have spent this entire blog post playing with one!

All that is needed to do is to express the number of occurrences of each distinct coordinate in the coordinate list. Let’s say that the first coordinate occurs a times in total, the second distinct coordinate occurs b times, the third occurs c times, etc. Then the total number of permutations is A(a, b, c, … k), where the list has k distinct terms. Since the original coordinate list had d terms, the number of permutations is a term on the dth layer of a new Pascal’s simplex.

This doesn’t just work for integer coordinates either. In fact, it works for any list of d coordinates that can be mapped to a point in (d - 1)-dimensional space. Remember, the space is made of all the points in the d-dimensional space whose coordinates add to n, making a cross section through the d-dimensional space.

Each way to permute a list of coordinates in this space, when applied to the points, produces one of the transformations that make the symmetry group of the (d - 1)-dimensional simplex. The possible values of A(a, b, … k) (the number of coordinate permutations) are the number of distinct points a single point can be mapped to under these transformations. Remember this, because it will be important.

Higher-dimensional kaleidoscopes

What really is a “line of symmetry”? Think about it. A symmetry is a set of transformations under which a set of points is invariant. For example, when an object has bilateral symmetry, it means that the position of each point can be reversed and it will match up to another point. If this reversal transformation is done to every point in 2D space, there will be a set of points that map to themselves. These points lie along a line, They are called the fixed points of the transformation, and the line they lie along is commonly called the “line” of symmetry of the aforementioned object.

Now let’s go back to our (d - 1)-dimensional space. Each point has d coordinates, leading to d! different permutations of coordinates and therefore d! different transformations of the points. It is easy to see that these transformations are one-to-one and onto, and therefore invertible. Furthermore, the fixed points under any transformation (besides the identity one) must all have some repeating numbers in their list of coordinates, as this is the only way that a non-trivial permutation of a list can output the same list. Conversely, each point with repeating numbers in its coordinates is a fixed point under some non-trivial transform.

Loosely speaking, the simplest-looking type of transform other than the identity transform is one that exchanges two coordinates while leaving the others the same. There are d*(d - 1)/2 of these. Each one can be described by starting with the d-by-d identity matrix and swapping two rows. This matrix acts as a linear transformation on R^d, and since it is a permutation matrix whose determinant is -1, it acts to reverse R^d; the fixed points make a subspace of dimension d - 1. The nth cross-section of R^d also gets reversed; the fixed points are the (d - 2)-dimensional intersection of the cross section and the subspace.

When d > 3, this intersection cannot be called a “line” of symmetry, as it is more than one dimension. Instead, let’s call it a hyperplane of symmetry. The d*(d - 1)/2 hyperplanes of symmetry together act like mirrors in space of d - 1 dimensions, and these transformations form a basis for the entire symmetric group. That is, any of the d! transformation of a single point can be formed by reflecting it through a combination of hyperplanar mirrors, like a kind of higher-dimensional kaleidoscope. Together, these mirrors cut the space into d! regions of points, these points together making up the set of all points not lying on any mirror.

Now, you might want to avoid the next part if you aren’t an expert on higher-dimensional geometry, as it contains a lot of advanced polytope terminology.

Each A_{(d - 1)} polytope is a convex uniform polytope formed by a Wythoffian operation on a (d - 1)-dimensional simplex. As it is uniform, it must be vertex-transitive, which means that any two vertices can be mapped onto each other using symmetric transforms. We have already seen what the transforms making up (d - 1)-simplectic symmetry are. The number of possible vertices of such a polytope must be a number of distinct vertices that are produced by a single vertex after each transformation. Thus, the number of possible vertices of any A_{d - 1}; polytope must be of the form A(p, q, … z) where p, q, … add to d. For example, the tetrahedron (o3o3x in Coxeter diagram) has A(3, 1) = 4 vertices, the truncated pentachoron (o3o3x3x) has A(3, 1, 1) = 20 vertices, and the biexipetirhombated dodecadakon (now there’s a shape you don’t think about every day) (o3o3x3o3x3o3o3o3x3x3o) has A(3, 2, 4, 1, 2) = 69300 vertices.

A sequence that appears everywhere

I want to finish this article as soon as possible, but there is one last property of the A function and the multidimensional Pascal’s “corner” that I just have to mention. As I mentioned in the previous post, the nth layer of the d-dimensional structure has terms that sum to d^n. But what if we sum just the terms on the inside of the nth layer; that is, every term whose coordinates are all positive?

What does this mean in terms of the A function? Remember, the A function gives the number of ways to order a sequence made of copies of distinct numbers, each number of copies corresponding to one of its arguments. If there are d terms–call them p, q, r, … z–, none of which are 0, the value of the function describes the number of runs of a sequence of p 0s, q 1s, r 2s … z (n - 1)’s. Summing these values up for all possible positive integer values of p, q, r, … z (that sum to n of course), we find the total number of n-digit strings that use every digit from 0 to d - 1, and only digits in that range.

If you remember one of my previous posts, you should be getting an epiphany right about now. If not, here is a quote straight from my “Starter constants and mysteries” post:

The A-th starter constant of the B-th powers is really the number of A-digit strings (I’m not calling them numbers, because the first digit can be 0 and it is still considered to have A digits), that use every digit from 0 to B - 1.

Yup, that’s right! It’s the starter constants! The sum of all A(p, q, r, … z) for each set of d nonzero terms p…z that sum to n, is equal to SC(n, d)!

Higher-dimensional Pascal’s Triangle

Most readers of this blog are probably familiar with Pascal’s Triangle. If not, it consists of rows of integers where the spaces between numbers in one row are directly above numbers in the next row down. The first row is made of two infinitely long strings of 0s separated by a 1. Each number on a subsequent row is derived by summing two adjacent numbers on the previous row, so each row contains one more nonzero term than the previous one. The zeroes aren’t written in the finished diagram, so it looks like the top of an infinitely large triangle:

It is well known that the rth number (using zero-based indexing) on the nth row (also using zero-based indexing) is the value nCr, read as “n choose r”, a function which computes the number of ways to choose r objects from a set of n, where the order of the chosen objects doesn’t matter. However, there are other ways to think of this operation. One of those ways is to consider a string of n objects consisting of r copies of one object and n - r copies of another object. Then nCr is the number of permutations of the string.

It is also helpful to stop thinking of it as a function of the total length of the string and the number of permutations. Instead, it should be thought of in terms of the number of objects of each type. If r objects are of type 0 and s objects are of type 1, then there are (r + s)Cr ways to order the string. Let’s call this value A(r, s).

Also, from now on in my examples, the “type 0″ objects will all be the number 0, and the “type 1″ objects will be the number 1, so as to match the index of the functional argument determining the number of copies of that object. Now the strings of objects can be considered lists of numbers.

One of the benefits of this new understanding is that the identity nCr = nC(n-r) can now be expressed as A(r, s) = A(s, r). Under the visualization, all this means is that the number of lists of r zeroes and s ones is the same of the number of lists of r ones and s zeroes. Another benefit is that the cases where nCr = 0 (where the value lay “outside” of the triangle) now become the cases where one of r or s is negative but r + s ≥ 0. The values that form the triangle itself come from the cases where r and s that are both nonnegative.

Now we can create a grid of all possible values of A for nonnegative values of r and s by plotting the value A(r, s) onto the point (r, s) in R^2:

This is Pascal’s triangle as seen from a different angle, In fact, it now looks more like the corner of a square, and this visualization as a quadrant of a plane will be useful when we extend the concept to higher dimensions. In Pascal’s triangle, the nth row of the triangle was the set of terms such that r + s = n. This line cuts a cross section through the grid perpendicular to the line r = s.

Three dimensions

Now that we have constructed Pascal’s triangle with a function that gives the number of orderings of zeroes and ones in various amounts, one might wonder what we can construct similarly from a function computing the number of orderings of three numbers. Let’s call this function A(r, s, t), where there are r, s, and t objects of each type. It will be understood as the number of ways that r zeroes, s ones, and t twos can be put into a list. Obviously the value of A(r, s, t) remains the same however r, s, and t are permuted.

If we plot the values A(r, s, t) on the points in 3-space (r, s, t) for nonnegative r, s, t, we get what looks like the corner of a cube. What happens when we set r + s + t, the total number of items to order, to a constant? Will we get a layer from a 3D version of Pascal’s triangle?

The points (r, s, t) in R^3 such that r + s + t is a constant integer form a plane perpendicular to the line r = s = t. The subset of this plane for positive r, s, t forms an equilateral triangle, whose vertices are on the r, s, and t axes. The points in this triangle such that r, s, and t are integers are arranged like the vertices of a triangular tiling, and each point is sqrt(2) away from its neighbors.

Under this geometric interpretation, this is the structure analogous to the nth row of Pascal’s triangle. It forms a triangle of points, n + 1 along each outer edge, and each point is associated with a trio of coordinates (r, s, t) from the original lattice and a corresponding value A(r, s, t) of the function.

Here is what the first 6 layers look like:

For each triangle, the left, right, and bottom edges contain the points where r, s, and t are 0 respectively. (Actually, the edges could be chosen in any order for this.) The lines of points through the triangle, parallel to one of these edges and x neighbors away from it, are the points whose coordinate corresponding to the direction of the edge (left, right, or bottom) has the value x. Of course, only two coordinates are required to label every point uniquely, but using three coordinates emphasizes the symmetry between the three values in the function; in fact, each permutation of r, s, and t maps points to other points and transforms the triangle onto itself! This is a beautiful way to demonstrate that the group of all permutations of three elements is the same as the symmetry group of an equilateral triangle!

So how do you compute these numbers anyway?

The formula for A(r, s, t) is A(r, s)*A(r + s, t). Of course, it is also A(r, t)*A(r + t, s), and A(s, t)*A(s + t, r). Intuitively, A(r + s, t) represents the number of lists that can be made from t twos and r + s blanks to be filled in with 0 and 1, and A(r, s) represents the number of ways the blanks in each list can be filled by r zeroes and s ones.

In practice, the nth layer can get computed from the first n + 1 layers in Pascal’s triangle. First un-flatten the square corner as seen above back into a triangle corner with 60-degree angles, and then multiply each member of the xth layer (where x goes from 0 to n) by A(n - x, x) = nCx. This is fun to do, as it doesn’t make the S3 symmetry of the resulting arrangement of numbers obvious until you actually try it.

Each layer can be constructed from the previous layer

There is also another way to construct each layer. In Pascal’s triangle, each row below the zeroth can be constructed by summing pairs of adjacent numbers on the previous row. Specifically, A(s, t) = A(s - 1, t) + A(s, t - 1). Even the 1s on the outside are created by summing 1s on the previous row with invisible zeroes neighboring them. (A(s, t) = 0 when s or t is negative.)

In the 3D version, triples of adjacent terms are of two types. One type, with coordinates (r - 1, s - 1, t), (r - 1, s, t - 1), (r, s - 1, t - 1), forms the vertices of a triangle pointing down. The other type, with coordinates (r - 1, s, t), (r, s - 1, t), (r, s, t - 1), forms the vertices of a triangle pointing up.

If the next layer gets made by summing both types of triples, it will have twice the density of numbers as the previous layer:

But if we sum only the triples pointing up, the ones with coordinates (r - 1, s, t), (r, s - 1, t), (r, s, t - 1) and put the results in the middles of the triangles, then the result will be the next layer, and the numbers will have coordinates (r, s, t) for all values of r, s, and t that sum to the layer number.

The fact that A(r - 1, s, t) + A(r, s - 1, t) + A(r, s, t - 1) = A(r, s, t) is obvious when we consider the fact that A(r, s, t) represents the number of strings of r 0s, s 1s, and t 2s and these consist of:

• A(r - 1, s, t) strings where a 0 is followed by r - 1 0s, s 1s, and t 2s
• A(r, s - 1, t) strings where a 1 is followed by r 0s, s - 1 1s, and t 2s
• A(r, s, t - 1) strings where a 2 is followed by r 0s, s 1s, and t - 1 2s.

Sum of each layer

In Pascal’s triangle, the numbers in the nth row sum to the value 2^n. This can be explained by the fact that there are 2^n strings of length n made of only 0s and 1s. Similarly, as there are 3^n strings of length n made of only 0s, 1s, and 2s, each layer of Pascal’s tetrahedron sums to a power of 3.

Higher dimensions

The function A(r, s, t) can be generalized to any number of arguments. Really, it can be thought of as taking in a tuple, of any length, of integers as arguments. For integers r, s, t, … z, it can be defined as A(r, s, t, … y, z) = A(r, s, … y) * A(r + s + … + y, z), and for two arguments, A(r, s) is defined as (r + s)Cr. The nth layer of the structure can be found by taking the set of points (r, s, … z) whose coordinates that sum to n, and associating to each point with tuple T of coordinates the value A(T), which will be positive if no coordinate is negative and 0 if at least one of them is negative but the sum is still positive.

Just as the layers of the 3D Pascal’s triangle are shaped like equilateral triangles, the layers of the higher dimensional analogs will also be shaped like a regular simplex, a shape which is just a pyramid of a regular simplex from the previous dimension, where all edges are the same length. For example, the 3D simplex is a tetrahedron, and the 4D simplex is a pentachoron.

In d dimensions, the lattice of points (r0, r1, r2, r3, … r(d - 1)) where each r-value is an integer, forms the vertices of a d-hypercubic tessellation of edge length 1. The subset of points where the coordinates are required to sum to an integer n form the vertices of a (d - 1)-simpletic tessellation of edge length √2. The points on this layer with nonnegative coordinates form a subset of this lattice in the shape of a (d - 1)-dimensional simplex. From now on, these points will be what I mean when I refer to a “layer” of the figure.

The points in the nth layer of the d-dimensional lattice (which itself is (d - 1)-dimensional, of course) can be decomposed into a stack of n + 1 (d - 2)-dimensional sub-layers of points in the shape of (d - 2)-dimensional simplices, ranging from n + 1 points per edge down to 1 point per edge (at 1 point per edge, there is also only one point in the entire sub-layer; this is the tip of the layer). This stack constructs the (d - 1)-dimensional simplex as a pyramid of a (d - 2)-dimensional simplex.

How to find the numbers in each layer

The same method mentioned above, of constructing the nth layer of 3D Pascal’s pyramid from the first n + 1 layers of Pascal’s triangle, also works for higher dimensions. For the nth layer of the d-dimensional pyramid, stack the first n + 1 layers of the (d - 1)-dimensional pyramid (the 0th to the nth layer), and multiply each number on the x-th layer by A(n - x, x) which is just equal to nCx.

For example, here are the first 5 layers of 3D Pascal’s triangle:

And here are the cross-sections of layer 4 in 4D Pascal’s triangle:

Except this does not work exactly from a geometrical standpoint, because in the first n layers of Pascal’s pyramid, adjacent points in neighboring layers are only 1 unit apart, instead of the √2-unit distance between adjacent points from the same layer. Instead of a regular simplex for each layer, this method simply produces a cut-off corner of a hypercube! To fix this problem, all that is needed is to “stretch” the pyramid by increasing the distance between neighboring layers (now “sub-layers” as part of a layer themselves) until all adjacent points have the same distance of √2 between them.

Each layer can also be constructed by adding terms from the previous layer.

To understand how this would work, you have to realize that in (d + 1)-dimensional Pascal’s triangle, there are d different types of “gaps” between points. The x-th type is found by taking the coordinates of a point x layers ahead and finding all possible ways to subtract 1 from x of those coordinates. For example, in 4D Pascal’s triangle, a gap of type 2 would be made of these points: (r - 1, s - 1, t, u), (r - 1, s, t - 1, u), (r - 1, s, t, u - 1), (r, s - 1, t - 1, u), (r, s - 1, t, u - 1), (r, s, t - 1, u - 1) - there is one gap for each possible set of values of r, s, t, and u.

Gaps of type 1 form the vertices of a simplex, flipped relative to the orientation of the layer itself. The numbers from these points get added to form the number in the next layer, at the center of the gap. Each point belongs to exactly d+1 of these gaps, so the sum of the terms from the (n + 1)st layer is (d + 1) times the sum of the terms from the nth layer. The initial layer sums to 1 (as 1 is the only nonzero term in that layer), and therefore the nth layer sums to the value (d + 1)^n (again, the initial layer must be counted as the 0th, not the 1st).

Also, not all these gaps are the same shape. Some form the vertices of a simplex, some the vertices of a rectified or birectified simplex, etc. In fact, these gaps are the shapes of the facets of the simpletic tessellation whose vertices are the points in a single layer.

So, to review:

• (d + 1)-dimensional Pascal’s triangle is a collection of points in (d + 1)-dimensional space with coordinates (r, s, t, … y, z) where each coordinate is a positive integer.
• Each point is associated with a value A(r, s, t, … y, z), where A(r, s) = (r + s)Cr = (r + s)!/(r!*s!) and A(r, s, … y, z) = A(r + s + … + y, z).
• The nth layer of this triangle is the set of points for which r + s + … y + z is a constant.
• The points in a single layer are the vertices of a d-dimensional simplectic tessellation (d-honeycomb) of edge length √2 – the 2D simplectic tessellation is the triangular tiling and the 3D simplectic tessellation is the tetrahedral-octahedral honeycomb.
• The value of the point (r, s, … y, z) can be found by summing the values of the points (r - 1, s, … y, z), (r, s - 1, … y, z) … (r, s, … y - 1, z), (r, s, … y, z - 1).

Nice! Soon we’ll look at more properties of this triangle, like which numbers can appear where.

How to calculate exact trig values, part 3

11th roots of unity

This is my third post about calculating exact trigonometrical values based on roots of unity. I am giving the examples for prime roots of unity.

My previous post showed that the 7th roots of unity had square roots and cube roots in their formulas, because 7 - 1 = 2*3. Since 11 - 1 = 2*5, the 11th roots of unity will have square roots and 5th roots in their expression, namely, a sum of 4 fifth roots, each of formulas involving the fifth roots of unity.

Before we start, I want to make a correction to something I said earlier. In my last post I stated that a1 + a2 + a3 + r1*(a1 + r1*a2 + r2*a3) + r2*(a1 + r2*a2 + r1*a3) = 3*r1, and a1 + a2 + a3 + r2*(a1 + r1*a2 + r2*a3) + r1*(a1 + r2*a2 + r1*a3) = 3*r2. In fact, the first left-hand expression equals 3*r2 and the second equals 3*r1. This is the corrected expression for the 7th root of unity:

Now on to the current calculation.

Here are the 11th roots of unity:

1, x1, x2, x3, x4, x5, x6, x7, x8, x9, x10

Let’s try to find a power cycle that goes through each 11th root of unity once, except for 1, starting with x1.

Let’s try squaring each term. Since x(n) is just x1^n, and x1^11 = 1, then x(a)*x(b) = x((a + b) mod 11). This is axiom 2 from the first post.

x1, x2, x4, x8, x5, x10, x9, x7, x3, x6, x1…

This gives us a cycle of 10, like we wanted. Now to find each root of unity, we are going to be solving a quadratic equation and a quintic equation. Let’s first find the roots of the equation by summing together every fifth term of the cycle, starting from the first, second, third, and fourth, and fifth terms:

x1 + x10 = a1

x2 + x9 = a2

x4 + x7 = a3

x8 + x3 = a4

x5 + x6 = a5

To find each of these values, we will need to find the following values, where r1, r2, r3, and r4 are the four 5th roots of unity not equal to 1, r1 has a polar angle of 2*pi/5, and r(n) = r1^n:

a1 + a2 + a3 + a4 + a5 = s0

a1 + r1*a2 + r2*a3 + r3*a4 + r4*a5 = s1

a1 + r2*a2 + r4*a3 + r1*a4 + r3*a5 = s2

a1 + r3*a2 + r1*a3 + r4*a4 + r2*a5 = s3

a1 + r4*a2 + r3*a3 + r2*a4 + r1*a5 = s4.

Then we can find the five roots by taking the inverse Fourier transform:

s0 + s1 + s2 + s3 + s4 = 5*a1

s0 + r4*s1 + r3*s2 + r2*s3 + r1*s4 = 5*a2

s0 + r3*s1 + r1*s2 + r4*s3 + r2*s4 = 5*a3

s0 + r2*s1 + r4*s2 + r1*s3 + r3*s4 = 5*a4

s0 + r1*s1 + r2*s2 + r3*s3 + r4*s4 = 5*a5

We already know that s0 = x1 + x10 + x2 + x9 + x4 + x7 + x8 + x3 + x5 + x6 = -1, by axiom 1, but s1, s2, s3, and s4 must be calculated via their fifth powers as sums of 5th roots of unity.

The algebra required to solve for s1^5 is so long-winded that it took 2 whole years since I started writing this post before I finally managed to concentrate on it long enough to solve it. There are 3125 values, of 70 different types, to sum in the expanded expression. Each term consists of a product of 5 values of the form a(n), multiplied by a 5th root of unity, each of which need to be expanded into a pair of x(n) values. Here is the result:

(a1 + r1*a2 + r2*a3 + r3*a4 + r4*a5)^5 = -196 - 130*r1 + 255*r2 - 20*r3 + 90*r4.

After substituting into this expression the respective values for r1, r2, r3, and r4 that we calculated way back in the first post, it becomes:

s1 = -979 - 275*√5 - 220i*√(10 - 2√5) + 275i*√(10 + 2√5)

Amazing! I always get a feeling of wonder when I see such large and arbitrary-looking numbers in a formula for such an easy to define value. The only patterns I can see in these numbers are that -979, -275, -220, and 275 are all multiples of 11 - the degree of the roots we are calculating - and that -275, -220, and 275 are all multiples of 5 as well. The divisibility by 5 occurs because all the terms containing a value r(n) could have their a(n) values cyclically permuted to make 5 different terms having the same value, forcing the total number of r(n)-containing terms to be a multiple of 5 for each value of n.

The expressions for s2^5, s3^5, and s4^5 can be found by substituting out powers of r1 for the corresponding powers of r2, r3, and r4 respectively. Their values are:

s2^5 = -979 + 275*√5 - 220i*√(10 + 2√5) - 275i*√(10 - 2√5)

s3^5 = -979 + 275*√5 + 220i*√(10 + 2√5) + 275i*√(10 - 2√5)

s4^5 = -979 - 275*√5 + 220i*√(10 - 2√5) - 275i*√(10 + 2√5)

Now we need to take 5th roots of each of these expressions. The trouble here is in finding out which 5th root to use. As I said in my first post on roots of unity, I am defining c^(1/n) to be the value x having a polar angle equal to 1/n that of c, such that x^n = c, and therefore x has an angle between 0 and 2*pi/n radians. For the other nth roots of c, it needs to be multiplied by one of the nth roots of unity. But we don’t know what s1’s polar angle is, so we don’t know if it’s 1, r1, r2, r3, or r4 times (s1^5)^(1/5).

I haven’t found any pattern in which 5th root to choose when, but a calculator can check that:

s1 = r1*(-979 - 275*√5 - 220i*√(10 - 2√5) + 275i*√(10 + 2√5))^(1/5)

s2 = r1*(-979 + 275*√5 - 220i*√(10 + 2√5) - 275i*√(10 - 2√5))^(1/5)

s3 = r4*(-979 + 275*√5 + 220i*√(10 + 2√5) + 275i*√(10 - 2√5))^(1/5)

s4 = r4*(-979 - 275*√5 + 220i*√(10 - 2√5) - 275i*√(10 + 2√5)^(1/5)

Now we can calculate our a(n) values:

a1 = (-1 + r1*(-979 - 275*√5 - 220i*√(10 - 2√5) + 275i*√(10 + 2√5))^(1/5) + r1*(-979 + 275*√5 - 220i*√(10 + 2√5) - 275i*√(10 - 2√5))^(1/5) + r4*(-979 + 275*√5 + 220i*√(10 + 2√5) + 275i*√(10 - 2√5))^(1/5) + r4*(-979 - 275*√5 + 220i*√(10 - 2√5) - 275i*√(10 + 2√5)^(1/5))/5

a2 = (-1 + (-979 - 275*√5 - 220i*√(10 - 2√5) + 275i*√(10 + 2√5))^(1/5) + r4*(-979 + 275*√5 - 220i*√(10 + 2√5) - 275i*√(10 - 2√5))^(1/5) + r1*(-979 + 275*√5 + 220i*√(10 + 2√5) + 275i*√(10 - 2√5))^(1/5) + (-979 - 275*√5 + 220i*√(10 - 2√5) - 275i*√(10 + 2√5)^(1/5))/5

a3 = (-1 + r4*(-979 - 275*√5 - 220i*√(10 - 2√5) + 275i*√(10 + 2√5))^(1/5) + r2*(-979 + 275*√5 - 220i*√(10 + 2√5) - 275i*√(10 - 2√5))^(1/5) + r3*(-979 + 275*√5 + 220i*√(10 + 2√5) + 275i*√(10 - 2√5))^(1/5) + r1*(-979 - 275*√5 + 220i*√(10 - 2√5) - 275i*√(10 + 2√5)^(1/5))/5

a4 = (-1 + r3*(-979 - 275*√5 - 220i*√(10 - 2√5) + 275i*√(10 + 2√5))^(1/5) + (-979 + 275*√5 - 220i*√(10 + 2√5) - 275i*√(10 - 2√5))^(1/5) + (-979 + 275*√5 + 220i*√(10 + 2√5) + 275i*√(10 - 2√5))^(1/5) + r2*(-979 - 275*√5 + 220i*√(10 - 2√5) - 275i*√(10 + 2√5)^(1/5))/5

a5 = (-1 + r2*(-979 - 275*√5 - 220i*√(10 - 2√5) + 275i*√(10 + 2√5))^(1/5) + r3*(-979 + 275*√5 - 220i*√(10 + 2√5) - 275i*√(10 - 2√5))^(1/5) + r2*(-979 + 275*√5 + 220i*√(10 + 2√5) + 275i*√(10 - 2√5))^(1/5) + r3*(-979 - 275*√5 + 220i*√(10 - 2√5) - 275i*√(10 + 2√5)^(1/5))/5

Unfortunately, since Unicode lacks a fifth root symbol (that I am aware of), I had to write the 5th root of x as x^(1/5).

Anyway, we now know the values of x1 + x10, x2 + x9, x3 + x8, x4 + x7, and x5 + x6.

Since x1 and x10 are complex conjugates, (x1 + x10)/2 is the real part of x1. This is the same value as cos(2*pi/11), and it is just a1/2.

Here is an image of what the expression for cos(2*pi/11) actually looks like when written out (with fifth-root symbols in place of x^(1/5)), just to show you how long it gets.

To figure out the value of, say, x1, we will be needing both x1 + x10 and x1 - x10. We already know the x1 + x10 = a1. Let’s call x1 - x10 = t1.

t1^2 = (x1 - x10)^2 = x2 + x9 - 2 = a2 - 2

So, t1 = √(a2 - 2). And just like a1 = 2*cos(2*pi/11), t1 = 2i*sin(2*pi/11).

So:

sin(2*pi/11) = √(2 - a2)/2 = √(55 - 5*(s1^5)^(1/5) - 5*r4*(s2^5)^(1/5) - 5*r1*(s3^5)^(1/5) - 5*(s4^5)^(1/5))/10.

If written out in full, this expression would look similar to the one given above except that:

• the numerator is under a square-root sign
• it starts with 55 instead of -1 and then subtracts the 5th roots instead of adding them
• All of the 5th roots are multiplied by 5
• The 1st and 4th ones don’t get multiplied by r(n) values.
  

The sines and cosines of 4*pi/11, 8*pi/11, 6*pi/11, and 10*pi/11 can be found by doing operations on a1, a2, a3, and a4 respectively.

————————————–

Whew! That was way more complex than the formula for the 7th roots of unity. Next up is the 13th roots of unity, and I don’t think they will be nearly as hard.

Imagine we have an infinite lattice of points, each one having coordinates F(s, t) = [x, y] = [a*s + b*t, c*s + d*t] for some real values {a, b, c, d} where s and t can equal any integers.

For example, here is a picture of the lattice with a = 3, b = 1, c = -2, d = 4:

Points with integer coordinates are shown in the background. The red lines are s = n, the green lines are t = n. Blue points are in the lattice.

As we can see, 1/12 of all the points with integer coordinates are in the lattice. Given a set of a, b, c, d values, how can we tell what fraction of the points will be in the lattice?

We can start by seeing that drawing lines for the set of all points where s = n or where t = n, for all integer values of n, divides the plane into a tiling of parallelograms, as in the image above. There is a direct correspondence between the parallelograms and points in the lattice; each point is the lower-left corner of a parallelogram, and each parallelogram has a lattice point in its lower-left corner. Therefore, the area of a parallelogram is the same as one over the fraction of all integer-coordinate points that are in the lattice.

Now, one could calculate the area of this parallelogram by taking the area of the (a + b) by (c + d) rectangle that it’s embedded in and subtracting the areas of the b by c rectangles and the a by c and b by d right-angled triangles… but it just so happens that the area of a parallelogram embedded in 3-space can be found by taking the magnitude of the cross product of the two vectors formed by going from one point to its two neighbors. In this case, those vectors are [a, c, 0] and [b, d, 0]. Their cross product is [0, 0, a*d - b*c], and its magnitude is a*d - b*c.

This value, a*d - b*c, is the factor by which the area of any 2D shape before the transformation changes when the transformations is applied, as any shape can be approximated by a large number of parallelograms.

The transformations can also be written:

and as you might have noticed, the scaling factor a*d - b*c is the determinant of this matrix. This means that the determinant of any matrix is how much it “stretches” a plane when multiplied by all points on the plane.

What this means is that if and only if the value a*d - b*c = ±1, the lattice points cover every point with integer coordinates. But there is another way to find out whether all integer-coordinate points are reached. Simply find the values s0, s1, t0, t1, such that F(s0, t0) and F(s1, t1) equal [1, 0] and [0, 1] respectively. If these s and t values are integers, then every point [m, n] can be reached by setting s = s0*m + s1*n and t = t0*m + t1*n.

So what are the values of s0, s1, t0, and t1 in terms of a, b, c, and d? The equations to solve are:

a*s0 + b*t0 = 1
c*s0 + d*t0 = 0
a*s1 + b*t1 = 0
c*s1 + d*t1 = 1

s0 = d/(a*d - b*c)
t0 = c/(b*c - a*d)
s1 = b/(b*c - a*d)
t1 = a/(a*d - b*c)

If the scaling factor, a*d - b*c, is called D, these can be written as d/D, -c/D, -b/D, a/D. Since all of them need to be integers, the value D must be a factor of a, b, c, and d.

Let’s say that a, b, c, and d are equal to D*i, D*j, D*k, and D*l, which is true for some integers i, j, k, and l. Substituting these into the formula for D, we get that D = D^2*(i*l - j*k). Since a, b, c, and d are factors of D, they must also be factors of D^2. Similarly, since they are factors of D^2, they must be factors of D^4. In fact, they need to be factors of D to every positive power.

Since a, b, c, and d can only have a finite number of factors, the number of distinct powers of D must be finite. Therefore, D can only be 0, 1, or -1. Clearly letting D = 0 leads to undefined values of s0, t0, s1, and t1. Therefore, the only possible values of a*d - b*c are ±1. Of course, this restriction is not only necessary but sufficient to insure integer values of s0, t0, s1, and t1 and therefore a covering of every integer point in the lattice.

Last digits of powers, continued

In my last post on this subject, I proved that for integers {n, x} and x ≥ 2, not only do n^(x + 4) and n^x always have the same last digit (they are congruent mod 10) but n^(x + 20) and n^x always have the same last two digits (they are congruent mod 100)!

Let’s look at the last three digits. First we will look at them in base 5 – that is, look at the whole number modulo 5^3. We already know that mod 5^2, n^(x + 20) ≡ n^x (except in special cases), so the last two digits repeat with period 20. From here, it is just a small step to prove that the last 3 digits repeat with period 100.

The special cases I mentioned above happen when n is divisible by 5 and x is less than 2. So for now we will assume that n is not divisible by 5.

Say that n^x = p and n^20 = 25*q + 1, which is true for some integer q unless n is divisible by 5. Now, n^(x + 20) is equal to 25*p*q+p, which is congruent to p mod 25, as expected. n^(x + 40) is n^(x + 20 + 20) = 25*q*(25*p*q + p) + (25*p*q + p) which is congruent to 50*p*q + p mod 125. In fact, mod 125, n^(x + 20*k) ≡ k*25*p*q + p for all k. This also means that n^(x + 100) ≡ 125*p*q + p, and therefore is also congruent to p, which equals n^x. Since n^(x + 100) ≡ n^x mod 125, the last 3 digits of the powers of n repeat with period 100.

This holds true for all n and x such that p is an integer, so this pattern works all the way back to n^0.

In the other cases, where n is divisible by 5, n^3 and all higher powers of n are 0 mod 125. So, still speaking in base 5, the last three digits of these powers will repeat with period 1.

This means that, for integers {n, x} and x ≥ 3, n^(x + 100) ≡ n^x mod 125, and thus the sequence formed from the last 3 digits in base 5 of a(x) = n^x always repeats in (a factor of) 100 steps.

Now we need to look at the last digits of n^x mod 8. Remember, for coprime a and b, if a number’s values mod a and mod b are known, its value mod a*b can always be calculated. This means that if the values of n^x repeat with period 100 when taken both mod 8 and mod 125, they also repeat with period 100 when taken mod 1000.

The easiest way here is to realize that if n is odd, n^2 ≡ 1 mod 8. This means that for even x, n^x ≡ 1 (because all even powers are squares) and therefore for odd x, n^x ≡ n. Since n^(x + 2) ≡ n^x, n^(x + 100) ≡ n^x, for odd n and positive x. For even n, n^x is divisible by 8, and so n^x ≡ 0, whenever x ≥ 3.

This means that for integers {n, x} and x ≥ 3, n^(x + 100) ≡ n^x when taken mod 8 or mod 125. It follows that n^(x + 100) ≡ n^x mod 1000. This means that in base 10, the last 3 digits of powers of n should have settled into a cycle of 100 terms by the time n^3 is reached. Compare this to previous results about the last 2 digits and 1 digit, written in formal logic:

• ∀n,x ∈ ℤ:((x ≥ 3) → (n^(x + 100) ≡ n^x mod 1000)
• ∀n,x ∈ ℤ:((x ≥ 2) → (n^(x + 20) ≡n^x mod 100)
• ∀n,x ∈ ℤ:((x ≥ 1) → (n^(x + 4) ≡ n^x mod 10)

At this point, the pattern seems obvious. If we take the number mod 10^p, all we need to do to make the statement true is to make the repeat length 4*5^(p - 1) and say the pattern always works when x ≥ n.

And indeed, looking at the last 4 digits of powers of n, it is seen that they always repeat after 500 terms! Mod 5^4, they repeat every 500 terms for a reason similar to the proof in the second paragraph; and taken mod 2^4, the period is 4, which is also a factor of 500. And for some values of n, 4 terms are needed for the powers to acquire all the factors of 2 or 5 for their last 4 digits to be repeated 500 terms later. So for this pattern to work for all n, the exponent must be at least 4.

But when we get to 5 digits, the pattern seems to break down. One would expect the last 5 digits of n^x to repeat in 2500 terms. Mod 5^5, they all do repeat with period 2500 (or a factor thereof), but mod 2^5, some of them repeat with period 8! For example, 5^6 ≡ 9 and 5^14 ≡ 9, but 5^10 ≡ 25. Since 2500 is not divisible by 8, 5^n and 5^(n + 2500) are not congruent.

It turns out that for general values of n, 5000 terms are needed for powers of n to repeat mod 10^5, and therefore for the last 5 digits of these powers to repeat.

So, what’s the actual formula? Well, unsurprisingly, the repeat length of n^x mod 2^(p + 1) is based on that of n^x mod 2^p. Fortunately, the proof is simpler than for 5^p.

Let’s guess that n^x mod 2^p has a repeat length of 2^(p - 2) (or a factor thereof) when p ≥ 3. After all, this is what we saw for p = 3, 4, and 5. To prove this, we will prove that adding 1 to the value of p doubles the repeat length. Given an odd value k such that k^x mod 2^p has the full repeat length (i.e. it repeats in 2^(p - 2), but no factor thereof, steps), k^0 ≡ k^(2^(p - 2)) ≡ 1, but k^(2^(p - 3)) ≢ 1. If we can prove that k^(2^(p - 2)) mod 2^(p + 1) ≢ 1, the proof will be complete because k^(2^(p - 2)) will be congruent to 2^p + 1 mod 2^(p + 1) and k^(2^(p - 1)) will be congruent to 1, giving k^x a repeat length of 2^(p - 1) mod 2^(p + 1). If we furthermore assume that k^(2^(p - 3)) ≡ 1 mod 2^(p - 1), k^(2^(p - 3)) mod 2^p can only be 1 or 2^(p - 1) + 1. So its square, k^(2^(p - 2)), must be congruent to 1. However, we assumed by induction that k^(2^(p - 3)) mod 2^(p - 1) ≢ 1, and 1 and 2^(p - 1) + 1 are the only values mod 2^p whose square is congruent to 1. So k^(2^(p - 2)) cannot be 1 mod 2^(p + 1) and therefore k^x has a repeat length of 2^(p - 1) mod 2^(p + 1).

This means that 4 terms are needed for powers of n to repeat mod 2^4, 8 terms are needed for powers of n to repeat mod 2^5, and so on. 2^(p - 2) terms are needed for powers of n to repeat mod 2^p, and 5^(p - 1) terms are needed for them to repeat mod 5^p. So for p > 3, 10^(p - 1)/2 terms are needed for x^n to repeat mod p.

Jonathan Bowers‘ birthday, plus a program

Today (November 27) is the 47th birthday of a really great mathematician named Jonathan Bowers. He is a mathematician who specializes in studying large numbers and higher dimensional polytopes. Among his many achievements in the study of polytopes were discovering the majority of the known uniform polychora (4-dimensional polytopes) and an even higher percentage of the known uniform higher-dimensional polytopes. He also investigates facet-transitive polytopes and curved objects known as polytwisters. His website can be found here: https://polytope.net/hedrondude/home.htm

He also invented a notation for describing very large numbers, called “infinity scrapers”. This notation, called Bowers Exploding Array Function, takes the form of a linear or multidimensional array (or even above multidimensional and into more abstract spaces, which collapse down to a number of dimensions determined by a value in an intermediate stage in an array’s evaluation). Its rules are as follows:

• The first entry is called the base.
• The second entry is called the prime entry.
• Ones are the default (and smallest) array entry, and each array can be thought of as lying in a multidimensional space each of whose unspecified entries is a 1. For example,

{3, 3, 3} = {3, 3, 3, 1, 1, 1, 1} =

{3, 3, 3, 1, 1, 1, 1…
{1, 1, 1, 1, 1…
{1, 1, 1, 1…
{1…
…

• If the prime entry is 1, the entire array evaluates to the base.
  
• The first entry after the prime entry that is not 1 is called the pilot.
• The entry right before the pilot is called, if it exists, the copilot.
• In each step, the copilot (if it exists) gets replaced by the value of the original array, except with the prime entry decremented.
• Also in each step, the pilot of the original array gets decremented.
• Every entry before the pilot gets replaced by the base value.
• If there are any rows/ spaces before the pilot, they get filled w/th a hypercube of the same dimension of edge length equal to the prime entry, w/th one corner at the first entry of the space.
• This continues until the original array consists of just a base and a prime entry. The final value is the base to the power of the prime entry.

I am writing a Python program (currently in development) to “evaluate” an array, except that most of their values are too big to even express in this universe! The program still goes as far as it can. Here it is: https://drive.google.com/open?id=0Bw_QB526PYiBX3RvcHBicTdDS2c

I know so much about polytopes I’m surprised I didn’t talk about them more on this blog. I know that it would probably take about 100 medium-sized posts to do justice to everything I know about them, but one of these days I still plan to delve into the subject from the beginning and explore what I know about it in a neat fashion.

Anyway, a few days ago I was watching a chemistry video on Khan Academy. It involved a geometric proof that the hydrogen atoms in a methane molecule always met the carbon atom at an angle of about 109°. They started by constructing a tetrahedron in such a way that it would be easy to find the angle between two vertices and the center.

In the video, four points were plotted in a 3-dimensional graph: (√(2), 1, 0), (-√(2), 1, 0), (0, -1, √(2)), and (0, -1, -√(2)), and the video was going to explain that those were the vertices of a regular tetrahedron.

Of course, the most obvious way to prove it was to find the squares of the distances between the x-, y-, and z-coordinates of each pair of points, add them together, and determine that the final result was the same in all 6 cases. By the 3D extension to the Pythagorean theorem, these results were the squares of the distances between pairs of points, and thus verifying their equality was equivalent to proving that all the points are equidistant from each other. Knowing that four points are equidistant from each other is sufficient for proving that they are the vertices of a regular tetrahedron.

But my grandiose knowledge of polytopes caused me to notice a more beautiful geometric proof, which hinged on the fact that those four points were just alternate vertices of a cube.

I immediately paused the video and wrote this proof down. Here is what I wrote:

If you start with a cube with coordinates (±√(2), ±1, 0) where the two plus-and-minuses are independent of each other, for four of its vertices, and (0, ±1, ±√(2)) again where the two plus-and-minuses are independent, for the other four; you can remove four of the vertices that aren’t adjacent in the cube, and the four remaining vertices will be (√(2), 1, 0), (-√(2), 1, 0), (0, -1, √(2)), and (0, -1, -√(2)).
And I can prove that if you remove four vertices from a cube in such a fashion, the other four will form a regular tetrahedron. In fact, the ones you removed will also form such a tetrahedron.
First of all, let’s prove that it actually is a cube that we start with. The eight coordinates I gave above expand out to be:
(√(2), 1, 0), (√(2), -1, 0), (-√(2), 1, 0), (-√(2), -1, 0), (0, 1, √(2)), (0, -1, √(2)), (0, 1, -√(2)), (0, -1, -√(2)).
Now, four of those points (those being (√(2), 1, 0), (-√(2), 1, 0), (0, 1, √(2)), (0, 1, -√(2))) form a square with edge length 2. (This is pretty easy to verify for yourself, especially if you take out the middle coordinates.)
The other four points are just the same, except where the y-coordinate is -1 instead of 1. So each of these points are two units directly below the other points. This means the figure formed is a right prism with height length 2, of a square with edge length 2. Such a prism has to be a cube.
Okay, now it’s time for the interesting part of the proof. First, as I said, the four vertices at (√(2), 1, 0), (-√(2), 1, 0), (0, -1, √(2)), and (0, -1, -√(2)) were taken such that no two of them are adjacent to each other. As it turns out, choosing four vertices of a cube in such a way forces the four vertices to be vertices of a regular tetrahedron. This is because the distance between each vertex and the other three is the distance across the diagonal of a square in the original cube, making it √(2) times the edge length of the cube.
This, in turn, is because when the vertices are chosen in this way, a pair of them will be on every square of the cube, directly opposite each other. Each of those pairs will be connected by a line segment which is the diagonal of its square, so therefore its length must be √(2) times the edge length of the square. As there are six squares in the cube and one diagonal for each, this accounts for all six possible pairs of the 4 vertices chosen and determines that they are all the same distance apart.
Lastly, why must the resulting shape be a regular tetrahedron? Start with three points. If these three points are equidistant from each other, they must form an equilateral triangle. Now, if a fourth point is added outside the plane of these three points, a tetrahedron must be formed, in that four sets of three points can be chosen, each of which acts as a triangular face. Finally, since each of these sets of three points must be equidistant, they must form equilateral triangles. Since the shape has equilateral triangles as faces, it must be a regular tetrahedron.

Lychrel numbers, part 2

This is a follow-up to my earlier post about Lychrel numbers.

It seems very likely that the reverse-and-add process will never reach a palindrome when starting with 196. This is because when a number is on the order of 10^(2*n), the probably of it resolving into a palindrome in the next iteration is very roughly 1 in 2^n. Since the number multiplies by about sqrt(10) after each iteration, the probability of it reaching a palindrome gets decreases exponentially for each iteration, by a factor of about 2^(¼). For those with a background in cellular automata, the process can be liked to running a pattern in a very barely exploding rule, like B368/S1278, where the probability of eventual stabilization decreases exponentially with the number of unstabilized cells.

However, like the normality of pi or e, or whether any patterns in the aforementioned rule explode, this has not been proven, because the process is an adequate pseudo-random number generator.

On the other hand, in binary it can be proven that some numbers will never reach a palindrome this way, the smallest being 10110.

This comes from the fact that when a binary number is of the form 10[1]_n-101[0]_n (where [b]_n is the digit b repeated n times), the next four steps of the process will give 11[0]_n-110[1]_n-201, 10[1]_n01[0]_n, and 10[1]_n01[0]_n+1. None of these forms are palindromes, and the fourth is just the first with n replaced by n+1. So whenever a number can be written as 10[1]_n-101[0]_n for some value of n, by induction it will never produce a palindrome. 10110 becomes 1010100 after two steps and thus, it is proven that it is a binary Lychrel number.

Lychrel numbers

One year ago, on July 16, 2015, I got the laptop on which I am writing this now.

First of all, the day July 16 should be familiar to anyone who read my Cheryl’s Birthday post. And when I got my laptop, I wanted to name it after this math problem. At first I thought of naming my laptop Cheryl. But then, I remembered the Lychrel numbers: a set of numbers that was named as a “rough anagram” of the name Cheryl. To make my computer’s name more unique, I decided to name it Lychrel as well, a name that related to two math concepts.

But what are the Lychrel numbers?

Pick a number, like 73. Now add it to its reverse. Keep doing this until the result is a palindrome. In the case of 73, we add 73 + 37 = 110, 110 + 011 = 121, which is a palindrome.

Now, some numbers take a few steps to become a palindrome, like 56. Some take several steps (89 takes 24). And there is strong evidence that some of them never become palindromes.

Numbers that never produce palindromes from this process are called Lychrel numbers. The first Lychrel number is (conjectured to be) 196.

The interesting thing is, though, that no number has been proven to be a Lychrel number in base 10.

Here is a site where a number can be tested for 300 iterations (just replace the 196 in the URL: https://jasondoucette.com/pal/196)

Bonus: Proof that the nth starter constant is always divisible by n!

Earlier this year, I think it was in February, I suddenly realized why the nth starter constant of the xth powers was always divisible by n! (n factorial).

First, assume that the nth is always divisible by n!. Let’s write the (n-1)st SC as a*(n-1)! and the nth as b*n!, where a and b are integers. This works for all n > 0. For n = 0, the nth SC is always either 1 (when x-1 = 0) or 0 (when x-1 > 0) so it is always divisible by 0!

Now, the formula for the nth starter constant of the xth powers is n times the sum of the (n-1)st and the nth starter constants of the (x-1)st powers. This is equal to n*(a*(n-1)! + b*n!), which can be simplified to (a + b*n)*n!. So, the nth SC of the xth powers is also divisible by n! But remember, this assumes that the same holds rue for the SC’s of the (x-1)st powers.

To complete this proof by induction, I will point out that as the first starter constant of the 0th powers is 1 and the others are all 0, then obviously the theorem holds true for x = 0. Yes, that’s all we need. Now we know that it holds true for all values of x!

QED.

My original proof of the Starter Constant Mystery

So I recently dug up my old piece of paper explaining my 2012 proof of the Starter Constant Mystery. I managed to decipher it and it turns out it was actually pretty simple.

Here is the proof:

Okay. Say you have a sequence x_0, x_1, x_2, x_3, x_4….* The nth term of this will be called x_n. We want to prove that:

If the kth starter constant for x_n is c_k, then the kth starter constant for n*x_n is k*(c_(k-1) + c_k) except when k = 0 in which case it is 0.

The first part is easy. When n = 0, n*x_n will also be 0, and as the 0th starter constant is also the same as the 0th term in the sequence, it will also be 0.

The following holds when k ≥ 1:

The formula for the kth starter constant is x_k - k*x_(k-1) + kC2*x_(k-2) - kC3*x_(k-3)…  ± x_0. where C means “choose”. This can also be written kCk*x_k - kC(k-1)*x_(k-1) + kC(k-2)*x_(k-2) - kC(k-3)*x_(k-3)….

We want to show that if x_n gets replaced by n*x_n, the formula will become:

kCk*k*x_k - (kC(k-1) - (k-1)C(k-1))*k*x_(k-1) + (kC(k-2) - (k-1)C(k-2))*k*x_(k-2)…

To prove this, it suffices to show equality between each term in the two series. Therefore, we want to show that kC(k-n)*(k-n)*x_(k-n) = (kC(k-n)-(k-1)C(k-n))*k*x_(k-n) for all n and k in the appropriate ranges.

Dividing x_(k-n) out and substituting k-n for n (which is allowed because n goes from 0 to k) gives us kCn*n = (kCn - (k-1)Cn)*k. This can be further reduced to kCn*n = (k-1)C(n-1)*k. Substituting n for (k-n) again we get kC(k-n)*(k-n) = (k-1)C(k-n-1)*k, which is the same as kCn*(k-n) = (k-1)Cn*k.

This is how far I got in spring 2012. I could have probably completed the proof any time I wanted, but I was waiting for a special event, which came on June 20, 2012.

We want to show that kCn*(k-n) = (k-1)Cn*k. I did this by constructing a (k-2)-dimensional simplex. Now, such a simplex has (k-1)Cn (n-1)-dimensional elements (this includes one -1-dimensional element). A (k-1)-dimensional simplex has k of these as facets. Therefore, exploding its facets outward such that each element is represented once on each facet gives (k-1)Cn*k (n-1) dimensional elements.

The simplex originally had kCn (n-1)-dimensional elements, each of which belongs to k-n facets. Since exploding the facets multiplies each element so that there is one copy for each facet**, it would multiply the number of (n-1)-dimensional elements by k-n to make kCn*(k-n) in total.

We just proved that the number of (n-1) dimensional elements is both kCn*(k-n) and (k-1)Cn*k and therefore  kCn*(k-n) = (k-1)Cn*k.This solves the Starter Constant Mystery.

QED.

*As I stated in last year’s post, tumblr’s post editor now makes subscripts cumbersome to insert into posts. This time I will be separating the would-be subscript from the variable using an underscore.

**Even the nullitope (-1-dimensional facet), which becomes k-0 = k nullitopes.

More last digits of powers

Let’s look at the second to last digits of powers.

In the post about last digits of powers, I proved that the last digits of the powers of any integer n will always repeat with a period of 4 (or some factor thereof). Now I will show that the last two digits of the powers of n will repeat with a period of 20, that is, that for sufficiently large x, n^(x + 20) - n^x will be divisible by 100.

First, if n^x and 100 are coprime for all x, n^(x + 20) - n^x can have n^x factored out of it and the result, n^20 - 1, will still be divisible by 100.

Also, if n^x is coprime to 100, every factor of n^x will also be coprime. Thus, if n is coprime to 100, then n^20 and n^x will always end in the same digit. Proving this will show that these values of n will have powers whose last two digits repeat with a period of 20.

Proof that powers of n mod 100 repeat after 20 steps

Okay, so we start with the numbers divisible by 5. Powers of these numbers above the first are always divisible by 25. Therefore, these powers always end in the digits 00, 25, 50, 75. If they are divisible by 2, they will also be divisible by 4, so this weeds out 50.

Also, these powers will only divisible by 2 if the base number is. This leads to the well-known fact that higher powers of anything ending in 0 will always end in 00. Since this has a period of 1, it repeats after 20 steps too.

If n ends in 5, even powers of n (above the zeroth) will always end in 25. This can be proven simply by realizing that all odd squares must be one more than multiples of 4. This narrows down the four possible sets of last two digits for multiples of 25 to just one: 25. If n itself is also one more than a multiple of 4, odd powers of n will also end in 25, Otherwise, if n is one less than a multiple of 4, its odd powers, being n times the even powers, will all have to be one less than multiples of 4 and therefore end in 75. This is easy to prove using arithmetic modulo 4.

So for n ending in 5, powers of n will repeat with a period of 1 if n mod 4 ≡ 1, and 2 otherwise. Therefore, powers of these numbers will also have last two digits repeating after 20 steps.

That was pretty easy. If you don’t have time to read through it all, the key points are:

1. Higher powers of numbers ending in 0 will always end in 00
2. Higher powers of numbers ending in 5 will always repeat endings 25, 75, 25, 75… or 25, 25, 25…
3. Therefore, for any number divisible by 5, the last two digits of its powers will repeat after 20 steps (in fact, even two steps).

That was easy. Now for the numbers not divisible by 5.

There is a wonderful theorem, that I have found without reading about anywhere, but I am sure has already been discovered. Here is one version of it:

If a and b are coprime integers, then the pair (x mod a, x mod b) will be different for all x such that 0 < x  ≤ a*b. Furthermore, if one knows these values, one can calculate the value of x mod a*b even if x is not in the range specified earlier.

This is very useful. What it means is that if we know a number’s residues mod 4 and mod 25, it can have only one possible residue mod 100. So if we can prove that the powers repeat after 20 steps when taken both mod 4 and mod 25, they will also repeat after 20 steps when taken mod 100.

Mod 4, powers of even numbers will be repeating 0s for all powers after the first. Even powers of odd numbers will be 1, and there odd powers of odd numbers will be the same as the odd number itself, either always 1 or always 3. Therefore, the modulo 4 residues of powers of n repeat after 2 steps, and therefore also repeat after 20 steps.

Under mod 25 arithmetic it’s more complicated.

As I have established in my previous post about last digits of powers, n^4 ≡ 1 mod 5 is always true except when n is divisible by 5. This comes from Fermat’s little theorem (not Fermat’s last theorem, mind you) and it means that n^4 mod 25 will be one more than a multiple of 5. If n^4 ≡ 5*a + 1 mod 25, what can we say about n^8? Well, n^8 must be congruent to (5*a + 1)^2 = 25*a^2 + 10*a + 1, which itself is congruent to 10*a + 1 = 5*(2*a) + 1. In fact, we can generalize. If n^(4*x) is congruent to 5*c + 1, n^(4*x + 4) is congruent to 5*(c + a) + 1 because (5*c + 1)*(5*a + 1) = 25*c*a + 5*(c + a) + 1 ≡ 5*(c + a) + 1 mod 25.

This means that n^(4*x) ≡ 5*(a*x) + 1. What does this say about n^20?

Why, n^20 ≡ 5*(4*5) + 1 = 100 + 1 = 101 ≡ 1 mod 25. Since n^20 ≡ 1 mod 25, then n^x will always have the same residue mod 25 as n^(x + 20).

We know that for odd n, n^x will always have the same residue mod 4 as n^(x + 20). This means that n^x will always have the same residue mod 100 as n^(x + 20)! This completes part of our proof.

For even n, n^x will have the same residue mod 4 as n^(x + 20) when x ≥ 2. Now we know that those numbers will also have the same residue mod 25, they will also have the same residue mod 100! This completes the other part of their proof.

We have proven that for sufficiently high x (now known to be for x ≥ 2), n^(x + 20) and n^x will have the same residue mod 100. Therefore, n^(x + 20) - n^x will be divisible by 100.

QED.

In the next section I will demonstrate how the proof can be altered to prove that n^(x + 100) - n^x is divisible by 1000 for x ≥ 3, and a (slightly unexpected) generalization to higher powers of 10.

Irrational primes!

Most people think of the primes as the numbers 2, 3, 5, 7… which are not divisible by any whole numbers other than one and themselves, and for the longest time this was true. But recently I have made a groundbreaking discovery that there is a load of new irrational primes between the integers.

So how do you find these?

Well, I started with Wilson’s Test, which says that an integer N (greater than one) is prime if and only if (N - 1)! is congruent to -1 modulo N. This means that, iff N is prime, ((N - 1)! + 1)/N should always be an integer.

Here are the first few of those integers for the first few integer primes:

p  ((p - 1)! + 1)/p
2  1
3  1
5  5
7  103
11 329891
13 36846277
17 1230752346353

But the statement, ((p - 1)! + 1)/p is only an integer when p is prime, naively assumes p must be an integer. Since factorials of irrational numbers are a very real thing, why can’t irrationals be prime too?

Let’s try plugging various integer values into X in the equation X = ((p - 1)! + 1)/p, and solving for p.

When X=1, we have two positive solutions for p: p=2 and p=3. Both are known primes.

When X=2, we have two positive solutions as well: p=1 and p=4.154439…

When X=3, the solutions are p=0.7443404… and p=4.562151…

When X=4, the solutions are p=0.6143126… and p=4.816165…

When X=5, the solutions are p=0.5330696… and p=5. One irrational prime and one integer one.

But between 5 and 7 there are 97 irrational primes, and between 7 and 11 there are 329787. Furthermore, there are an infinite number of them between 0 and 1. And there are 9.33 quinquagintillion between 1 and 100. But because there are infinitely more non-integer primes than integer primes, their discovery is definitely infinitely more important than integer than that of the integer primes!

Last Digits of Powers

Ever since I realized that n always ends in the same last digit as n^5, I have been fascinated by the last digits of powers.

I have now memorized hundreds of powers, such as the first 105 cubes, the first 57 4th powers, and the first 51 5th powers. In doing so I came to realize many patterns in their digits. For example, the last digit of the nth powers always repeats with a period of 10. When n is 1 mod 4, these digits are always 0, 1, 2, 3, 4, 5, 6, 7, 8, 9.

Here is why this happens. Fermat’s little theorem says that for a prime p and a number n not divisible by p, n^(p-1) ≡ 1 modulo p. This means that n^p ≡ n modulo p. As it turns out, this second result is also true when n is divisible by p; obviously, both are congruent to 0 mod p. Since n^p and n are congruent mod p, they end in the same last digits in base p.

Now let p = 5. We have now that n^5 ends in the same last digits as n, but this is only in base five. To extend this to base 10, we realize that n^5 and n are obviously congruent mod 2 as well, because one is even iff the other one is. Since any two numbers congruent mod 5 and 2 are also congruent mod 10, we have that n^5 and n are congruent mod 10.

Since n^5 and n end in the same last digit, it follows that for each n, n^4 is a number such that, when multiplied by n, ends in the same last digit as n. Since n^5 has the same last digit as n, n^5 multiplied by n^4 also has the same last digit as n. Multiplying by n^4 any number of times will yield the same last digit. Thus, the 9th powers, 13th powers, 17th powers, etc. all have the same last digits as the first powers.

The squares, 6th powers, etc. have their own shared set of last digits, of course, as do the cubes, 7th powers, etc. and the 4th, 8th etc. powers. For the squares the digit pattern is: 0, 1, 4, 9, 6, 5, 6, 9, 4, 1; for the cubes the pattern is: 0, 1, 8, 7, 4, 5, 6, 3, 2, 9; for the 4th powers the pattern is 0, 1, 6, 1, 6, 5, 6, 1, 6, 1.

Last digits of n ^ (4x) | x, n ∈ ℤ & x > 0

An interesting thing to note is that the last digits of the 4th, 8th… powers are not always 1–the last digit of the 0th powers–, even though 0 is the preceding member in the exponent sequence. This is because the powers beyond the 0th have special requirements for their last digits:

1. Since 2 is a factor of the base number, 10, every power of a multiple of two must end in an even digit.
2. Similarly, 5 is a factor of 10 so every power of a multiple of 5 must end in a digit which is a multiple of 5 (either 0 or 5).
3. Not a separate requirement, but every power of a multiple of 10 must fulfill both above rules, and therefore end in 0 because the only digit divisible by both 2 and 5 is 0.

2^4 must end in 2, 4, 6, or 8. The only choice that lets 2^5 end in 2 is 6. 4^4, 6^4, and 8^4 end in 6 as well. This happens because 2, 4, 6, 8, 12, etc., being divisible by 2 but not 5, have multiples whose last digits repeat with a period of 5. Since multiplying these numbers by anything ending in 1 results is a product with the same last digit, multiplying them by anything ending in 6 will create a number with the same last digit too. Multiplication by any number ending in something other than 1 or 6 will produce a number ending in a different digit. The 5th powers of these numbers will end in the same last digit as the first powers, so the 4th powers will end in 1 or 6. Since they (every number divisible by 2 but not 5) are all even, their 4th powers must end in 6.

Similarly, if n ends in 5, the only things n^4 can end in to make n^5 end in 5 are 1, 3, 5, 7, and 9. Since n^4 must be divisible by 5, it ends in 5. (Not to mention all powers beyond the zeroth of any number ending in 5 also end in 5.)

For numbers not divisible by 2 or 5, the only thing their 4th power can end in is 1. Here is why: If n is coprime to 10, multiples of n have last digits that repeat with a period of 10, instead of some factor. This means there is a one-to-one function that maps each digit 0-9 to the last digit of n times that digit. For example, when n=3, the digits 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 map to 0, 3, 6, 9, 2, 5, 8, 1, 4, 7. Since the function is one-to-one, for any numbers divisible by n that end in the same last digit (such as n and n^5), their results of division by n must also have common last digits (in this case, 1 and n^4.) This means that n^4 must end in 1 for all n coprime to ten; that is, all n ending in 1, 3, 7, and 9–just like n^0.

Putting it all together, we have that n^4 ends in:

• 1 if n ends in 1, 3, 7, or 9
• 6 if n ends in 2, 4, 6, or 8
• 5 if n ends in 5
• 0 if n ends in 0.

That’s plenty to know about patterns the last digits of powers. On to the last two digits!

So in my last post, we figured out that when the heptagonal tiling gets taken by “layers”, that is, a ring of heptagons completely surrounding the outside of the previous ring, which surrounds another ring etc., all the way down to one heptagon, the number of heptagons in each ring is 1 followed by 7 times alternate Fibonacci numbers:

[1, 7, 21, 56, 147, 385, 1008, 2639, 6909, 18088…]

We also figured out (with the exception of the zeroth layer) that each heptagon in one layer always corresponds to between two and three in the next layer, which means the each layer has between two and three times as many as the previous layer. In fact as the number of heptagons grows large, the ratio between the number in adjacent layers approaches (3 + √5)/2, which can be derived directly from the way the terms are based off the Fibonacci numbers.

What happens if we try higher hyperbolic tilings, like the octagonal, nonagonal, and decagonal tilings?

Here is a picture of the octagonal tiling, {8, 3}:

The first layer is one octagon, the second is a ring of eight, and by counting you can see that the third layer has 32, but after that it’s hard to tell just by eyeballing the figure.

Fortunately, we can see that just like the heptagons in the previous post, the octagons (again, omitting the central one) come in two types. Besides the two octagons they touch in their current layer, they touch either one or two from the previous layer.

The kind of octagon that touches one from the previous layer has 5 sides left to touch. We can call these “5″s.

The kind that touches two from the previous layer has only 4 sides left so we can call them “4″s.

We can see that “4″s spring from a boundary between two octagons on the previous layer, and “5″s are in between, touching only one from the previous layer.

So if each layer is given by a string of “4″s and “5″s, the next layer will have “4554″ for each “4″ and “45554″ for each “5″. “4″s from adjacent rows will overlap. For example, if one layer contained:
“45455”
the next layer would have:
“4554555455455545554″
in its place.

But since the “4″s overlap, each “4″ becomes “455″, and each “5″ becomes one “4555″. There will be no “missing” 4 at the end because the pattern is cyclic.

So if there are A “4″s and B “5″s in one row, there will be A + B “4″s and 2A + 3B “5″s in the next row. This means we can calculate the number of octagons in each layer, by repeatedly substituting A for A + B, and B for 2A + 3B, and calculating A + B.

Here is a table of how many type-”4″, type-”5″, and total polygons there are in each layer.

Layer#  Type-”4″  Type-”5″  Total
1           0              8             8
2           8              24           32
3           32            88           120
4           120          328         448
5           448          1224       1672
6           1672        4568       6240
7           6240        17048     23288

There is an easier way to calculate these numbers. Just like the heptagonal tiling numbers were 7 times alternate Fibonacci numbers, we can use a similar “bootstrapping” rule here, where each term (beyond the first few) is defined solely from its previous two terms.

If each term is A + B, the next term is (A + B) + (2A + 3B) and the term after that is ((A + B) + (2A + 3B)) + (2(A + B) + 3(2A + 3B)). These simplify to 3A + 4B and 11A + 15B. Since 11A + 15B is just 4(3A + 4B) - (A + B), we can calculate each term as four times the previous term, minus the term before that…

…except if either of those terms is “1″, as the zeroth layer is a special case.

So the sequence stars 1, 8, 32 and every subsequent term is four times the previous, minus the previous still. The ratio between successive terms approaches 2+√3.

[1,8,32,120,448,1672,6240,23288,86912,324360,1210528,4517752…]

The next tiling is the nonagonal tiling, also called the order-3 nonagonal tiling or the enneagonal tiling. As you can probably guess, this tiling consists of nonagons meeting three at a vertex.

We can define layers starting from an arbitrary central nonagon, and then categorize the nonagons as either “5″s or “6″s, depending on whether they touch 5 or 6 from the next layer.

Since each “5″ becomes “5666″ and each “6″ becomes “56666″, then:

if there are A “5″s and B “6″s in one layer, there are A + B “5″s and 3A + 4B “6″s in the next layer. So there are A + B in one layer, 4A + 5B in the next, and 19A + 24B = 5(4A + 5B) - (A + B) in the next. So the bootstrapping rule for the nonagonal tiling is:

The 0th term is 1.
The 1st term is 9.
The 2nd term is 45.
Every subsequent term is five times the previous term, minus the previous still.

The ratio between terms approaches (5+√21)/2.

[1,9,45,216,1035,4959,23760,113841,545445,2613384,12521475…]

And so on…

General formula

The bootstrapping formula for the coordination sequence (as this is what the OEIS called what I am describing) of the p-gonal tiling, for p ≥ 6, can be derived by noticing polygons of type “p-4″ which touch two from the current and two from the previous layer, and polygons of type “p-3″ which touch two from the current and one from the previous layer.

A + B polygons in one layer then become (p - 5)A + (p - 4)B in the next layer and (p^2 - 9p + 19)A + (p^2 - 8p + 15)B in the next layer still. If
A + B = x,
(p - 5)A + (p - 4)B = y, and
(p^2 - 9p + 19)A + (p^2 - 8p + 15)B = z,
then it can be stated that (p - 4)y = x + z.

I bolded this formula to emphasize how important it was. This gives us a formula for the coordination sequence of any regular tiling {p, 3}. The formula is this:

First start with 1, followed by p and p^2 - 4p. Then, each following term in the sequence is (p - 4) times the previous term minus the previous term still.

And the ratio between adjacent terms approaches (n-4+√(n^2-8n+12))/2.

Table

Finally, here is a table of the first 10 terms in each coordination sequence up to p = 37:

[1, 3]
[1, 4, 1]
[1, 5, 5, 1]
[1, 6, 12, 18, 24, 30, 36, 42, 48, 54…]
[1, 7, 21, 56, 147, 385, 1008, 2639, 6909, 18088…]
[1, 8, 32, 120, 448, 1672, 6240, 23288, 86912, 324360…]
[1, 9, 45, 216, 1035, 4959, 23760, 113841, 545445, 2613384…]
[1, 10, 60, 350, 2040, 11890, 69300, 403910, 2354160, 13721050…]
[1, 11, 77, 528, 3619, 24805, 170016, 1165307, 7987133, 54744624…]
[1, 12, 96, 756, 5952, 46860, 368928, 2904564, 22867584, 180036108…]
[1, 13, 117, 1040, 9243, 82147, 730080, 6488573, 57667077, 512515120…]
[1, 14, 140, 1386, 13720, 135814, 1344420, 13308386, 131739440, 1304086014…]
[1, 15, 165, 1800, 19635, 214185, 2336400, 25486215, 278011965, 3032645400…]
[1, 16, 192, 2288, 27264, 324880, 3871296, 46130672, 549696768, 6550230544…]
[1, 17, 221, 2856, 36907, 476935, 6163248, 79645289, 1029225509, 13300286328…]
[1, 18, 252, 3510, 48888, 680922, 9484020, 132095358, 1839850992, 25625818530…]
[1, 19, 285, 4256, 63555, 949069, 14172480, 211638131, 3160399485, 47194354144…]
[1, 20, 320, 5100, 81280, 1295380, 20644800, 329021420, 5243697920, 83570145300…]
[1, 21, 357, 6048, 102459, 1735755, 29405376, 498155637, 8439240453, 142968932064…]
[1, 22, 396, 7106, 127512, 2288110, 41058468, 736764314, 13220699184, 237235820998…]
[1, 23, 437, 8280, 156883, 2972497, 56320560, 1067118143, 20218924157, 383092440840…]
[1, 24, 480, 9576, 191040, 3811224, 76033440, 1516857576, 30261118080, 603705504024…]
[1, 25, 525, 11000, 230475, 4828975, 101178000, 2119909025, 44416911525, 930635233000…]
[1, 26, 572, 12558, 275704, 6052930, 132888756, 2917499702, 64052104688, 1406228803434…]
[1, 27, 621, 14256, 327267, 7512885, 172469088, 3959276139, 90890882109, 2086531012368…]
[1, 28, 672, 16100, 385728, 9241372, 221407200, 5304531428, 127087347072, 3044791798300…]
[1, 29, 725, 18096, 451675, 11273779, 281392800, 7023546221, 175307262725, 4375658021904…]
[1, 30, 780, 20250, 525720, 13648470, 354334500, 9199048530, 238820927280, 6200145060750…]
[1, 31, 837, 22568, 608499, 16406905, 442377936, 11927797367, 321608150973, 8671492278904…]
[1, 32, 896, 25056, 700672, 19593760, 547924608, 15322295264, 428476342784, 11982015302688…]
[1, 33, 957, 27720, 802923, 23257047, 673651440, 19512634713, 565192755237, 16371077267160…]
[1, 34, 1020, 30566, 915960, 27448234, 822531060, 24648483566, 738631975920, 22134310794034…]
[1, 35, 1085, 33600, 1040515, 32222365, 997852800, 30901214435, 956939794685, 29634232420800…]
[1, 36, 1152, 36828, 1177344, 37638180, 1203244416, 38466183132, 1229714615808, 39312401522724…]
[1, 37, 1221, 40256, 1327227, 43758235, 1442694528, 47565161189, 1568207624709, 51703286454208…]

Let’s look at the dodecahedron. It has 12 pentagonal faces, 3 meeting at every vertex. Here is a depiction of it using a type of projection called a Schlegel diagram:

It is clear that any face touches 5 other faces at the edges, in a ring. These are marked “X” in the picture:

Furthermore, those 5 faces touch 5 more faces that the first face doesn’t touch.

Finally, those faces touch 1 last face, making 12 in total.

Separation

Let’s define the separation of any two faces to be the minimum number of faces needed to traverse to go from one from the other, including the destination but not the source. We can see that given any face of the dodecahedron:

• 1 face will have separation 0 (the given face itself),
• 5 faces will have separation 1,
• 5 faces will have separation 2,
• and 1 face will have separation 3.

This gives us a sequence: [1, 5, 5, 1].

Schlafli symbols

The Schlafli symbol of a regular polyhedron is an ordered pair of numbers. For a convex polyhedron, the first number represents the number of sides on each face and the second the number of edges (and thus faces) around each vertex. Thus the dodecahedron’s Schlafli symbol is {5, 3}.

If three faces meet around every vertex of a polyhedron, every two faces touching at a vertex will also touch at an edge. Thus, every time we add a layer of faces (as we did above for the dodecahedron) we completely cover the previous layer, leaving no more faces able to be inserted next to the it, even if they only touch at the vertices.

So what happens if we try calculate the separation of faces of other polyhedra with Schlafli symbols of {x, 3}? Here are the results for the cube, whose Schlafli symbol is {4, 3}:

We can see that for a given face there is 1 face at separation 0, 4 at separation 1, and 1 at separation 2, so the cube defines the sequence:
[1, 4, 1]
akin to [1, 5, 5, 1] for the dodecahedron.

Similarly, the tetrahedron has the symbol {3, 3}. The tetrahedron is unique among the Platonic solids because faces are opposite vertices, instead of faces. Therefore, the last layer will not be a “lid” made of one single face (like it was for the cube and dodecahedron), but a cap of three triangles instead.

Here is the separation diagram for the tetrahedron. In the picture, the three edges that travel off the screen all meet at one vertex.

From this we can derive the sequence [1, 3].

So, the sequences of how many polygons are in each layer of the tetrahedron, cube, and dodecahedron go:

[1, 3]

[1, 4, 1]

[1, 5, 5, 1]

for the Schlafli symbols {3, 3}, {4, 3}, and {5, 3}.

More than 5 sides

What about {6, 3}? By the definition of the Schlafli symbol {6, 3} should be a polyhedron made of hexagons, with three meeting at every vertex.

But it can’t be a Platonic solid, because those only have triangles, squares, or pentagons.

Let’s build it layer by layer and see what it is.

It starts with one hexagon, which gets surrounded by six more.

The next layer has 12 hexagons.

And the next one has 18.

It is clear now that each layer will have six more hexagons than the layer before, as each of the six sides gets longer by one at a time. It is also clear that the resulting figure is not a Platonic solid because it is infinite – in fact, it is the regular hexagonal tiling.

And the relevant sequence is: [1, 6, 12, 18, 24, 30, 36…]. This and all the following sequences will be infinite.

Hyperbolic tessellations

While the Platonic solids are tessellations of a sphere, the hexagonal tiling is a tessellation of a flat (Euclidean) plane. This is apparent from its depiction above; while the Platonic solids had to be distorted to project onto the flat screen, the hexagonal tiling can tessellate with perfectly regular hexagons.

In order to realize the Schlafli symbols {n, 3}, with n being an integer larger than 6, we need to tile with convex polygons 7 sides or greater, 3 to a vertex, For this a new type of surface is needed, called a hyperbolic surface.

Unlike spherical and Euclidean surfaces, there is no manifestation of a uniform hyperbolic surface in 3 dimensions such that every point looks the same as every other. Similar to how the projections of spherical polyhedra had faces that appeared larger farther away from the center, projections of hyperbolic tilings will have faces that appear smaller farther away from the center. Also, since the angles of the three polygons that meet at each vertex get bigger, space needs to expand out faster than quadratically when distance grows linearly. Thus while the number of polygons per layer grew and then shrunk for polyhedra, and grew linearly for the hexagonal tiling, it will grow superlinearly for hyperbolic tilings.

{7, 3}

The order-7 heptagonal tiling, sometimes just called the heptagonal tiling, has a Schlafli symbol of {7, 3}. Here are the first three layers, with [1, 7, 21] heptagons respectively:

The fourth layer has 56 heptagons:

We can see the number of heptagons in each layer grows superlinearly. Upon closer inspection, each heptagon in one layer touches a run of either three or four heptagons in the next layer. But the heptagons at the beginning and end of each run touch two from the previous layer. Let’s say that each heptagon in the first layer or beyond “corresponds” to the one or two heptagons that only it touches, plus the one that it shares with its left neighbor on the same layer. For example, the yellow heptagon marked in blue corresponds to the three green heptagons marked in blue, and the yellow heptagon marked in purple corresponds to the two green heptagons marked in purple:

It is now apparent that each heptagon in one layer corresponds to two in the next if it has three free sides, or three if it has four. This means that, after the first layer, the number of heptagons per layer grows exponentially with each layer having between two and three times more than the last.

To find a formula for the number of heptagon, notice that the diagram has heptagonal symmetry (slightly distorted in the projection) about the central heptagon. This means that each point gets repeated seven times across the figure (unless it’s in the center), and therefore, every layer after the zeroth has a multiple of seven heptagons in it.

So let’s try looking at a seventh of each layer, using a special notation to write out rings of heptagons. In this notation, each number represents one heptagon, describing the number of “free” sides on the heptagon (that is, the number of sides that don’t get touched by members of its own layer of previous layers). Numbers in brackets are repeats of numbers from the previous or the next of the sever copies.

So the first layer would be represented by: [4] 4 [4], because there are seven copies of one heptagon with four free sides.

The next layer would be [4] 3 4 4 [3]. This means that there are 21 heptagons, repeating 3, 4, 4, 3, 4, 4, 3, 4, 4, 3, 4, 4, 3, 4, 4, 3, 4, 4, 3, 4, 4 sides, or 7 runs of (3, 4, 4).

The third layer would be represented by [4] 3 4 3 4 4 3 4 4 [3]. Since the middle (excluding the bracketed numbers, which are repeats) has 8 terms, there are 7 * 8 = 56 heptagons in the third layer.

If you haven’t figured it out by now, in each layer the number 3 becomes (3, 4) in the next layer, and 4 becomes (3, 4, 4). This is because each “3″ heptagon touches two from the previous layer, and each “4″ heptagon touches one from the previous layer. So each “3″ in layer n touches three heptagons “3 4 3″ in layer n + 1 but only corresponds to “3 4″ because the final “3″ in layer n + 1 also touches the next heptagon in layer n.

A similar situation occurs when “4″ becomes “3 4 4″.

So what’s the number of heptagons in each layer? Well, if there are A “3″s and B “4″s, there will be A + B “3″s and A + 2B “4″s in the next layer. So if one layer (past the zeroth, which follows different rules) has A + B heptagons, the next will have

(A + B) + (A + 2B) =
2A + 3B heptagons, the next will have

((A + B) + (A + 2B)) + ((A + B) + 2(A + 2B)) =
(2A + 3B) + (3A + 5B) =
5A + 8B heptagons, the next will have

((2A + 3B) + (3A + 5B)) + ((2A + 3B) + 2(3A + 5B)) =
(5A + 8B) + (8A + 13B) =
13A + 21B heptagons, and so on.

We can see that the coefficients of A are every other Fibonacci number, and the coefficients of B are the other ones. In fact, if one layer has

(F_n*A + F_{n + 1}*B)

heptagons of type “3″ and

(F_{n + 1}*A + F_{n + 2}*B)

of type “4″, making

(F_{n + 2}*A + F_{n + 3}*B)

in total, the next layer will have

(F_{n + 2}*A + F_{n + 3}*B)

of type “3″, and

(F_{n + 3}*A + F_{n + 4}*B)

of type “4″, making

(F_{n + 4}*A + F_{n + 5}*B)

in total, with the next two Fibonacci numbers, so by induction the pattern continues.

So how many heptagons are there in each layer? If we start on the first layer, with A = 7 and B = 0, we get:

7, 21, 56, 147, 385, 1008, 2639, 6909, 18088, 47355…

or seven times the Fibonacci numbers with even index. Adding “1″ to the beginning for the zeroth layer gives sequence A001354, for the number of heptagons in each layer. Also, since the ratio of two consecutive terms approaches (3 + √5)/2, the number of heptagons per layer increases by about 2.62%.

I will discuss higher hyperbolic tilings in a follow-up post, as this post is getting too long.

When does n have the same digits as 2n?

As you may know, the number 142857 has a very interesting property:

A number n’s cyclic permutations are, loosely speaking, the numbers you can get by chopping digits of the end of n and sticking them on the beginning. 142857 is the first number which is a cyclic permutation of its own double (and also happens to be a cyclic permutation, its triple, quadruple, quintuple, and sextuple).

Let’s ask a broader question: when does a number contain the same digits as its double, in any order?

First let us look at 142857 and its double, 285714.

142857
285714

We will trace a path from each digit in 142857 to the digit directly below it in 285714, and then find the corresponding digit in 142857 and repeat:

1->2->5->1->2->5->1…

And if you start with 4:

4->8->7->4->8->7->4…

So what do we notice? For each digit in the cycle d:

• If d < 5, the next digit is either 2*d (if even) or 2*d + 1 (if odd)
  
• If d ≥ 5, the next digit is either 2*(d - 5) or 2*(d - 5) + 1

We also note that each digit d in 142857 is directly above an odd digit in 285714 if the digit to the right is 5 or greater (because it carries when it doubles), and is directly above an even digit otherwise.

We can mark each digit with the symbol < if it carries to the left when it doubles, and > if a carried 1 from the right gets added to its double. Then the pair looks like this:

1  4  2  8  5  7
        > <><> <
2  8  5  7  1  4

For example, 8 “doubling” to 7 gets both symbols, because it both carries a one (16->6) and adds a carried one from the next column (6->7).

We notice that each > is immediately followed by a <. This makes sense, as they both refer to the same carried 1.

Now we can put the symbols in our 3-digit cycles, putting > at the end and < at the beginning:

1
2>
<5>

and:

4
<8>
<7.

Now comes the fun part: We can put these six numbers together in any way we want, as long as each > gets followed by a <. The resulting number is always an anagram of its double. The smallest possible result is 125874:

12><5><8><74, where the angle brackets point to carried 1s, which you can get by combining the symbols above. Its double is 251748.

I have searched every possible cycle of digits following the same rules as 1-2-5-1… and 4-8-7-4… (which are: n becomes 2n or 2n+1, mod 10), and it appears 125874 is the shortest possible.

New proof of the Starter Constant Mystery

This is a follow-up to my earlier post about starter constants.

As you may recall, I had already just proved the second starter constant mystery, which was:

The A-th starter constant of the B-th powers is really the number of A-digit strings (I’m not calling them numbers, because the first digit can be 0 and it is still considered to have A digits), that use every digit from 0 to B - 1.

(Actually I explained it in terms of taking cards from a stack, but this is an equivalent definition I was using later on.)

I thought that this might lead to a simpler proof of the first starter constant mystery, and I was right! To review, here is the first starter constant mystery says that you can get the starter constants for x*f(x) from those of f(x) this way:

List the starter constants for f(x) starting at x = 1, and append an extra number to the beginning (any number will do).

This can be accomplished by taking the starter constants from x = 0 and adding adjacent terms as in Pascal’s Triangle to form a string of numbers one longer.

Multiply the nth term (starting from the top at n = 0) by the number n.

You now have the starter constants for x*f(x), starting at x = 0.

So, if f(x) has n starter constants, including the a at the beginning, which are:

a, b, c, d… y, z

where a is f(0), the starter constants for x*f(x) are:

0, a + b, 2*(b + c), 3*(c + d)… (n - 1)*(y + z) + n*z

This is especially useful for determining the starter constants of x*(n + 1) from those of x^n. Starting w/ 1, 0, 0, 0… as the starter constants of x^0 = 1 (0 is the starter constant when you get past a constant sequence, and will subsequently be omitted), we get:

0,1 as the starter constants of the 1st powers,

0,1,2 as the starter constants of the squares,

0,1,6,6 as the starter constants of the cubes,

0,1,14,36,24 as the starter constants of the 4th powers,

0,1,30,150,240,120 as the starter constants of the 5th powers,

0,1,62,540,1560,1800,720 as the starter constants of the 6th powers, and so on.

I wrote down a proof for this in June 2012, but it was complicated and I don’t remember what it is at the moment. However, the second starter constant mystery allowed me to construct another proof of this for the case of x^n by viewing the starter constants as sets of digit strings, just in time for the third anniversary of the original proof.

First consider the function SC(a, b), which is the b-th starter constant for the a-th powers. For example: SC(3, 2) is 6, the second term on the third row of the table above (counting the 0 at the beginning of each row as the 0th starter constant, as always). We need to prove that:

• SC(a, 0) = 0 for a > 0
• SC(0, b) = 0 for b > 0
  
• SC(0, 0) = 1
  
• SC(a + 1, b + 1) = (b + 1)*(SC(a, b) + SC(a, b + 1)) for a and b positive.
  

The first is trivial as the 0th starter constant of f(x) is always f(0), and the second and third are trivial as we know the starter constants of x^0 are 1, 0, 0, 0, 0….

The third can be found by realizing that SC(a + 1, b + 1) is the number of (a + 1)-digit strings in base (b + 1) that use all digits in base (b + 1) from 0 to b. Since every digit is used equally and there are (b + 1) different digits, there are SC(a + 1, b + 1)/(b + 1) strings w/ the same first digit, say b.

Since the first digit is always b, SC(a + 1, b + 1)/(b + 1) is also the number of a-digit strings formed by taking the b off the beginning of each of these (a + 1)-digit strings. Since the original (a + 1)-digit strings had to include every digit, these a-digit strings come in two types:

• Those that include every digit from 0 to b, because the original string included b more than once
• Those that include every digit from 0 to b - 1, but not b, because the only occurrence of b in the original string at the beginning

But by the second starter constant mystery, the number of strings of the first type is just SC(a, b + 1), while the number of strings of the second type is just SC(a, b). So we have that SC(a + 1, b + 1)/(b + 1) = SC(a, b) + SC(a, b + 1), or SC(a + 1, b + 1) = (b + 1)*(SC(a, b) + SC(a, b + 1)). QED.

Starter Constants & Mysteries

Introduction

For a long time, about 10 years now (!), I have been interested in what happens when you take differences between adjacent terms in a sequence, for example:

0, 1, 4, 9, 16, 25, 36, 49…
1, 3, 5, 7, 9, 11, 13…
2, 2, 2, 2, 2, 2…

where the first sequence is y = n^2, and each successive sequence is the difference between adjacent terms in the previous sequence. Taking any further differences produces the zero function, y = 0.

We can do this for any sequence f(n), where f1(n) = f(n+1) - f(n), f2(n) = f1(n+1) - f(n), and in general f_x(n) = f_x-1(n+1) - f_x-1(n), until for some value of x f_x(n) = k, for some constant k. (I won’t be using the subscripts much, because tumblr recently made it very hard to insert any kind of formatting into a post, which is why the sequences above aren’t in a monospace font, even though they should be.)

Specifically, I have been interested in the first terms in these sequences (what I call “starter constants”), that is, f(0), f1(0), f2(0), and looking for patterns in them. Here is what I found.

Starter constants of powers

My main objective was to find a pattern among the starter constants of n^k, for integers k, akin to Pascal’s triangle or something. This was partially because they were increasingly hard to calculate for higher values of k, but also because just by looking at them they seemed to be filled with patterns that I couldn’t find. Here is the difference table for the 4th powers:

0, 1, 16, 81, 256, 625 1296, 2401…
1, 15, 65, 175, 369, 671, 1105…
14, 50, 110, 194, 302, 434…
36, 60, 84, 108, 132…
24, 24, 24, 24…

so the starter constants are 0, 1, 14, 36, 24.

(Historical note: I used to calculate the starter constants starting at f(1), so I would have computed this as: 1, 15, 50, 60, 24. How they change with different “offsets” of the same sequence will become relevant later.)

The first things I noticed were that the nth powers have n! as their last starter constant, and 0, 1, and 2^n - 2 as their first three. But for a long time I couldn’t find any other patterns.

A new approach

Flash forward to 2011. I was just getting out of the shower when I suddenly realized that the SC’s for the cubes – 0, 1, 6, and 6 – were divisible by 0, 1, 2, and 3 respectively. I tried dividing the last 3 by 1, 2, and 3, and I got:

1, 3, 2

Suddenly I realized something. 1, 3, AND 2 WERE JUST THE STARTER CONSTANTS OF THE SQUARES WHEN YOU STARTED AT 1^2 INSTEAD OF 0!!!! I wondered if the same thing worked for other powers. So I tried the fourth power SC’s – 0, 1, 14, 36, 24 – and I got 1, 7, 12, and 6, which were indeed the starter constants of (x + 1)^3!

I finally had what seemed to be a method for getting the n+1st power starter constants from the nth ones, and indeed the starter constants of n*f(n) from those of f(n) for any sequence f(n). Here is how it works:

1. List the SC’s for f(x) starting at x = 1, and append an extra number to the beginning (any number will do).
   This can be accomplished by taking the SC’s from x = 0 and adding adjacent terms as in Pascal’s Triangle to form a string of numbers one longer.
2. Multiply the nth term (starting from the top at n = 0) by the number n.
3. You now have the SC’s for x*f(x), starting at x = 0.

For example, say you have a sequence with the SC’s 7, 3, 5, 4.

The difference table for such a sequence would go like this:

7, 10, 18, 35, 65, 112… (sequence itself)
3, 8, 17, 30, 47… (first differences)
5, 9, 13, 17… (second differences)
4, 4, 4… (third differences, constant sequence)

Adding adjacent starter constants gives you:

7, 10, 8, 9, 4

Now multiply by 0, 1, 2, 3, 4:

0, 10, 16, 27, 16.

Which gives the sequence:

0, 10, 36, 105, 260, 560, 1080…

And the differences:

10, 26, 69, 155, 300, 520…
16, 43, 86, 145, 220…
27, 43, 59, 75…
16, 16, 16…

which is indeed x*f(x)!

But I still didn’t have a proof that it always worked. And that, I knew, is what would solve the mystery.

The starter constant mystery gets solved

In spring 2012, I started making good progress on solving the starter constant mystery, and finally, on June 20, 2012, I solved it! The proof is too long to write here, but all my logic is written down on pieces of paper in my room.

Also, I’ll probably be writing another proof soon. More on that later.

Uses in algebra

Knowing the SC’s for the powers is very useful. Say we know a sequence by its SC’s, and we want to figure out its polynomial. We can form the SC’s by adding scaled versions of the SC’s for the powers, and the scaling factors will be the coefficients for the polynomial. For example, say we wanted to find the polynomial for our sequence earlier, with the SC’s 7, 3, 5, 4.

First of all, since 0, 1, 6, 6 are the SC’s for the cubes, 0, 2/3, 4, 4 are the SC’s y = 2/3*x^3.
0, 1, 2 are the SC’s for the squares, so 0, ½, 1 are the SC’s for y = ½*x^2, and adding this to 2/3*x^3 with the SC’s 0, 2/3, 4, 4 gives us 0, 7/6, 5, 4, the SC’s for y = 2/3*x^3 + ½*x^2.
0, 11/6 are the SC’s for y = 11/6*x, so 0, 3, 5, 4 are the SC’s for y = 2/3*x^3 + ½*x^2 + 11/6*x.
And finally, 7 is the SC for y = 7, so 7, 3, 5, 4 are the SC’s for y = 2/3*x^3 + ½*x^2 + 11/6*x + 7. It is common for polynomials that generate integers to have non-integer coefficients like this.

If you know the SC’s of a polynomial f(x), it is also possible to figure them out for f(x)/x, assuming f(x)/x reduces to a polynomial itself. To do this we just have to apply the method for finding the SC’s of x*g(x) based on those for g(x) in reverse:

Say the SC’s for f(x) are 0, a, b, c, d … m, n. (The first one has to be 0 in order for f(x) to be divisible by x.) Then this is how the SC’s for f(x)/x are found:

Divide a by 1, b by 2, c by 3… all the way up to n by i[n], where i[n] is the index of n, and replace the zeroth SC by the undefined value 0/0. You should get 0/0, a, b/2, c/3, d/4, … n/i[n].

Now replace each term (except for 0/0) by the alternating sum of the terms from it to i[n], to get (from bottom to top):

n/i[n]

(n-1)/i[n-1] - n/i[n]

(n-2)/i[n-2] - (n-1)/i[n-1] + n/i[n]

all the way up to…

a - b/2 + c/3 … ± n/i[n].

These are the SC’s for f(x)/x, with a - b/2 + c/3 … ± n/i[n] being the zeroth and working upward.

Except for one thing. The zeroth SC of a sequence s(x) is always equal to s(0). But f(0)/0 is undefined. As it turns out, the zeroth SC here:

a - b/2 + c/3 … ± n/i[n]

is the limit of f(x)/x as x goes to 0. So this is also a way to find the limit of f(x)/x as x goes to 0, by looking at just the SC’s.

A surprising theorem

“If f(x) is a polynomial sequence with integer starter constants and f(0) = 0, then for only a finite number of primes p will f(p)/p not be an integer.”

This certainly surprised me, the fact that you could take any sequence of integers and, as long as there were a finite number of SC’s and the zeroth one was 0, high enough primes p would always be factors of the pth term in the sequence. For example:

0, 1, 8, 28, 68, 135, 236, 378…
1, 7, 20, 40, 67, 101, 142…
6, 13, 20, 27, 34, 41…
7, 7, 7, 7, 7…

28 is not divisible by 3, but 8/2 = 4, 135/5 = 27, 378/7 = 54, and all higher primes will divide their terms too.

To see why this works, look at the SC’s for f(x)/x (or, more precisely, the limit of f(h) over h as h -> x). From the formula given above:

n/i[n]

(n-1)/i[n-1] - n/i[n]

(n-2)/i[n-2] - (n-1)/i[n-1] + n/i[n]

…

a - b/2 + c/3 … ± n/i[n].

it is clear that the denominator of the gth SC will be a factor of the product of the integers from g to i[n], as it is formed by adding fractions with denominators from g to i[n]. (Remember a, b, c … n are the SC’s of the original function, which we specified were integers.) But all of the denominators are factors of i[n]! (and also the LCM of the integers from 1 to i[n]), so the denominators of the terms themselves are factors of that number too. But for any prime number p which cannot be a factor of the denominator, f(p) is an integer and so the denominator of the simplest form of f(p)/p must be a factor of p. But since p is not a factor of the maximum possible denominator, the only number that can be a factor of both is 1. So the simplest form of f(p)/p has a denominator of 1, and is therefore an integer. This can be repeated for all primes the denominators are not divisible by, which is all but a finite number of primes.

The second starter constant mystery

Back to the mysteries. In April 2015, almost 3 years after solving the original starter constant mystery, I happened to be searching for starter constant of the 6th powers when I found the triangle of SC’s, read line by line, as sequence A090582 in the OEIS! The description they gave was:

Numerator Q(m,n) of probability P(m,n)=Q(m,n)/n^m of seeing each card at least once if m>=n cards are drawn with replacement from a deck of n cards, written in a two-dimensional array read by antidiagonals with Q(m,m) as first row and Q(m,1) as first column.

That was strange. They had the exact same elusive sequence, but with a different definition! Maybe I could prove the two definitions were equivalent and get another way to calculate the SC’s. I might even be able to find a simpler proof of the original starter constant mystery!

I translated their definition, and made the following conjecture:

“The bth starter constant of the ath powers is the number of ways to choose a cards from a stack of b, with replacements, and get every single card.”

I knew this was true when b = 1, because there is only one way to choose one card from a set of a cards, no matter what a is. I also knew it was true for b = 2, because the 2nd SC of the ath powers is 2^a - 2, and out of the 2^a ways there would be to choose and replace a cards from a deck of two, the only two that wouldn’t get both cards chosen were selecting the same card repeatedly, making 2^a - 2 ways to get both cards.

So I tried to prove this for all values of a and b. After hitting a dead end about summation of binomial coefficient products, I decided to take a break, but on June 2, 2015, I suddenly had a glorious insight that led to a solution!

Proof of the second SCM

First of all, I will henceforth explain this in terms of “strings of a digits in base b” instead of choosing and replacing a cards from a set of b, to emphasize that the order of the card-choosing matters, and to number every card in the set from 0 to b-1.

Okay. So first of all, the number of a-digit strings in base b is b^a. (Here, when we say “a-digit strings”, we mean “strings of a or less digits”, i.e. the first digit can be 0, analogous to the choosing of cards. Or we could be using definite-length base b, with digits 1 through b - see the last post.) If a holds a constant value (not to be confused with the property of being a starter constant), which it will throughout the proof, then y = b^a is a function determining the number of a-digit strings in base b. That’s pretty obvious, isn’t it?

Even when b = 0, the range of digits 0 ≤ d < b is the null set, which means there are 0 possible a-digit strings. So that works out too.

Now let’s study the differences between the nth set and the (n-1)st set.
Since each digit string in the set of digit strings for base b is also in the set for base b+1, the cardinality of the differences between the two sets is the difference of the cardinalities, or in other words, (b+1)^a - b^a.

What would this set represent? Why, it would represent the digit strings that used only digits in base b+1, but did not use only digits in base b. In other words, it was the set of digit strings that used only digits from 0 to b, and included b.

So there are (b+1)^a - b^a strings of digits in base b+1, that use the digit b. This is actually the number of strings in base b+1 that have one fixed digit, no matter what it is. Substituting b for 0, we can see that this is also the number of base-b+1 digit strings that use the digit 0.

For b = 0, this describes the 1st SC (= 1^a - 0^a) as the number of base-1 strings that use the one specific digit, say 0; that is, all base-1 strings, because 0 is the only digit they can use. But this is also the number of base-1 strings that use every digit. So we proved the (trivial) case of our theorem for b = 1.

Let’s call x^a f(x). Now (b+1)^a - b^a = f1(b), from the notation at the beginning, and f1(b+1) - f1(b) = f2(b). We want to prove that f2(0) is the number of base-2 a-digit strings that use both digits 0 and 1.

First notice that since f1(b) represents the number of base-b+1 strings using 0, f2(b) represents the number of base-b+2 strings using 0 minus the number of base-b strings using 0. Since all base-b+1 strings are base-b+2 strings, this is the same as the number of base-b+2 strings using the digit 0 that are not valid base-b strings, which in turn is the same as the number of base-b+2 strings that use the digits 0 and b. Finally, we can substitute b+1 for 1 and say that this is the number of base-b+2 strings that use the digits 0 and 1.

Continuing this way, we can prove by induction that f_n(b) is the number of base-b+n strings that use the first n digits (or any set of n digits in the valid range from 0 to b + n - 1).

This means that f_n(0), i.e. the nth starter constant of the ath powers, is the number of base-n strings that use the first n digits, in other words, all n digits from 0 to n-1. QED.

Usage in probability

This unexpectedly related the SC’s to a problem I had been wondering about since 2012.

How many people need to be in a room for there to be more than a 50% chance that people born on all 365 days (excluding Leap Day) are present?

If you know about the birthday paradox, you should know if there are 365 (non-Leapie) people in the room, the probability of no two people sharing a birthday, which is the same as all 365 common birthdays being covered, is 365!/365^365, or only

1.454955215618703403371401590385251600494220164 × 10^-157.

It is also obvious that if there are 100000 people in a room, there’s a very good chance that each possible birthday gets covered many times. But when does the chance pass ½?

To do this you need to calculate the 365th SC’s of the nth powers, which can be expressed as 365^n - 365*364^n + 365C2*363^n - 365C3*362^n…, where 365Cn is 365 choose n, the nth binomial coefficient on the 365th row of Pascal’s Triangle, until one of them exceeds ½*365^n, and then the answer is n.

That is too difficult even for me (but at least I know how to calculate it), so let’s try a simpler problem.

How many people do you need before it becomes likely that you have one born on each day of the week?

To answer this problem, you would need to look at the SC’s for the 7th powers, because there are 7 days in a week. If we number the days of the week from 0 to 6, the week days the people were born on could be represented as a base-7 number. We need to find the minimum number of digits such that it is likely that the number will use every digit from 0 to 6. Since there are 7^a possible a-digit strings, we need to find the smallest value of a such that the 7th SC of the ath powers is more than half of 7^a.

If we use the formula for the 7th SC as 7^a - 7*6^a + 21*5^a - 35*4^a + 35*3^a - 21*2^a + 7, we can figure out that this transition happens for the a=17, when the 7th SC is 129568848121440, and 7^17 = 232630513987207. So 17 is the minimum number of people needed in order for it to be likely that there are ones born on each day of the week.

Where to next?

Now that I’ve proved the starter constant mystery and the second starter constant mystery, what will I do next? There are still mysteries out there. For example, the SC’s are actually listed thrice in the OEIS, each under a different rearrangement of the terms, and they give a different definition as well under A019538:

Triangle of numbers T(n,k) = k!*Stirling2(n,k) read by rows (n >= 1, 1 <= k <= n).

So, as it turns out, the nth SC isn’t just divisible always divisible by n (which is an obvious corollary of the starter constant mystery), it’s divisible by n! as well! This sounds like it could be a nice thing to prove too.

I will probably also be using the second starter constant mystery to make a simpler proof for the first one – most likely on June 20, for the third anniversary of the original solution.

Table of the starter constants up to the 10th powers

1. 0,1
2. 0,1,2
3. 0,1,6,6
4. 0,1,14,36,24
5. 0,1,30,150,240,120
6. 0,1,62,540,1560,1800,720
7. 0.1,126,1806,8400,16800,15120,5040
8. 0,1,254,5796,40824,126000,191520,141120,40320
9. 0,1,510,18150,186480,834120,1905120,2328480,1451520,362880
10. 0,1,1022,55980,818520,5103000,16435440,29635200,30240000,16329600,3628800
    

Unusual number bases

Have you ever gotten tired of expressing numbers in base 10 all the time? Want to try out some new interesting bases, like ones without a digit 0 (where you can still write every positive integer) or ones where numbers that seem to be integers turn out to be irrational? You’ve come to the right place! Here is a selection of some of my favorite unusual number bases.

Base 37

This is just normal base 37. I happen to like it because 37 is my favorite number, but also because 37 is prime (many nice consequences, including the fact that 36 out of 37 36th powers end in 1) and one more than a square, just like 10 (which means 0.111… is the square of a rational number, 1/6). I use the digits 0 to 9 followed by A to Z and !, which makes for a nice way of representing any string of text as a single number; the 37th digit, meaning 36₁₀ could mean any character that wasn’t a number or a letter. Also 787 and 788, also two of my favorite numbers, end in the same last two digits as their 37th powers in base 37, while most numbers end in only the same last digit as their 37th powers. This may sound strange but it is probably the most normal alternate base on this list.

Centered nonary

This uses 9 digits, but unlike normal base 9 the digits go from -4 to 4. This is useful because you can just multiply each digit by -1 to take the negative of a number. Normally I write the digits -4 to -1 as 1 to 4 flipped about the horizontal axis, but on a computer 1′, 2′, 3′, and 4′ will have to do.

Any valid expression in normal nonary will have the same value in this base. For example 39₁₀ is 43 in both bases.

Here are some more numbers written in centered nonary:

0.2 - 0.22′22′22′…

0.5 - 0.44444… or 1.4′4′4′4′4′…

5 - 14′

37 - 41

68 - 4′4′

77 - 104′

219 - 33′3

Double-digit base 120

This is actually formed by alternating bases 12 and 10. The base-120 ‘digits’ are separated by commas. The first digit is in base 12 and the second is in base 10, so 0 to 99 are written normally, but 100 is written as A0, and 110 is written B0.

Here are some numbers written in double-digit base 120:

1/11 - .10,A9,10,A9…

1/8 - .15

1/7 - .17,17,17…

1/6 - .20

1/5 - .24

¼ - .30

1/3 - .40

½ - .60

2 - 02

121 - 01,01

675 - 05,75

Base φ

Yes, this is the base of the golden ratio. Like any non-integer base, the actual number of digits used is the ceiling function of the golden ratio, however, there is ambiguity, for example:

φ^3 can be written as 1000 or 110.

In general, φ^n can be written as 1000…00 or 110…00, where there …s replace n-5 zeroes, because it is φ^(n-2) + φ^(n-1).

So here’s how we find the right representation of a number. First start with the largest power of φ that is less than your number, then subtract it. Next find the largest power of φ smaller than the remainder, and subtract that too. Keep doing this until you get 0, and put 1s in the places corresponding to the exponents. No two consecutive digits in the resulting number should be 1. For example:

10 = φ^4 + φ^2 + φ^-2 + φ^-4 = 1010.0101

As you may have guessed, every integer has a finite representation in this base. But they get long awfully fast:

40 = 10010101.01001001

111 = 1010001010.0000100001

675 = 10010010000010.00101001001001

Nevertheless, each number has a unique representation using 0s and non-consecutive 1s this way, in a similar way to how each positive integer has a unique representation as a sum of non-consecutive Fibonacci numbers.

Definite-length base 10

In this one, we have ten digits, juts like normal base 10. However, the digits are 1, 2, 3, 4, 5, 6, 7, 8, 9, and A (meaning 10) meaning there is no digit 0.

Normally all numbers have unshown zeroes before the non-zero digits. However, numbers in this base cannot be padded out with zeroes, hence the name definite-length base 10.

All numbers without A’s in definite-length base 10 have the same value in regular base 10. Here is a selection of some numbers with 0 in base 10 and their corresponding representations in definite-length base 10:

10 - A

20 - 1A

100 - 9A

101 - A1

110 - AA

1023 - A23

1203 - 11A3

120059 - 119A59

1000000000 - 99999999A (because it’s one more than 999999999)

This actually would make a good way of representing strings without using a “null character” that can only appear at the end of a string.

“Base” based on prime factors

Unlike the other bases on this list, this base multiplies the values specified by each digit, rather than adding them. Each digit represents a prime p, and digit n represents the number p^n. This actually uses an infinite number of digits, as n can get arbitrarily high. All rational numbers can be represented this way, but close-together numbers often have wildly varying representations.

The last digit represents 2, the second last digit represents 3, the third last digit represents 5, and so on. Here are some example values.

1 - 0

2 - 1

3 - 10

4 - 2

5 - 100

6 - 11

7 - 1000

8 - 3

9 - 20

10 - 101

12 - 12

15 - 110

21 - 1010

504 - 1023

999 - 100000000030

0 - no representation

-10 - -101

2/5 1′01 (here 1′ means -1 again)

How to calculate exact trig values, part 2

Part 1 is here

So when we left off, I had mentioned that cos(pi/n) could be expressed using radicals for every rational value of n. Then I started calculating the values of cos(2pi/p) and sin for prime p, as half the sum of pth roots of unity.

So far I have the values:

cos(2pi/3) = -½

sin(2pi/3) = √3/2

cos(2pi/5) = (-1 + √5)/4

sin(2pi/5) = √(10 + 2√5)/4

Now I will try calculating cos(2pi/7). Let’s start with the six 7th roots of unity not equal to 1: x1, x2, x3, x4, x5, x6. As always, when I express nth roots of unity as x(k) for various values of k from 1 to x-1, x1 has a polar angle of 2pi/n radians. x(k) is just x1^k.

First of all, the sum of these roots is -1. There are 6 of them, so we need to solve a quadratic on top of a cubic, or a cubic on top of a quadratic. Both ways will give different but equivalent expressions for each root. However, solving the cubic first gives the values of 2*cos(2pi/7), 2*cos(4pi/7), and 2*cos(6pi/7) along the way.

Let’s try create a power cycle of length 6 by starting with x1, and repeatedly taking squares:

x1^2 = x2, x2^2 = x4, x4^2 = x1 (because 8 ≡ 1 mod 7), so the sequence goes:

x1, x2, x4, x1, x2, x4…

Hmm, that didn’t work. This only gives a power cycle of length 3. Let’s try starting with x1 and cubing the previous result, rather than squaring:

x1^3 = x3, x3^3 = x2, x2^3 = x6, etc. The sequence goes:

x1, x3, x2, x6, x4, x5, x1…

There! We have a cycle of 6. Now to find the roots of our cubic equation we need to take every third term, starting on the first, second, and third term, and sum:

x1 + x6 = a1

x3 + x4 = a2

x2 + x5 = a3

It might seem easier to just pick the terms whose indexes add up to 7, but sometimes we need to pick out more than two terms to sum (for example if we were solving the quadratic equation first, then we would need to sum 3 alternating terms) and this is a general method for doing that. To make the cycle, I could have taken each number to any power p to get the next number, as long as p is the same number each time, as long as the cycle turns out to be length 6, rather than length 3, 2, or 1. (The length is always a factor of the maximum repeat.) The length of the cycle is actually the same as the repeat length of the decimal expansion of 1/n in base p.

When we calculated the fifth roots of unity, we needed to figure out a1 and a2 by first figuring out a1 + a2, and then figuring out a1 - a2 via its square. In this case we need to figure out a1 + a2 + a3, a1 + r1*a2 + r2*a3 by way of its cube, and a1 + r2*a2 + r1*a3 by way of its cube, where r1 and r2 are the two cube roots of unity. We can then add these up to get 3*a1.

Here is the procedure for a1 + r1*a2 + r2*a3:

(a1 + r1*a2 + r2*a3)^3 =

a1^3 + a2^3 + a3^3 + 6*a1*a2*a3 + 3*r1*(a1^2*a2 + a2^2*a3 +a1*a3^2) + 3*r2*(a1*a2^2 + a2^2*a3 + a1*a3^2) =

(after a long and tedious amount of algebra…)

12 + 10*(x1 + x2 + x3 + x4 + x5 + x6) + 12*r1*(x1 + x2 + x3 + x4 + x5 + x6) + 9*r2*(2 + x1 + x2 + x3 + x4 + x5 + x6) =

(substituting sum(x(n), n = 1…6) for -1, axiom 1 in the previous post)

12 + 10(-1) + 12*r1*(-1) + 9*r2*(2 + -1) =

2 - 12*r1 + 9*r2

r1 and r2 are the non-trivial cube roots of unity, which, as I calculated in the previous post, are (-1 + i*√3)/2 and (-1 - i*√3)/2 respectively. (Remember, r1 has a polar angle of 2pi/3 radians, and r2 has a polar angle of 4pi/3 radians.)

So if we plug those values into 2 - 12*r1 + 9*r2, we get:

(a1 + r1*a2 + r2*a3)^3 = (7 - 21i*√(3))/2

which means a1 + r1*a2 +r2*a3 = ∛((7 - 21i*√(3))/2).

We can calculate the value of a1 + r2*a2 + r1*a3 by replacing r1′s by r2′s and vice versa in our calculation, which gives us 2 + 9*r1 - 12*r2, or (7 + 21i*√(3))/2, so a1 + r2*a2 + r1*a3 = ∛((7 + 21i*√(3))/2).

As mentioned earlier, (a1 + a2 + a3) + (a1 + r1*a2 + r2*a3) + (a1 + r2*a2 + r1*a3) = 3*a1. Similarly, (a1 + a2 + a3) + r1*(a1 + r1*a2 + r2*a3) + r2*(a1 + r2*a2 + r1*a3) = 3*a2, and (a1 + a2 + a3) + r2*(a1 + r1*a2 + r2*a3) + r1*(a1 + r2*a2 + r1*a3) = 3*a3. Dividing each of these by 3 and substituting, we get:

a1 = (-1 + ∛((7 - 21i*√(3))/2) + ∛((7 + 21i*√(3))/2))/3

a2 = (-1 + (-1 + i*√3)/2*∛((7 - 21i*√(3))/2) + (-1 - i*√3)/2*∛((7 + 21i*√(3))/2))/3

a3 = (-1 + (-1 - i*√3)/2*∛((7 - 21i*√(3))/2) + (-1 + i*√3)/2*∛((7 + 21i*√(3))/2))/3

To calculate x1, we need to know x1 + x6 and x1 - x6. x1 + x6 = a1, of which we already know the value, so all we need to do is express x1 - x6 in terms of a1, a2, and a3.

(x1 - x6)^2 =

x1^2 + x6^2 - 2*x1*x6 =

x2 + x5 - 2 =

a3 - 2

x1 - x6 = √(a3 - 2) =

√((-7 + (-1 - i*√3)/2*∛((7 - 21i*√(3))/2) + (-1 + i*√3)/2*∛((7 + 21i*√(3))/2))/3) =

√(-21 + (-3 - 3i*√3)/2*∛((7 - 21i*√(3))/2) + (-3 + 3i*√3)/2*∛((7 + 21i*√(3))/2))/3 =

i*√(21 + (3 + 3i*√3)/2*∛((7 - 21i*√(3))/2) + (3 - 3i*√3)/2*∛((7 + 21i*√(3))/2))/3

So,

x1 = (a1 + √(a3 - 2))/2 = (-1 + ∛((7 - 21i*√(3))/2) + ∛((7 + 21i*√(3))/2) + i*√(21 + (3 + 3i*√3)/2*∛((7 - 21i*√(3))/2) + (3 - 3i*√3)/2*∛((7 + 21i*√(3))/2)))/6

x6 = (a1 - √(a3 - 2))/2 = (-1 + ∛((7 - 21i*√(3))/2) + ∛((7 + 21i*√(3))/2) - i*√(21 + (3 + 3i*√3)/2*∛((7 - 21i*√(3))/2) + (3 - 3i*√3)/2*∛((7 + 21i*√(3))/2)))/6

cos(2pi/7) = (-1 + ∛((7 - 21i*√(3))/2) + ∛((7 + 21i*√(3))/2))/6

sin(2pi/7) = √(21 + (3 + 3i*√3)/2*∛((7 - 21i*√(3))/2) + (3 - 3i*√3)/2*∛((7 + 21i*√(3))/2))/6

If we put these values into a calculator, we see that we have chosen the correct cube root, and (a1 + a2)/2 is indeed cos(2pi/7).

Since I don’t know if there’s a way to make a mathematical expression on Tumblr, here is a screenshot of the expression for x1 made in Google Docs:

Note that the part of the expression under the square root, (x1 - x6)/2, is the only imaginary part of the number. (x1 + x6)/2, despite containing the sum of two cube roots of complex numbers, is real because the cube roots are complex conjugates. This is a casus irreducibilis case.

Also note how many multiples of 7 there are in the result. This is not unnatural, as the fifth roots of unity contained 5 and 10, and the cube roots of unity contained 3. I don’t know why this happens, but I think it has to do with things cancelling out when you take this expression to the 7th power and get 1.

In part 3, we will cover cos(2pi/11), and the 11th roots of unity.

How to calculate exact trig values

So, you probably know the simple trigonometric identities for cos(pi/3) = ½, cos(pi/4) = √2/2, cos(pi/6) = √3/2. You might even know that cos(pi/5) = (1+√5)/4, cos(pi/8) = √(2+√2)/2, and cos(pi/12) = (√2 + √6)/4, which are less known but just as true.

But did you know that for every rational n there is a formula for cos(pi/n) in radicals?

And no, I don’t simply mean they are algebraic numbers, some of which of degree greater than four have no radical expression. No, each of these values can be expressed using ith roots, where i is an integer, along with addition, multiplication, and division, and all the arguments being integers.

To be clear, this includes things like (3-√2)^(1/5), √-5 even though it’s imaginary, 14^(2/3) because it can be written as 196^(1/3), and even 2^(-½) or the negative second root of two, because it can be written as √2/2. However, it excludes 4^(1/3)^(1/5), where the exponents are right-associative, because it cannot be written as n^(1/i), where i is an integer and n is a valid expression.

First of all,

cos(2pi*k/n) = (r(k,n) + r(n - k,n))/2

where

r(a,b) = e^(2pi*i*a/b)

or the bth root of unity at 2pi*a/b radians around the unit circle in the complex plane. This comes from the formula

e^(i*x) = cos(x) + i*sin(x)

so

e^(2pi*i*k/n) = cos(2pi*k/n) + i*sin(2pi*k/n)

or

r(k,n) = cos(2pi*k/n) + i*sin(2pi*k/n).

Similarly,

r(n - k, n) = cos(2pi*(n-k)/n) + i*sin(2pi*(n-k)/n).

But

2pi*(n-k)/n = 2pi - 2pi*k/n

so

cos(2pi*(n-k)/n) = cos(2pi-2pi*k/n) = cos(2pi*k/n)

and

sin(2pi*(n-k)/n) = sin(2pi-2pi*k/n) = -sin(2pi*k/n).

So equation (6) can be written as

r(n - k,n) = cos(2pi*k/n) - i*sin(2pi*k/n).

Combining equations (5) and (10) gives us

r(k,n) + r(n - k,n) = 2*cos(2pi*k/n).

Divide both sides by 2 and this brings us back to

cos(2pi*k/n) = (r(k,n) + r(n - k,n))/2

which is just equation (1).

So how are we going to calculate those roots of unity? In this post, if c is a complex number with a polar angle of Θ, c^(1/n) is defined to be the nth root with a polar angle of Θ/n, so we can’t just say the kth nth root of unity is 1^(k/n) because that is just equal to 1. We need to express it in pth roots, where p is less than n.

Let’s try some examples, for prime roots of unity, which I think are the most fun to work with. Hopefully you will be able to pick up on the general method.

Axioms

When I do arithmetic with roots of unity, I need only 3 axioms. These axioms are easy to prove using algebra, so I will not provide proofs here. However, they are the only three rules you need to simplify expressions with roots of unity sufficiently.

1. If x1, x2, x3 … x(n-1) are nth roots of unity, their sum is -1.

2. If x(a) and x(b) are nth roots of unity, their product is x©, where c is (a+b) mod n.

3. x0 = 1.

We’re ready! Let’s start with an easy case: the square roots of unity.

Call the square roots of unity x0 and x1. By axiom 3, x0 = 1. So all we have left is x1.

By axiom 1, the sum of the roots of unity besides 1, is -1. So x1 = -1. Solved.

That wasn’t so hard, was it? Now let’s try the cube roots of unity.

The cube roots are x0, x1, and x2. x0 = 1, so we’re left with x1 and x2.

By axiom 1, x1 + x2 = -1. What is x1 - x2?

We want to make both terms positive so we can sum them. The easiest way to do this is by taking (x1 - x2)^2.

(x1 - x2)^2 = x1^2 + x2^2 -2*x1*x2.

By axioms 2 and 3, this is x2 + x1 - 2. By axiom 1, this is -1 - 2, or -3

Since (x1 - x2)^2 = -3, x1 - x2 = √-3, or i*√3.

Since we know x1 + x2 and x1 - x2, we can sum them to get 2*x1.

2*x1 = (x1 + x2) + (x1 - x2) = -1 + i*√3, so x1 = (-1 + i*√3)/2.

Similarly we can find x2 by taking (x1 + x2) - (x1 - x2) and dividing by 2, so x2 = (-1 - i*√3)/2.

If we sum these and divide by two (or we could have just stopped at x1 + x2) we get cos(2pi/3) = -½. We can use cosine-to-sine formulas to find sin(2pi/3) = √3/2 (it’s not a coincidence that this is (x1 - x2)/(2*i); in fact, while (r(k,n) + r(n - k,n))/2 = cos(2pi*k/n), (r(k,n) - r(n - k,n))/2 = i*sin(2pi*k/n)). We can furthermore derive, using cos(x/2) = √((1+cos(x))/2), cos(pi/3) = ½, and cos(pi/6) = √3/2, etc.

Now you might be thinking, wouldn’t it be easier to just take x1*x2, and extract x1 and x2 from a quadratic equation? Well, it might be easier now, but soon you’ll be having to take the roots of cubic and quintic equations, so instead of constructing the equation itself, we find the structure of the solution and see which numbers go in it.

Let’s go to the fifth roots of unity. Since x0 = 1, we need to figure out x1, x2, x3, and x4. Let’s start with x1, and square repeatedly. We get:

x1, x2, x4, x3

We will use this sequence, because it cycles through all four terms. If it didn’t, we would repeatedly cube x1, repeatedly biquadrate x1, etc.

Since there are 4 terms, and 4 is 2 * 2, we need to solve a quadratic equation, and then another using our previous solutions as coefficients. The solutions of our first quadratic equation are going to be found by taking the sum of alternate terms in the sequence above. x1 + x4 = a1, and x2 + x3 = a2.

Once again, we need to figure out their sum, and their difference via the square of their difference. This is the general way we will be solving quadratics in calculations of roots of unity.

a1 + a2 = x1 + x2 + x3 + x4 = -1.

(a1 - a2)^2 =

a1^2 + a2^2 - 2*a1*a2 =

(x1 + x4)^2 + (x2 + x3)^2 -2(x1 + x4)(x2 + x3) =

x2 + x3 + 2 + x1 + x4 + 2 - 2*x3 - 2*x4 - 2*x1 - 2*x2 =

-(x1 + x2 + x3 + x4) + 4 =

1 + 4 = 5

(a1 - a2)^2 = 5

a1 - a2 = √5

a1 = (-1 + √5)/2

a2 = (-1 - √5)/2

We might need a calculator to check that (-1 + √5)/2 = x1 + x4 and (-1 - √5)/2 = x2 + x3 and not vice versa, because we could have taken either sign of the square root. This is one of the more annoying aspects of this type of calculation; you need to check to make sure the sum of roots of unity you found is the right one.

Now, to figure out x1, we need to take x1 + x4 and (x1 - x4)^2. Our answers can be in terms of a1 and a2 because we now know their values in radicals.

x1 + x4 = a1

(x1 - x4)^2 =

x2 + x3 -2 =

a2 - 2

x1 - x4 = √(a2 - 2)

Substituting in (-1 - √5)/2 for a2, we find:

x1 - x4 =

√((-1 - √5)/2 - 2) =

√((-5 - √5)/2) =

√(-10 - 2√5)/2 =

i*√(10 + 2√5)/2

A calculator can confirm that x1 - x4 is indeed i*√(10 + 2√5)/2 rather than -i*√(10 + 2√5)/2, which means we chose the correct sign of the square root.

So we have:

x1 = (-1 + √5 + i*√(10 + 2√5))/4

x4 = (-1 + √5 - i*√(10 + 2√5))/4

Similarly we can derive:

x2 = (-1 - √5 + i*√(10 - 2√5))/4

x3 = (-1 - √5 - i*√(10 - 2√5))/4

And:

cos(2pi/5) = (-1 + √5)/4

sin(2pi/5) = √(10 + 2√5)/4

Whew! That was getting hard, wasn’t it? But this is just the beginning. We haven’t even encountered cube roots yet!

More to come!