New Integer Sequences Arising From 3-Period Folding Numbers

Quynh Nguyen, Jean Pedersen, and Hien T. Vu Department of Mathematics and Computer Science Santa Clara University Santa Clara, CA 95053 USA

                  nxquynh89@gmail.com
                   jpedersen@scu.edu
                  hien.t.vu@gmail.com

Abstract

Following Pólya’s “guess and test” method, we seek to discover 3-period folding numbers analogous to the exhaustive set of 2-period folding numbers discovered by Hilton and Pedersen in 1981. Most of the rows and columns of the 2-period folding numbers are reported in the Online Encyclopedia of Integer Sequences (OEIS) with various other mathematical interpretations. We provide a table of 3-period folding numbers, but it is not exhaustive, as we demonstrate by showing other sets of 3-period folding numbers that are not in the table. We close the paper with an algorithm for finding more sets of 3-period folding numbers and a conjecture about how many such sets exist.

In Loving Memory of Jean Pedersen (1934–2016 )

Dedicated to the memory of George Pólya (1887–1985 ) and Peter Hilton (1923–2010 )

1 Motivation

Once upon a time, one of the authors of this paper (JP) discovered that you could take a strip of adding machine tape and, after making any arbitrary fold across the tape, if you bisect the obtuse angle that this transversal makes with the tape it produces a triangle (generally not equilateral). This isn’t at all surprising. However, if you continue to bisect the newly formed obtuse angles (going from left to right) then the new triangles get closer and closer to equilateral triangles. That is, the smallest angle on this tape approaches \frac{π}{3} (see [10]).

Section 2 describes how to construct a regular convex polygon from suitably folded tape. In Section 3 we introduce one definition, one hypothesis that yields two theorems, along with two algebraic identities. This will equip us to systematically find those sets of numbers that require either 2- or 3-period folding procedures.

Section 4 is a brief description and a slightly different approach than what appeared in [3, p. 351] and [7] to obtain 2-period folding numbers. We show an example, and give the table of 2-period folding numbers in two formats.

Section 5 describes our exploration of 3-period folding numbers. We are able to present a table of 3-period folding numbers, but unlike the table for 2-period folding numbers, it is not exhaustive. Then in Section 6 we give examples of what we call our Mystery Monsters, which leads to Section 7 where we give an algorithm for finding more of these Monsters, including another set of 3-period folding numbers. We conclude, in Section 8, with a 3-period Folding Number Conjecture and some questions for the reader to explore.

2 Important paper-folding ideas

First, let us discuss how to use our folded tape to produce a sought after regular star \{\frac{b}{a}\}- gon^{1}. Assume that we have a straight strip of paper with certain vertices marked, at equally spaced intervals, on its top edge. Further assume that the creases at those vertices, labeled A_{nk}, n = 0, 1, 2, … (see Figure 1) on the top edge, form two identical angles of \frac{aπ}{b}. The first is between the crease along the line A_{nk}A_{nk+2} and the second is between that line and the line A_{nk}A_{nk+1} (as shown in Figure 1(a)). If we fold this strip on A_{nk}A_{nk+2}, as shown in Figure 1(b), and then twist the tape so that it folds on A_{nk}A_{nk+1}, as shown in Figure 1(c), the direction of the top edge of the tape will be rotated through an angle of 2 (\frac{aπ}{b}). We call this process of Folding And Twisting, the FAT-algorithm.

Now consider the equally spaced vertices A_{nk} along the top of the tape, with k fixed and n varying. If the FAT-algorithm is performed on a sequence of angles, each of measure \frac{aπ}{b}, at the vertices given by n = 0, 1, 2, …, b − 1, then the top edge of the tape will have turned through an angle of 2aπ. Thus the vertex A_{bk} will come into coincidence with A_{0}. The top edge of the tape will have visited every ath vertex of a bounding regular convex b-gon, thus creating a star \{\frac{b}{a}\}-gon. As an example, see Figure 4(c) where a = 2 and b = 7. When a = 1, our b-gon is a special case of the star \{\frac{b}{1}\}-gon.

1Note that when we speak of a \{\frac{b}{a}\}-gon, we assume that a, b are coprime. Then a star \{\frac{b}{a}\}-gon is the sequence of edges that visit every ath vertex of a regular b-gon. Since, for example, the \{\frac{7}{3}\}-gon of Figure 4(d) would be the same as a \{\frac{7}{4}\}-gon, we will assume that a < \frac{b}{2}. Of course, if a = 1, the \{\frac{b}{a}\}-gon becomes the regular b-gon.

If one wishes to produce a regular polygon with p sides where p = 2^{n}b, this can be achieved by putting in secondary fold lines bisecting successive angles of \frac{π}{b} as many times as necessary to produce angles of \frac{π}{2^{n}b} along the top edge of the tape. This is why we only have to create folding procedures for odd numbers b ≥ 3, in order to be able to construct all regular p-gons where p ≥ 3.

Figure 2 illustrates how a suitably creased strip of paper may be folded by the FATalgorithm to produce a regular convex p-gon. In Figure 2 we have written V_{k} instead of A_{nk}, since it is more natural in this particular context.

