The Prechac Transformation

An elegant method for generating symmetric passing patterns from “solo” patterns was proposed by French mathematician and juggler Cristophe Prechac in a post on rec.juggling in June 1999. Prechac states that, “in the basic form of a symmetric passing pattern, all partners do the same sequence of throws, either in phase or out of phase.” In this blog, we will study how and why Prechac’s algorithms work. For simplicity, we’ll limit ourselves to vanilla siteswap sequences as the starting point for the Prechac construction.

Prechac started with the assumption that a given vanilla object siteswap sequence (OSS) is to be juggled with the hand siteswap sequence (HSS) “2”, i.e., with a juggler throwing alternately with the right and left hands. He thus refers to the vanilla OSS as a “solo pattern”.

In Phase Passing

For “in phase” symmetric passing, we start with multiple jugglers doing the same solo pattern with the same timing. Now designate any throw as a pass instead of a self and get each juggler to pass it to another juggler. The concept is illustrated in Figure 1.

The target juggler for a pass could be chosen differently. For example, another possibility is shown in Figure 2.

The in phase symmetric pattern generation can be viewed as a series of siteswap operations. For example, to get the pattern of Figure 1, we first do a siteswap between the T_i throws of J₀ and J₁ as shown in Figure 3.

Next, we do a siteswap between the T_i throws of J₁ and J₂ as shown in Figure 4 to get the in phase symmetric passing pattern.

If B objects were being used in the solo pattern, then N jugglers doing the same pattern would need N*B objects. If they convert this to an in phase symmetric passing pattern using successive siteswap operations, it would still have N*B objects.

Out of Phase Passing

When Prechac wrote his post, most common passing patterns were already following the in phase methodology. The out of phase transformation was, however, something new and we present the generalized 2-step procedure below with an illustrative example.

Step 1 of 2

Let N jugglers be juggling the same solo siteswap sequence “T₀ T₁ …T_i … T_P-1” of period P . However, each successive jugglers throws should be cyclically rotated to the right^[1] by P/N beats. Note that P/N could be a fractional number.

Example

Consider the period P=4 pattern “T₀ T₁ T₂ T₃” = “4 5 1 2” which N=6 jugglers are juggling. We call the jugglers J₀, J₁, J₂, J₃, J₄ and J₅. Now, we rotate each successive juggler’s throws cyclically to the right by 4/6 = 2/3 beats. So the timing is as in Figure 5 where the top row indicates the beat number.

The “4” throw shown in red highlights the cyclic rotation of each juggler’s pattern to the right by 2/3 beats. Notice that the juggler pairs (J₀, J₃), (J₁, J₄) and (J₂, J₅) end up making synchronous throws. We will prove later that whenever P and N are not mutually prime, we will have some jugglers making synchronous throws.

The arrows from siteswap number “1” to siteswap number “2” for each juggler indicate that the object thrown as a “1” by each juggler has to be thrown as a “2” on the next beat for that juggler. We will choose to transform this “1” throw to a pass using step 2 of Prechac’s algorithm.

Step 2 of 2

Replace any T_i (where 0≤i≤P-1) with T_i‘ = T_i ± k*P/N for all the jugglers to get the out of phase symmetric passing pattern “T₀ T₁ … T_i‘p … T_P-1” where the “p” appended to T_i‘ indicates that that throw is a “pass”.

Here, k is an integer such that 1 ≤ k ≤ N-1. Subtraction is permitted only if T_i‘ > 0. The transform may be performed on more than one of the throws in the solo sequence.

Example (contd.)

We choose i = 2 and k = 2 and choose to add k*P/N to T_i = T₂ = 1. Thus, the “1” throw will be transformed to 1+2*4/6 = 7/3. We do this for all the jugglers. As can be seen in Figure 6, the 7/3 throw means that this object should be thrown after 7/3 beats but no juggler is throwing 7/3 beats after their own throw!

This modified throw is now to be considered as a pass and the new 6-juggler passing pattern is “4 5 7/3p 2″ or equivalently, “4 5 2.3p 2″ where the “p” indicates a pass.

To practically juggle this pattern, a couple of questions need to be answered:

1. How many objects should be used?
2. To whom does the 7/3 throw get passed?

Prechac’s algorithm ensures that a unique answer exists for these questions.

Number of Objects

Assuming that the Prechac transformation resulted in a valid pattern, we apply the average theorem to determine the number of objects required. In our example sequence, the sum of siteswap numbers for all six jugglers put together is 6*(4+5+7/3+2) = 80. Period of the siteswap sequence is 4. Therefore, number of objects required = 80/4 = 20.