Because the regular convex 7-gon is the first regular polygon that we encounter for which there is no Euclidean construction (with a straight edge and compass), we are faced with a real difficulty in creating a crease line making an angle of \frac{π}{7} with the top edge of the tape. We proceed by adopting a general policy we call our optimistic strategy. Assume that we can crease an angle of \frac{2π}{7} (certainly we can come close) as shown in Figure 3(a). Given that we have the angle of \frac{2π}{7}, one can then fold the top edge of the strip DOWN to bisect this angle, producing two adjacent angles of \frac{π}{7} at the top edge as shown in Figure 3(b). Then, since we are content with this arrangement, we go to the bottom of the tape where we observe that the angle to the right of the last crease line is \frac{6π}{7} — and we decide, as paper-folders, to avoid leaving even multiples of π in the numerator of any angle next to the edge of the tape. So we bisect this angle of \frac{6π}{7} by bringing the bottom edge of the tape UP to coincide with the last crease line and creating the new crease line sloping up as shown in Figure 3(c). We settle for this because there is an odd multiple of π in the numerator and go to the top of the tape where we observe that the angle to the right of the last crease line is \frac{4π}{7} — and, since this is 2^{2} · (\frac{π}{7}) we are forced to bisect this angle twice, each time bringing the top edge of the tape DOWN to coincide with the last crease line, obtaining the arrangement of crease lines shown in Figure 3(d). But now we notice something miraculous has occurred! If we had really started with an angle of exactly \frac{2π}{7}, and if we now continue introducing crease lines by repeatedly folding the tape DOWN TWICE at the top and UP ONCE at the bottom, we get precisely what we want, namely pairs of adjacent angles measuring \frac{π}{7}, at equally spaced intervals along the top edge of the tape. We call this folding procedure the D^{2}U^{1}-folding procedure (or, more simply (2, 1)-folding procedure), which we call a 2-period folding procedure.

How do we prove that this evident convergence actually takes place? A very direct approach is to admit that the first angle folded down from the top of the tape in Figure 3(a) might not have been precisely \frac{2π}{7}. Then the bisection forming the next crease would make the two acute angles nearest the top edge in Figure 3(b) only approximately \frac{π}{7}. Let us call them \frac{π}{7} + ϵ (where ϵ may be either positive or negative!). Consequently the angle to the right of this crease, at the bottom of the tape, would measure \frac{6π}{7} − ϵ. When this angle is bisected, by folding up, the resulting acute angles nearest the bottom of the tape, labeled \frac{3π}{7} in Figure 3(c), would in fact measure \frac{3π}{7} − \frac{ϵ}{2}, forcing the angle to the right of this crease line at the top of the tape to have measure \frac{4π}{7} + \frac{ϵ}{2}. When this last angle is bisected twice by folding the tape down, the two acute angles nearest the top edge of the tape will measure \frac{π}{7} + \frac{ϵ}{2^{3}} . This makes it clear that every time we repeat a (2, 1)-folding on the tape the error,

ϵ , is reduced by \frac{1}{2^{3}} .

We see that our optimistic strategy has paid off — by simply assuming we have an angle of \frac{2π}{7}, or \frac{π}{7}, at the top of the tape to begin with, and folding accordingly, we get what we want — successive angles at the top of the tape which, as we fold, rapidly get closer and closer to \frac{π}{7}. This will occur regardless of our original angle. In fact, when using any of these iterative folding procedures, every fold line cuts the previous error ϵ in half. So if you throw away the first 10 triangles on your folded tape, the error in the subsequent desired angles will be less than \frac{ϵ}{2^{10}} , which should be undetectable to even the most discerning eye, and the remaining tape can be used to construct very respectable regular polygons.

Figure 4(a) shows a piece of the tape folded by the (2, 1)-folding procedure and Figure 4(b) shows the FAT regular 7-gon produced by folding and twisting on the successive long crease lines that make angles of \frac{π}{7} with the top edge of the tape. If you fold and twist on every other successive medium crease line, the top edge of the tape will form the regular star \{\frac{7}{2}\}-gon of Figure 4(c). If you flip the tape so as to reverse the top and bottom edges and fold and twist on every other short crease line, the top edge of the tape will form the regular star \{\frac{7}{3}\}-gon of Figure 4(d). The excess tape is folded around the points to get the right-hand figure of Figure 4(d).

The procedure we use to obtain the tape on which the smallest angles converge to \frac{π}{7}, with its error correction proof, will work for any choice of your initial angle that is of the form \frac{aπ}{b}, if a and b are odd integers so that b ≥ 3 and a < \frac{b}{2}. Here we only concern ourselves with a = 1, since we only wish to construct approximations to regular convex b-gons (see [3, p. 351], [4, p. 335], [5] for variations involving star polygons).

You may wish to use the optimistic approach yourself for constructing a regular 11-gon. Start with two identical angles of \frac{π}{11} next to each other instead of \frac{π}{7}, as we did in Figure 3(b) and draw suitable lines, which when interpreted will produce instructions for folding tape to construct a regular 11-gon. In this case you will find that the next angle of \frac{π}{11} appears at the bottom edge of the tape, but if you continue it will then appear again on the top edge of the tape. The folding procedure will be (3, 1, 1) — meaning you fold the tape D^{3}U^{1}D^{1}U^{3}D^{1}U^{1} · · ·. Since the Ds and Us alternate and the exponents run repeatedly through 3, 1, 1, we call this a 3-period folding procedure.

3 Useful tools

It is tedious to have to draw the illustrations corresponding to Figure 3 to determine the folding procedure each time we want to fold any b-gon. What we would like is an algorithmic way to find the folding procedure. In order to do this, we give the relevant mathematical background; this includes two theorems (that have the same hypothesis) and two elementary algebraic identities.

Hypothesis 1. Suppose we construct the following symbol:

b | \begin{matrix}a_{1} & a_{2} & · & · & · & a_{r} \\ k_{1} & k_{2} & · & · & · & k_{r} \end{matrix}| ,  (1)

where b, a_{i} are odd, a_{i} < \frac{b}{2}, ∑_{i=1}^{r} k_{i} = k and

b − a_{i} = 2^{k_{i}}a_{i+1},  (2)

i = 1, 2, ⋯, r, a_{r+1} = a_{1}, with r minimal. Note that r = the number of columns, which we also call the period.

It was proved in [3, Chapter 4] that, given any two odd numbers a and b, with a < \frac{b}{2}, there is always a completely determined unique symbol (1) for any a = a_{1}. Since r is minimal, the list a_{1}, a_{2}, …, a_{r} is without repeats; thus the symbol (1) is contracted. If gcd(b, a_{i}) = 1, we say the symbol (1) is reduced.

Theorem 2. (Paper-folding Theorem) Given the symbol (1) for any odd b ≥ 3 as described above, and a_{1} = 1, the sequence k_{r}, k_{1}, k_{2},… k_{r−1}, (or any cyclic permutation of this sequence) when used as consecutive exponents in the sequence DUDUDUDU ⋯ encodes a folding procedure that produces tape which can be used to construct a regular b-gon.

If you fail to stop when the symbol repeats, then no harm will come in terms of the folding procedure. You just need to stop at some point where the next a_{1} = 1. For example,

if you were to write the symbol for 5 as 5 | \begin{matrix}1 & 1 \\ 2 & 2 \end{matrix}|, or 5 | \begin{matrix}1 & 1 & 1 \\ 2 & 2 & 2 \end{matrix}| instead of the contracted

symbol 5 | \begin{matrix}1 \\ 2 \end{matrix}| , the folding instructions would give the same result. When confronted with a

symbol that is not contracted, we will call it a degenerate case. The two non-contracted symbols above thus give degenerate 2- and 3-period folding instructions, respectively.

Theorem 3. (Quasi-order Theorem) Suppose that symbol (1) is contracted and reduced, then k is the Quasi-order of 2 mod b, denoted QO(b) = k. That is 2^{k} ≡ ±1 mod b. In fact, 2^{k} ≡ (−1)^{r} mod b, where r is the period. This means that b exactly divides 2^{k} −(−1)^{r}, which may be written

b | (2^{k} − (−1)^{r}).

Thus if r is odd, b | (2^{k} + 1) and if r is even, b | (2^{k} − 1).

Theorems 2 and 3 are proved by Hilton, Holton, and Pedersen in [3, p. 351].

The Quasi-order Theorem holds if the symbol (1) begins with any a_{i} < \frac{b}{2} and because the symbol is contracted, the QO(b), tells you the smallest k such that b|2^{k} + 1 (when the number of columns in the symbol (1) is odd), or such that b|2^{k} − 1 (when the number of columns in the symbol (1) is even). An important consequence of the Quasi-order Theorem, which we will use later, is that it partitions all the integers b ≥ 3 into two distinct sets. Those integers will either be in the set of folding instructions having an odd number of entries (r odd) or in the set of folding instructions having an even number of entries (r even).

When r is odd, if we don’t insist on the smallest k such that b|2^{k} + 1, then there will always exist an a > k such that b | 2^{a} − 1. This is because (2^{k} − 1)(2^{k} + 1) = 2^{2k} − 1, so a = 2k and b | 2^{2k} − 1. However, when r is even and k is the smallest number such that b | 2^{k} − 1, then it is not possible to find a suitable exponent a > k such that b | 2^{a} + 1. This algebraic fact manifests itself in the folding procedures in that the bottom row with an odd number of entries greater than 1 needs to be duplicated in order for the angle \frac{π}{b} to appear at equally spaced intervals along the top of the tape (recall when b = 11); whereas, for folding procedures with the bottom row having an even number of entries, no repetitions are needed for this to happen.

For all integers t and y, with t ≥ 2 and y ≥ 1 we have the following two algebraic identities:

Identity 4.

t^{y} − 1 = (t − 1)(t^{y−1} + t^{y−2} + ⋯ + t^{1} + 1)

Identity 5.

t^{2y+1} + 1 = (t + 1)(t^{2y} − t^{2y−1} + ⋯ − t^{1} + 1).

These identities allow us to infer that both \frac{t^{y}−1}{t−1} and \frac{t^{2y+1}+1}{t+1} are integers.

Example 6. If we wish to construct a regular convex 7-gon, we start with b = 7, a_{1} = 1, and writing the beginning of symbol (1) as

b = 7| \begin{matrix}1 & a_{1} & · & · & · \\ k_{1} & k_{2} & · & · & · \end{matrix}

Then, by (2), we have 7 − 1 = 6 = 2^{1} · 3, so that k_{1} = 1 and a_{2} = 3, and filling in those values we have

b = 7| \begin{matrix}1 & 3 & · & · & · \\ 1 & k_{2} & · & · & · \end{matrix}

Using (2) again, we have 7 − 3 = 4 = 2^{2} · 1. This tells us that k_{2} = 2 and a_{3} = 1, but since a_{1} = 1, we stop, draw the final vertical line, and obtain the symbol

b = 7 | \begin{matrix}1 & 3 \\ 1 & 2 \end{matrix}| .

The number of columns tells us that r = 2, indicating a 2-period folding procedure. Then since k_{1} = 1 and k_{2} = 2, by Theorem 2, the folding procedure is given by ( 2, 1), which is the same procedure that was used to construct the regular 7-gon of Figure 4( b). Do you see why? [ Hint, it has to do with the value of k_{i} that precedes a_{i}, starting with i = 1]. Notice, too, that the Quasi-order Theorem tells us

2^{3} ≡ (−1)^{2} mod 7, or that 7|[2^{3} − (−1)^{2}] = 2^{3} − 1,

which should come as no surprise!

Example 7. If we wish to construct a regular 11-gon, we start with b = 11, a_{1} = 1, obtaining the symbol

b = 11 | \begin{matrix}1 & 5 & 3 \\ 1 & 1 & 3 \end{matrix}| .