In general, if the original solo sequence “T₀ T₁ … T_i … T_P-1” for B objects is transformed to “T₀ T₁ … T_i‘p … T_P-1” for N jugglers, where T_i‘ = T_i±k*P/N, then assuming that the new sequence is valid, the number of objects required is:

N*(T₀+T₁+…+T_i‘+…+T_P-1)/P

= N*(T₀+T₁+…+[T_i±k*P/N]+…+T_P-1)/P

= N*(T₀+T₁+…+T_i+…+T_P-1)/P ± N*k*P/(N*P)

= N*B ± k.

We can double check our example using this formula. We started with the solo sequence “4 5 1 2” involving B = 3 objects and added k*P/N with k = 2 and N = 6 to get our transformation. Therefore, number of objects in resultant pattern = N*B + k = 6*3 + 2 = 20.

Passing Details

To determine which juggler passes to which juggler, let us first look at J₀. As remarked earlier, J₀ can not be making the 7/3 throw to himself as he is not scheduled to throw anything 7/3 beats later. Figure 7 suggests two potential candidates to whom J₀ could be making the 7/3 throw, as they need to have an object scheduled to be thrown 7/3 beats after J₀ makes the 7/3 throw.

This apparent confusion about whether J₀ should pass to J₂ or J₅ has arisen because they are throwing synchronously. However, as we can see in Figure 8, J₀ cannot be passing to J₅ because the object that J₅ has to throw as a “5” is being supplied by J₅‘s own “2” throw two beats earlier.

In contrast, J₂ will not have any object to throw as a “2” unless J₀ passes to J₂. This is because J₂‘s own “1” throw has got transformed to 7/3 and so that object is no longer available to be thrown as a “2” one beat later.

Let us work this out in the general case. Let’s say that in the original solo pattern, the object getting thrown as T_i is next thrown as T_j after T_i beats and we apply the Prechac transformation to the T_i throw. In the transformed pattern, T_i will become T_i±k*P/N and this object will become unavailable to be thrown as T_j after T_i beats for each of the jugglers. But for juggler J_x, the juggler number (x±k) mod N will be making the T_j throw after T_i±k*P/N beats due to the offsetting of the jugglers’ throws. Though other jugglers may be making synchronous throws at the same beat, the construction ensures that there is only one juggler who is specifically making the T_j throw at that beat. To prove this, let’s suppose that the cyclic rotation has resulted in two jugglers J_a and J_b with b > a, who are making the T_j throw at the same beat. Now by construction, if juggler J_a is making the T_j throw at beat j, then juggler J_b will be making the T_j throw at beat [j+(b-a)*P/N] mod P. If these two beats are to be the same, then,

j = [j+(b-a)*P/N] mod P, i.e., there exists an integer q such that

P*q+j = j+(b-a)*P/N, i.e.,

q = (b-a)/N

But a ≥ 0 and b ≤ N-1. Also, b > a. Therefore,

0 < (b-a)/N ≤ (N-1)/N < 1, i.e., q = (b-a)/N cannot be an integer. Thus, we arrive at a contradiction, proving that for every juggler, there is a unique other juggler to whom the pass must be made.

Clarifications on the Modulo Operation

We have used the modulo operation in a couple of potentially confusing scenarios which need clarification.

Negative Dividend

To identify the target juggler for a pass, we were interested in juggler number (x±k) mod N, where 0 ≤ x ≤ N-1 and 0 < k ≤ N-1. Here, (x-k) could be negative. The modulo operation is then used in the sense that the remainder should be positive. For example, if x=0 and k=2, then (x-k) = -2. With N = 6, we will consider -2 mod 6 = +4 with quotient = -1, as opposed to considering it to be -2 with quotient = 0. Thus, in our example, if we had chosen to subtract 2*P/N from any T_i, J₀ would be making that pass to juggler number (0-2) mod 6, = 4, i.e., to J₄.

Fractional Dividend

While proving that the target juggler for a pass is unique, we said that if juggler J_a was making the T_j throw at beat j, then juggler J_b would make the T_j throw at beat [j+(b-a)*P/N] mod P. Here, (b-a)*P/N could be a fractional number. For example, let b = 4, a = 2, P = 4 and N = 6. Then (b-a)*P/N = (4-2)*4/6 = 4/3 = 1.33. The modulo operation is to be done on the integer part of the dividend and the result is the remainder obtained thus plus the fractional part of the original dividend. In our example, using j = 0 for convenience, [j+(b-a)*P/N] mod P = 1.33 mod 4 = (1 mod 4) + 0.33 = 1 + 0.33 = 1.33.

Implications of Prechac Transformation

The out of phase construction of the Prechac patterns lends it some interesting characteristics. Sean Gandini’s “Staggered Symmetric Passing” details some of these. Here we look at some other mathematically interesting features.