The arithmetical steps, using (2), are:

11 − 1 = 10 = 2^{1} · 5, telling us that k_{1} = 1, a_{2} = 5;
11 − 5 = 6 = 2^{1} · 3, telling us that k_{2} = 1, a_{3} = 3;
11 − 3 = 8 = 2^{3} · 1, telling us that k_{3} = 3, and a_{4} = 1,

which is the a_{1} we started with, so we stop. By Theorem 2, the 3-period folding procedure that produces a regular convex 11-gon is given by ( 3, 1, 1).

4 2-period folding numbers

If we wish to examine all the numbers that have a 2-period folding procedure, we need to find all b such that the symbol (1) has just two elements in the bottom row. That is, suppose symbol (1) has the form

b |\begin{matrix}1 & a_{2} \\ x & k_{2} \end{matrix}| .

Then, by (2), b − 1 = 2^{x} · a_{2}, or a_{2} = \frac{b−1}{2^{x}}. And again, by (2), b − a_{2} = 2^{k_{2}} · 1, or, substituting the value for a_{2} = \frac{b−1}{2^{x}}, we have b − \frac{b−1}{2^{x}} = 2^{k_{2}}. Solving for b, we obtain

b = \frac{2^{x+k_{2}} − 1}{2^{x} − 1}.

Letting 2^{x} = t in Identity 4, we see that b is an integer if x+k_{2} = xy, so that k_{2} = xy −x, and express

b = \frac{2^{xy} − 1}{2^{x} − 1}.

Beginning with this value of b, we construct the symbol (1), using (2), obtaining

b = \frac{2^{xy} − 1}{2^{x} − 1} |\begin{matrix}1 & \frac{2^{xy−x}−1}{2^{x}−1} \\ x & xy − x \end{matrix}| .

Thus, all 2-period folding numbers are of this form, and the folding procedure, from Theorem 2, is given by (xy − x, x), where x, y ≥ 1. These 2-period folding numbers appear in Table 1, including the degenerate entries in the rows where y = 1 or 2. The sequences arising from the rows and columns of the table are all found in OEIS, except for the columns where x = 7, 9, 10 and the rows where y = 9, 10, 12 and all y ≥ 14. However, they do not appear in the context of being 2-period folding numbers. Please see the “Concerned with sequences” section at the end of the paper for a list of 2-period sequences which appear in the OEIS.

Look at Table 1 to see if you can determine the next number in the various rows, or columns, without calculating it. We think this is a pretty daunting task. However, if you look at these numbers, written in base 2, as shown in Table 2, you might detect patterns that would allow you to extend the entries in the rows and columns more easily.

y ≥ 7 2^{y} − 1
6  63  1365 37449 1118481 34636833
5  31  341 4681 69905 1082401 17043521
4  15  85 585 4369  33825  266305
3  7  21 73  273  1057  4161
2  3  5  9  17  33  65  2^{x} + 1
1  1  1  1  1  1  1  1
\begin{matrix}↑ \\ y \end{matrix} /x → 1  2  3  4  5  6  x ≥ 7

Table 1: Two-period folding numbers, b, expressed in base ten, where b = \frac{2^{xy}−1}{2^{x}−1}, with y > 1

\begin{matrix}6 & (\overline{1})^{5}1 & (\overline{10})^{5}1 & (\overline{100})^{5}1 & (\overline{1000})^{5}1 & (\overline{10000})^{5}1 & (\overline{100000})^{5}1 \\ 5 & 11111 & 101010101 & 1001001001001 & 10001000100010001 & 100001000010000100001 & (\overline{100000})^{4}1 \\ 4 & 1111 & 1010101 & 1001001001 & 1000100010001 & 1000010000100001 & (\overline{100000})^{3}1 \\ 3 & 111 & 10101 & 1001001 & 100010001 & 10000100001 & (\overline{100000})^{2}1 \\ 2 & 11 & 101 & 1001 & 10001 & 100001 & (\overline{100000})^{1}1 \\ 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ \begin{matrix}↑ \\ y \end{matrix} /x → & 1 & 2 & 3 & 4 & 5 & 6 \end{matrix}

Table 2: Two-period folding numbers, b, expressed in base two, where y > 1

We use here, and in future tables, the notation (\overline{d_{1} ⋯ d_{ℓ}})^{n} to mean that the overlined digits d_{i} between the parentheses are repeated n times. So that, for example, the entry in Table 2 with coordinates (x, y) = (4, 5) (with ℓ = 4, d_{1} = 1, d_{2} = d_{3} = d_{4} = 0) may then be expressed more compactly as

10001000100010001 = (\overline{1000})^{4}1.

5 3-period folding numbers

If we wish to examine all the numbers b that have a 3-period folding procedure, we need to find all the numbers b such that the symbol (1) has just three columns. That is, we want to be able to fill in b and k_{i} for

b |\begin{matrix}1 & a_{2} & a_{3} \\ k_{1} & k_{2} & k_{3} \end{matrix}| .

Using (2), we see that we need b − 1 = 2^{k_{1}} · a_{2}, so that a_{2} = \frac{b−1}{2^{k_{1}}} and b − a_{2} = 2^{k_{2}} · a_{3}, from which, by substituting a_{2} = \frac{b−1}{2^{k_{1}}}, we infer a_{3} = \frac{b2^{k_{1}}−b+1}{2^{k_{1}+k_{2}}} and thus b − \frac{b2^{k_{1}}−b+1}{2^{k_{1}+k_{2}}} = 2^{k_{3}} · 1. So, solving this last expression for b, we have a necessary condition for a 3-period folding procedure; namely that b is an integer when

b = \frac{2^{k_{1}+k_{2}+k_{3}} + 1}{2^{k_{1}+k_{2}} − 2^{k_{1}} + 1} = \frac{2^{k} + 1}{2^{k_{1}+k_{2}} − 2^{k_{1}} + 1},  (3)

where ∑_{i=1}^{3} k_{i} = k.

This is a considerably more complicated restriction than we had for the 2-period folding numbers. How should we proceed? First, we need to determine if there is an integer k such that 2^{k_{1}+k_{2}} − 2^{k_{1}} + 1 exactly divides 2^{k} + 1.

Elieser J. Oseguera (JP’s student at SCU) wrote a program for calculating the symbol (1), with a_{1} = 1, so we used Eli’s program to look at a lot of examples. We noticed the examples fell into categories, but the breakthrough came when we noticed that most of them had k_{2} = 1. So assuming that a_{1} = 1, k_{1} = x, and k_{2} = 1, from (3), we need an integer b of the form

b = \frac{2^{x+1+k_{3}} + 1}{2^{x+1} − 2^{x} + 1} = \frac{2^{x+1+k_{3}} + 1}{2^{x}(2^{1} − 1) + 1} = \frac{2^{x+1+k_{3}} + 1}{2^{x} + 1}.

Substituting t = 2^{x} into Identity 5, we see that in order for b to be an integer it must be the case that x + k_{3} + 1 = x(2y + 1), thus

b = \frac{2^{x(2y+1)} + 1}{2^{x} + 1}.

Then because x+1+k_{3} = x(2y +1), we get k_{3} = 2xy −1 and, from Theorem 2, we obtain the special set of 3-period folding numbers whose folding instructions are (2xy − 1, x, 1), for x, y ≥ 1. Here is the complete symbol encoding those 3-period folding numbers:

b = \frac{2^{x(2y+1)} + 1}{2^{x} + 1} |\begin{matrix}1 & \frac{2^{2xy}−1}{2^{x}+1} & \frac{2^{2xy+x−1}−2^{2xy−1}+1}{2^{x}+1} \\ x & 1 & 2xy − 1 \end{matrix}| .  (4)

Theorem 2 tells us that if we fold repeatedly D^{2xy−1}U^{x}D^{1}U^{2xy−1}D^{x}U^{1} ⋯, then the smallest angle on the tape will converge to \frac{π}{b}. Consequently, we can use this tape to construct arbitrarily good approximations to those regular convex b-gons using the FAT-algorithm. When x = y = 1 this becomes the degenerate 3-period folding procedure (1, 1, 1).

As with the 2-period folding numbers, the sequence of numbers in any row, or column, of Table 3 is not familiar to most people — but if you look at Table 4, where these numbers are expressed in base 2, you may find the sequences less mysterious.

\begin{matrix}6 & 2731 & 13421773 & 61083979321 & 264917625139441 & 1117984489315730401 \\ 5 & 683 & 838861 & 954437177 & 1034834473201 & 1091781727847393 \\ 4 & 171 & 52429 & 14913081 & 4042322161 & 1066193093601 \\ 3 & 43 & 3277 & 233017 & 15790321 & 1041204193 \\ 2 & 11 & 205 & 3641 & 61681 & 1016801 \\ 1 & 3 & 13 & 57 & 241 & 993 \\ \begin{matrix}↑ \\ y \end{matrix} /x → & 1 & 2 & 3 & 4 & 5 \end{matrix}

Table 3: Three-period folding numbers, b, expressed in base ten, where b = \frac{2^{x(2y+1)}+1}{2^{x}+1}, with x and y ≠ 1

\begin{matrix}6 & (\overline{10})^{5}11 & (\overline{1100})^{5}1101 & (\overline{111000})^{5}111001 & (\overline{11110000})^{5}11110001 & (\overline{1111100000})^{5}1111100001 \\ 5 & (\overline{10})^{4}11 & (\overline{1100})^{4}1101 & (\overline{111000})^{4}111001 & (\overline{11110000})^{4}11110001 & (\overline{1111100000})^{4}1111100001 \\ 4 & 10101011 & (\overline{1100})^{3}1101 & (\overline{111000})^{3}111001 & (\overline{11110000})^{3}11110001 & (\overline{1111100000})^{3}1111100001 \\ 3 & 101011 & (\overline{1100})^{2}1101 & (\overline{111000})^{2}111001 & (\overline{11110000})^{2}11110001 & (\overline{1111100000})^{2}1111100001 \\ 2 & 1011 & 11001101 & 111000111001 & 1111000011110001 & 11111000001111100001 \\ 1 & 11 & 1101 & 111001 & 11110001 & 1111100001 \\ \begin{matrix}↑ \\ y \end{matrix} /x → & 1 & 2 & 3 & 4 & 5 \end{matrix}

Table 4: Three-period folding numbers, b, expressed in base two, with x and y ≠ 1

Note that Table 1 contains all possible 2-period folding numbers, whereas of Table 3 does not contain all possible 3-period folding numbers. So we have more work to do. It is also important to note that as a consequence of the Quasi-order Theorem, except for the degenerate 2- and 3-period folding number 3, none of the numbers in Table 1 can appear in Table 3.

The sequences corresponding to the first column (x = 1) and the first two rows (y = 1, 2) of Table 3, arising from 3-period folding numbers, appear on OEIS (see A007583, A020515, A020518 in [12]).

6 Mystery monsters

We realized that the numbers in Table 3 were only a subset of what is possible because we encountered in our preliminary explorations other numbers that did not fit into the table. The numbers in these categories tended to begin big and to increase in size very rapidly, so we called them Mystery Monsters.

Let us give some examples and then, on the basis of what we learn from these examples, we will state an algorithm for finding more 3-period folding numbers.

Monster A

We discovered the following 3-period symbol:

20165 | \begin{matrix}1 & 5041 & 3781 \\ 2 & 2 & 14 \end{matrix}| .

Recalling the degenerate symbol

5 | \begin{matrix}1 & 1 & 1 \\ 2 & 2 & 2 \end{matrix}| ,

led us to conjecture that there would be a family of symbols of the form

b | \begin{matrix}1 & a_{1} & a_{2} \\ 2 & 2 & 12y + 2 \end{matrix}| .

Using (3) to find b, and then using (2) to construct the symbol (1), we soon discovered there is, indeed, a sequence of such symbols for Monster A of the form

b = \frac{2^{12y+6} + 1}{2^{4} − 2^{2} + 1} = \frac{2^{6(2y+1)} + 1}{13} | \begin{matrix}1 & \frac{2^{12y+4}−3}{13} & \frac{2^{12y+4}−2^{12y+2}+1}{13} \\ 2 & 2 & 12y + 2 \end{matrix}| ,  (5)

y = 0, 1, 2, 3, …

By Theorem 2, the folding procedure for this b would be (12y + 2, 2, 2). What pleased us most was that when we calculated the first few cases of this set, they displayed the same repetitive nature in base 2 that we had seen for the numbers in Tables 2 and 4. Thus, for Monster A, we obtained the following table for 0 ≤ y ≤ 3.

y b in base ten b in base two
0 5  101
1 20165  (\overline{100111011000})^{1}101
2 82595525  (\overline{100111011000})^{2}101
3 338311270085 (\overline{100111011000})^{3}101

Satisfying as this was, it did not give us a dependable algorithm for finding such sequences, because we needed to recall a particular degenerate case. So, we tried a more systematic approach.

Suppose we want to determine whether or not a 3-period folding procedure can exist so that the symbol for b would be of the form:

b | \begin{matrix}1 & a_{1} & a_{3} \\ 2 & 2 & k_{3} \end{matrix}| .

From (3) we would have

b = \frac{2^{2+2+k_{3}} + 1}{2^{2+2} − 2^{2} + 1} = \frac{2^{k_{3}+4} + 1}{2^{4} − 2^{2} + 1} = \frac{2^{k_{3}+4} + 1}{13}.

To determine whether or not 13 can divide a number of the form 2^{k_{3}+4} + 1, we use Theorem

3. Hence we calculate the symbol (1) with b = 13, obtaining 13 | \begin{matrix}1 & 3 & 5 \\ 2 & 1 & 3 \end{matrix}|, and we deduce,

from Theorem 3, that the QO(13) = 6, with the number of columns, r, odd, meaning that the first time 13 divides a number of the form 2^{k} + 1 is when k = 6. This forces k_{3} = 2, which is our degenerate case. But, don’t despair, we appeal to Identity 5 to infer that if 13 | 2^{6} + 1, then 13 | 2^{6(2y+1)} + 1, thus giving us the same value of b as in (5) above.

Monster B

It was then natural to see if we could have a symbol of the form

b | \begin{matrix}1 & a_{2} & a_{3} \\ 3 & 2 & k_{3} \end{matrix}| .

As before, from (3) we have

b = \frac{2^{3+2+k_{3}} + 1}{2^{3+2} − 2^{3} + 1} = \frac{2^{k_{3}+5} + 1}{2^{5} − 2^{3} + 1} = \frac{2^{k_{3}+5} + 1}{25}.

To determine whether or not 25 can divide a number of the form 2^{k_{3}+5} + 1, we again use

Theorem 3. We calculate the symbol (1) with b = 25, obtaining 25 | \begin{matrix}1 & 3 & 11 & 7 & 9 \\ 3 & 1 & 1 & 1 & 4 \end{matrix}|, and

we deduce, from Theorem 3, that QO(25) = 10, with an odd number of columns, so the first time 25 divides a number of the form 2^{k} + 1 is when k = 10. This forces k_{3} = 5. Then, by Identity 5 we know that 25 | 2^{10(2y+1)} + 1. Indeed, in general, we have

b = \frac{2^{10(2y+1)} + 1}{25} |\begin{matrix}1 & \frac{2^{20y+7}−3}{25} & \frac{2^{20y+8}−2^{20y+5}+1}{25} \\ 3 & 2 & 20y + 5 \end{matrix}| , y ≥ 0.

By Theorem 2, the folding procedure for this b would be (20y + 5, 3, 2).

For Monster B, we have the following table for 0 ≤ y ≤ 2.

y b in base ten  b in base two
0 41  101001
1 42949673  (\overline{10100011110101110000})^{1}101001
2 45035996273705 (\overline{10100011110101110000})^{2}101001

Monster C

Encouraged by this, we examine the set of 3-period folding numbers where k_{2} = 2. Trying to construct Monster C of the form

b | \begin{matrix}1 & a_{1} & a_{3} \\ 4 & 2 & k_{3} \end{matrix}|

turns out to be futile, because from (3) b would have to be an integer of the form \frac{2^{k_{3}+6}+1}{2^{6}−2^{4}+1} = \frac{2^{k_{3}+6}+1}{49} and writing the symbol (1) with b = 49, we have

49 | \begin{matrix}1 & 3 & 23 & 13 & 9 & 5 & 11 & 19 & 15 & 17 \\ 4 & 1 & 1 & 2 & 3 & 2 & 1 & 1 & 1 & 5 \end{matrix}|, (with 10 columns!).

Theorem 3 tells us that QO(49) = 21, with an even number of columns. This means 49 cannot divide any number of the form 2^{k} + 1. So no 3-period folding instructions of the type (k_{3}, 4, 2) can exist.^{2}

Monster D

Undaunted, and hoping to learn something about this process, we tried to construct Monster D of the type