Minimal Period?

Normally, one considers a solo siteswap sequence written up to the minimal period (e.g., the period P = 1 sequence “3”) to be the same as the sequence generated by multiple repetitions of the minimal period (e.g., the period P = 3 sequence “3 3 3”). However, for Prechac transformations, these are different patterns. The unequal periods mean that the term P/N is different in the two cases and leads to different passing patterns when the out of phase Prechac transformation is applied to them.

Synchronous Throws

If the Highest Common Factor of P and N = HCF(P,N) = H > 1, then H jugglers will be throwing synchronously in the passing pattern. For example, when we transformed the period P = 4 sequence “4 5 1 2” for N = 6 jugglers to “4 5 7/3p 2″ we found that there were always HCF(P,N) = HCF(4,6) = 2 jugglers throwing synchronously: J₀ and J₃, or J₁ and J₄, or J₂ and J₅.

Let us prove the general case. We first recognize that jugglers will be throwing synchronously if their throws have been offset from each other by an integer number of beats. For J₀, the juggler J_x will have an offset of x*P/N beats. With x sweeping from 1 to N-1, the jugglers for which, x*P/N is an integer, will throw synchronously with J₀.

Let HCF(P,N) = H. Then there exist p and n such that P = H*p and N = H*n. Now as x ranges from 1 to N-1, it would hit the values = 1*n, 2*n, …, (H-1)*n. If x = m*n, then x*P/N = m*n*H*p/H*n = m*p = integer. Thus, we’ll get (H-1) values of x for which x*P/N is an integer, i.e., H-1 jugglers will throw synchronous to J₀, i.e., H jugglers will be involved in synchronous throws. The N jugglers can be viewed as n sets of H jugglers. All jugglers in a given set throw synchronously.

Disjoint sets of jugglers

Based on the value of k used for the transformation, we will end up with the set of N jugglers being split into HCF(k,N) sets of jugglers such that one set does not interact with any other set during the passing pattern. For example, when we transformed the period P = 4 sequence “4 5 1 2” for N = 6 jugglers to “4 5 7/3p 2″ using k = 2, juggler x passes to juggler (x±k) mod N, i.e., to juggler (x+2) mod 6. Thus,

J₀ passes to J₂, J₂ passes to J₄, J₄ passes to J₀.

J₁ passes to J₃, J₃ passes to J₅, J₅ passes to J₁.

The set of jugglers J₀, J₂ and J₄ don’t have any interaction with the set of jugglers J₁, J₃ and J₅! Thus, there are HCF(k,N) = HCF(2,6) = 2 disjoint sets of jugglers involved in the passing pattern.

In general, we can show that if HCF(k,N) = H > 1, then a particular chain of passing starting from J₀, will never touch J₁, J₂, …, J_H-1. Each of these jugglers will be part of independent passing chains thus leading to H disjoint sets of jugglers. To see this, let us say that our statement is false and that J_x‘s passing chain will eventually touch J_x+1. Now, assuming k is positive^[2], J_x will pass to juggler (x+k) mod N who will in turn pass to juggler ((x+k)+k) mod N and so on. Then for one of these jugglers to be (x+1), there must exist an m such that:

(x+m*k) mod N = x+1. Therefore, there must be some integer q such that

N*q+x+1 = x+m*k, i.e.,

m*k – N*q = 1.

If HCF(k,N) = H, then let k = H*k’ and N = H*N’. Then,

H*(m*k’-q*N’) = 1. (Equation 1)

Now, m, k’, q and N’ are all integers so the result of the brackets cannot be a fraction. Therefore,

|H*(m*k’-q*N’)| ≥ H

Thus, if H > 1, Equation 1 cannot be satisfied, and the chain of passes originating from J_x will not touch J_x+1. In fact, it will also not touch J_x+2, J_x+3, …, J_x+H-1, thus proving our assertion.

Though two sets of jugglers may not be interacting, they are still connected by the relative timing of their throws when juggling a specific Prechac pattern.

Asymmetric passing

In a remark towards the end of his post, Prechac extended his core idea and showed how symmetric passing patterns could be distorted into asymmetric ones by further offsetting the timing of one or more jugglers. For example, starting with the symmetric passing sequences “3.5p” or “4p 3” for two jugglers, if we shift one of the jugglers’ time origin by half a beat, we will end up respectively with the asymmetric passing patterns “<4p | 3p>” and “<4.5p 3 | 3.5p 3>”^[3] for two jugglers.

Footnotes

1. We could also choose to cyclically rotate to the left and similarly work out the logic for that case.
2. Similar logic works for negative k. This is also true for other places in this blog where we’ve worked with positive k.
3. See the “Passing notation” section here to interpret these sequences.