b | \begin{matrix}1 & a_{1} & a_{3} \\ 5 & 2 & k_{3} \end{matrix}| .

From (3), we infer that in this case b must be of the form \frac{2^{k}+1}{2^{7}−2^{5}+1} = \frac{2^{k}+1}{2^{7}−2^{5}+1} = \frac{2^{k}+1}{97}. To see if this is possible, we check the QO(97) by first constructing the symbol (1) with b = 97, obtaining

97 |\begin{matrix}1 & 3 & 47 & 25 & 9 & 11 & 43 & 27 & 35 & 31 & 33 \\ 5 & 1 & 1 & 3 & 3 & 1 & 1 & 1 & 1 & 1 & 6 \end{matrix}| (with 11 columns).

Theorem 3 tells us that QO(97) = 24, with an odd number of columns. Thus, we know that 97| = 2^{24} + 1. This, along with Identity 5, gives the relevant information for Monster D as

b = \frac{2^{24(2y+1)} + 1}{2^{7} − 2^{5} + 1} = \frac{2^{24(2y+1)} + 1}{97} | \begin{matrix}1 & \frac{2^{48y+19}−3}{97} & \frac{2^{48y+22}−2^{48y+17}+1}{97} \\ 5 & 2 & 48y + 17 \end{matrix}| .

By Theorem 2, the folding procedure for this b would be (48y + 17, 5, 2).

When y = 0, b = 101010001110100001, in base 2. For a general y ≥ 1 in base 2, b = \overline{(101010001110100000111111010101110001011111000000})^{y−1}101010001110100001.

7 A general approach for finding other 3-period folding numbers

Now looking back at Monsters A through D, it looks as though a general procedure for discovering 3-period folding sequences might go as follows:

2It was proved by Hilton and Pedersen in [6], using a different technique, that 7 cannot divide any number of the form 2^{k} + 1, and it follows that 49 cannot divide any number of the form 2^{k} + 1 as well. For our purposes, the argument we use seems simpler, and has the advantage that it covers all impossible cases.

(a) We seek to find k_{3} for symbol (1) with a_{1} = 1, k_{1} = x and k_{2} = f(x). Thus we want to fill in k_{3} for

b |\begin{matrix}1 & a_{2} & a_{3} \\ x & f(x) & k_{3} \end{matrix}| .

(b) Calculate from (3) the candidate b = \frac{2^{x+f(x)+k_{3}}+1}{2^{x+f(x)}−2^{x}+1}, calling the denominator d, so that

d = 2^{x+f(x)} − 2^{x} + 1.

(c) Calculate the symbol (1) using d in the b position, noting whether the number of columns in the symbol is even or odd. Then use Theorem 3 to find the QO(d).

(d) (i) If r is even, no such folding procedure can exist.

(ii) If r is odd, then the general symbol can be written as

b = \frac{2^{QO(d)(2y+1)}+1}{2^{x+f(x)} − 2^{x} + 1} |\begin{matrix}1 & a_{2} & a_{3} \\ x & f(x) & [QO(d)(2y + 1) − x − f(x)] \end{matrix}| ,  (6)

and, by Theorem 2, the folding procedure is given by

([QO(d)(2y + 1) − x − f(x)], f(x), x).

For a reality check, let us try our algorithm to obtain the b in (4) appearing in Table 3.

(a) We seek to find k_{3} for symbol (1) with a_{1} = 1, k_{1} = x and k_{2} = 1. Thus we want to fill in k_{3} for

b |\begin{matrix}1 & a_{2} & a_{3} \\ x & 1 & k_{3} \end{matrix}| .

(b) Calculate from (3) the candidate b = \frac{2^{x+1+k_{3}}+1}{2^{x+1}−2^{x}+1}, calling the denominator d, so that

d = 2^{x+1} − 2^{x} + 1.

(c) Construct symbol (1), beginning with 2^{x+1} − 2^{x} + 1 in the b position. Thus, since (2^{x+1} − 2^{x} + 1) − 1 = 2^{x+1} − 2^{x} = 2^{x}(2^{1} − 1) = 2^{x} · 1, we have

2^{x+1} − 2^{x} + 1 |\begin{matrix}1 \\ x \end{matrix}| (which has an odd number of columns).

By Theorem 3 the QO(2^{x+1} − 2^{x} + 1) = x and (2^{x+1} − 2^{x} + 1)|2^{x} + 1. This is not too surprising if you simplify (2^{x+1} − 2^{x} + 1).

(d) Since r is odd, we are in case (ii) so that the relevant information can be written as

b = \frac{2^{x(2y+1)}+1}{2^{x+1} − 2^{x} + 1} = \frac{2^{x(2y+1)}+1}{2^{x} + 1} |\begin{matrix}1 & a_{2} & a_{3} \\ x & 1 & x(2y + 1) − x − 1 \end{matrix}| ,

which is the same as (4) when k_{3} is simplified.

A set of monsters

We close by demonstrating our algorithm to find another set of 3-period folding numbers.

(a) We seek to find k_{3} for symbol (1) with a_{1} = 1, k_{1} = x and k_{2} = x − 1. Thus we want to fill in k_{3} for

b |\begin{matrix}1 & a_{2} & a_{3} \\ x & x − 1 & k_{3} \end{matrix}| .

(b) Calculate from (3) the candidate b = \frac{2^{2x−1+k_{3}}+1}{2^{2x−1}−2^{x}+1}, calling the denominator d, so that

d = 2^{2x−1} − 2^{x} + 1.

(c) To obtain the QO(2^{2x−1}−2^{x}+1), we construct symbol (1), beginning with 2^{2x−1}−2^{x}+1 in the b position. After repeated use of (2), we produce

2^{2x−1}−2^{x}+1 |\begin{matrix}1 & (2^{x−1} − 1) & (2^{2x−2} − 2^{x−1} − 2^{x−2} + 1) & (2^{x+1} − 2^{x} − 1) & (2^{2x−1} − 2^{x} + 1) \\ x & 1 & x − 2 & 1 & 2x − 2 \end{matrix}|

(with an odd number, 5, of columns!).

(d) Since the number of columns is odd, we are in case (ii) with the QO(2^{2x−1} − 2^{x} + 1) = 4x − 2, so we express the general symbol as

b = \frac{2^{(4x−2)(2y+1)} + 1}{2^{2x−1} − 2^{x} + 1} |\begin{matrix}1 & a_{1} & a_{3} \\ x & x − 1 & (8xy + 2x − 4y − 1) \end{matrix}| ,  (7)

for x ≥ 2

The numbers in this set turn out to start out fairly large (x = 3, this is our Monster B) and increase at a rapid rate, so we won’t give the table here.

Although we don’t give the explicit values of a_{2} and a_{3} in (6) and (7), it is an excellent exercise in algebra to work these out for particular values of f(x) and x, using (2), starting with b, when the algorithm produces a suitable value for b.

Our preliminary investigations indicate that we still have not found all the 3-period folding numbers. So, although we’ve made some progress, at this point, in the interest of saving space, we offer our conjecture.

8 3-period folding numbers conjecture

We have shown that each set of 3-period folding numbers (rows or columns of Table 3, along with Monsters A, B, and D) is an unbounded sequence of numbers. On the basis of our study, we have the Three-period folding numbers conjecture:

There are also an unbounded number of sets of 3-period folding numbers such as (4) and (7).

Questions for the Reader

1. Can you discover another set of 3-period folding numbers similar to (4) and (7)?

2. [Harder] Can you prove, or disprove, our Three-period Folding Numbers Conjecture?

3. Can you devise an algorithm for finding 4-period folding numbers?

4. In papers by Bekes, Pedersen, and Shao [1], Froemke and Grossman [2], Hilton, Pedersen, and Walden [8], McFarlane and Withers [9], and Polster [11], the authors used the basic ideas of Theorems 2 and 3 to discuss their applications in a wide variety of situations, some purely mathematical (in combinatorics or group theory), and some connected with the real world. Can the reader find other applications of these Theorems, within mathematics, or in the real world?

5. The first column and first two rows of Table 3 appear in the OEIS along with their interpretations within mathematics or the real world. Do the other entries of Table 3 or any of the 3-period sets of Monster numbers have any other interpretations within mathematics or the real world?

9 Acknowledgments

The authors would like to thank the Student Research Initiative at Santa Clara University for funding this research during the summer of 2012. We would also like to thank Ken Fan and Bin Shao for their valuable comments on earlier versions of this paper. We are also grateful to Nicholas Tran for his help with technical details involving the figures.

References

[1] R. Bekes, J. Pedersen, and B. Shao, Mad tea party cyclic partitions, College Math. J. 42 (2012), 25–36.

[2] J. Froemke, and G. W. Grossman, An algebraic approach to some number-theoretical problems arising from paper-folding regular polygons, Amer. Math. Monthly 95 (1998), 289–307.

[3] P. Hilton, D. Holton, and J. Pedersen, Mathematical Reflections — In a Room with Many Mirrors, Undergraduate Texts in Mathematics, Springer-Verlag, 1998.

[4] P. Hilton, D. Holton, and J. Pedersen, Mathematical Vistas — In a Room with Many Windows, Undergraduate Texts in Mathematics, Springer-Verlag, 2002.

[5] P. Hilton and J. Pedersen, Approximating any regular polygon by folding paper; an interplay of geometry, analysis and number theory, Math. Mag. 56 (1983), 141–155.

[6] P. Hilton and J. Pedersen, Some arithmetical connections between folding numbers and generalized Fibonacci and Lucas numbers, Bull. Belg. Math. Soc. Simon Stevin (Series B) 45 (1993), 273–296.

[7] P. Hilton and J. Pedersen A Mathematical Tapestry, Cambridge University Press, 2010.

[8] P. Hilton, J. Pedersen, and B. Walden, A property of complete symbols: an ongoing saga connecting geometry and number theory, in Homage to a Pied Piper, A. K. Peters, 2009, pp. 53–72.

[9] C. McFarlane and W. D. Withers, Dynamical systems and irrational angle construction by paper-folding, Amer. Math. Monthly 115 (2008), 355–358.

[10] J. Pedersen, Asymptotic Euclidean type constructions without Euclidean tools, Fibonacci Quart. 9 (1971), 199–216.

[11] B. Polster, Variations on a theme in paper-folding, Amer. Math. Monthly 111, (2004), 39–47.

[12] N. J. A. Sloane, The On-line Encyclopedia of Integer Sequences, http://oeis.org.

2010 Mathematics Subject Classification: Primary 11A99; Secondary 11B50, 51M15. Keywords: number theory, algorithm, paper-folding, sequence.

(Concerned with sequences \underline{A000225}, \underline{A002450}, \underline{A007583}, \underline{A020514}, \underline{A020515}, \underline{A020516}, \underline{A020518}, \underline{A020519}, \underline{A020521}, \underline{A023001}, \underline{A034496}, \underline{A034665}, \underline{A034674}, \underline{A083318}, \underline{A131865}, \underline{A132469}, \underline{A133853}, \underline{A135576}, and \underline{A218723}.)

Received April 10 2013; revised versions received December 30 2013; January 23 2016; February 6 2016. Published in Journal of Integer Sequences, March 19 2016.

Return to Journal of Integer Sequences home page.