A few words about PWW #25

In my previous post I made images like this:

What’s going on? Well, first, it’s easy to notice that each grid starts with 0 in the upper-left square; 1 is one square down and to the right of 0, then 2 is one square down and to the right of 1, and so on….

When we get to an edge, we “wrap around” from the bottom to the top and/or from the right to the left. For example, in the grid above, notice how the 4 is still one space to the right of the 3, but in the top row; likewise, the 7 is below the 6 but in the left column; then the 8 immediately wraps back around to the top row, and so on.

In other words, we can imagine that we are really making a straight diagonal line, but the bottom edge of the grid is “glued” to the top edge, and the right edge is glued to the left edge (making a torus, aka donut).

Equivalently, we can imagine gluing a bunch of copies of the grid together along their edges, and the numbers just count in a straight diagonal line, moving from one grid to the next, like this:

Although really, since each grid is supposed to be a copy, we should draw a diagonal sequence of numbers starting at 0 in the upper-left corner of every copy!

So in this particular example, if we keep doing this, we eventually fill up the entire grid/space:

But sometimes that doesn’t happen; for example:

In this example, when we get to the 5 in the bottom-right corner, we would have to wrap around to the top left again, but the 0 is already there. So the process stops before we actually fill up the whole grid. This is why some of the grids have empty spaces in them. Here’s another slightly more interesting example:

So, what’s the difference? How can you tell whether a particular grid is going to fill up or have empty spaces left over?

Posted in modular arithmetic, number theory, posts without words | Tagged , , , , | 3 Comments

Post without words #25

Image | Posted on by | Tagged | 2 Comments

Goldilogs and the n bears

Once upon a time there was a girl named Goldilogs. As she was walking through the woods one day, she came upon a curious, long house. Walking all round it and seeing no one at home, she tried the door and found that it was open. Inside, she saw a very long row of chairs. She tried sitting in the first chair, but it was too small for her. So she tried sitting in the second chair, but it was also too small. The third chair was too small as well. “Oh dear,” said Goldilogs. “This is going to take all day.”

But then Goldilogs noticed that the chairs were arranged in order, from smallest to largest, and she clapped her hands with delight. “What organized people must live here!” she exclaimed. “I wonder, how ever did they arrange their chairs this way?” So she tried the chair in the middle of the row, and it was too big. Next she tried the chair a quarter of the way along, and it was too small. She continued in this manner, eliminating half of the remaining chairs with each test, until finally she found one that was Just Right. In fact, she found it so quickly that she had plenty of time to sit and enjoy reading from the selection of algorithms textbooks that she found on a shelf, and then she put everything back the way she found it and left before the bears got home.

Posted in computation, humor | Tagged , , , , | 1 Comment

Finding the repetend length of a decimal expansion

We’re still trying to find the prefix length k and repetend length n of the decimal expansion of a fraction a/b, that is, the length of the part before it starts repeating, and the length of the repeating part. In my previous post we found that the prefix length k is fairly simple to find: it’s equal to the maximum number of factors of either 2 or 5 in b.

What about n? This is a bit tricker to do efficiently. Let b' denote the result after removing all factors of 2 or 5 from b, as before. Then we want (10^n - 1) to be evenly divisible by b', or put another way, we want the smallest n such that

10^n \equiv 1 \pmod {b'}.

So the obvious method is to compute 10 \bmod {b'}, 10^2 \bmod {b'}, 10^3 \bmod {b'}, and so on, and find the first which yields 1. Practically speaking, we don’t have to compute 10^n from scratch at each step: we can start with 1, and then at each step multiply the current value by 10 and reduce \pmod {b'}. We keep doing this until we reach 1 again, and record how many steps it took. For example,

\begin{array}{rcl} 10 &\equiv & 10 \pmod{21} \\ 10 \cdot 10 = 100 &\equiv & 16 \pmod{21} \\ 16 \cdot 10 = 160 &\equiv & 13 \pmod{21} \\ 13 \cdot 10 = 130 &\equiv & 4 \pmod{21} \\ 4 \cdot 10 = 40 &\equiv & 19 \pmod{21} \\ 19 \cdot 10 = 190 &\equiv & 1 \pmod{21} \end{array}

This took 6 steps, therefore n = 6 is the smallest n such that 10^n - 1 is divisible by 21; this matches what we saw in the previous posts, for example, the fact that 89/420 has a repetend length of 6 (remember that removing factors of 2 and 5 from 420 yields 21).

This method is correct, but we can do better—although for this we’ll need a little bit of group theory!

  • Recall that \Phi(b') is the set of numbers between 1 and b'-1 (inclusive) which share no common factors with b'.
  • \Phi(b') actually forms a group under multiplication \pmod {b'}: multiplying two values of \Phi(b') always yields another such value, and for every x \in \Phi(b') there is some y \in \Phi(b') such that xy \equiv 1 \pmod{b'}.
  • We are then really asking for the order of the element 10 in the group \Phi(b').
  • By Lagrange’s Theorem, the order of an element must evenly divide the order of the group.
  • The order of a group is just its size; in this case the order of \Phi(b') is \varphi(b'), the Euler totient function of b'.
  • Hence we have learned that n—the order of 10 in the group \Phi(b')—must evenly divide \varphi(b').

We can use this knowledge to find n more quickly than simply counting powers of 10: just list all the divisors of \varphi(b'), try each one by raising 10 to the power of the divisor \pmod {b'} (using fast modular exponentiation of course), and pick the smallest one that yields 1. Using our example from before of b' = 21, we find that \varphi(21) = (3-1)(7-1) = 12, and so n has to be one of 1, 2, 3, 4, 6, or 12. As another, bigger example, suppose b' = 3^5 \cdot 7 \cdot 89 = 151389. Then we can compute

\varphi(b') = (3-1) \cdot 3^4 \cdot (7-1) \cdot (89-1) = 2^5 \cdot 3^5 \cdot 11 = 85536.

(I was going to link to an explanation of how to compute \varphi—but it seems although I’ve mentioned \varphi many times before, I’ve never actually written about how to compute it! I’ll have to do that soon, since it’s a very interesting topic. In any case, if you don’t know how, you can just take my word for now.) This number has 6 \cdot 6 \cdot 2 = 72 divisors we would have to try (since to make a divisor of 2^5 \cdot 3^5 \cdot 11, there are 6 choices for the exponent of 2 (namely, 0 through 5), 6 choices for the exponent of 3, and 2 choices for the exponent of 11). 72 things to try is much, much better than trying every single possible value from 1 up to 151388! I wrote a little computer program to try them all, and it turns out that n = 1188 = 2^2 \cdot 3^3 \cdot 11^1 is the smallest divisor that works. Hence, we find that 1/151389 has a repetend of length 1188 (but I’m sure you knew that already =).

It turns out we can do this computation even faster—but that will have to wait for another post!

Posted in computation, group theory, modular arithmetic, number theory, pattern | Tagged , , , , , , | Leave a comment

Finding the prefix length of a decimal expansion

Remember from my previous post that we’re trying to find the prefix length k and repetend length n of the decimal expansion of a fraction a/b, that is, the length of the part before it starts repeating, and the length of the repeating part. In that post I showed how to reduce it to the following question:

What are the smallest values of k and n such that 10^k \cdot (10^n - 1) is evenly divisible by b?

and I left it at that, with some questions for thought.

  • Can you see why we get to determine the values of k and n separately, i.e. neither value influences the other at all?

    The reason we get to consider k and n separately is that 10^k and (10^n - 1) cannot possibly share any prime factors in common. 10^k = 2^k 5^k only has 2 and 5 as prime factors; on the other hand, (10^n - 1) cannot have 2 or 5 as prime factors since it is equivalent to (-1) \bmod 2 and \bmod 5. So the original question splits into two independent questions: (1) What is the smallest value of k such that 10^k cancels all the factors of 2 and 5 in b? (2) What is the smallest value of n such that (10^n - 1) cancels all the other prime factors in b?

The first sub-question is easy enough to answer: if b = 2^x 5^y b', where b' has no factors of 2 or 5, then choosing k = \max(x, y) is both necessary and sufficient: it will be just enough to cancel all the factors of 2 and 5 in b.

Let’s see how this works. The example we looked at last time was \displaystyle 89/420 = 0.21\overline{190476}. If we factor 420 we get (2^2 \cdot 5) \cdot (3 \cdot 7), so our analysis above says k = 2, since there are two factors of 2. And sure enough, the decimal expansion has a prefix of length 2.

As another example, let’s pick a denominator by its factorization: suppose we have a denominator of 2^2 \cdot 5^4 \cdot 11 \cdot 19 \cdot 37 = 19332500. 5 has a higher exponent than the 2, so we predict the prefix will have length 4: and sure enough, for example,

\displaystyle 1/19332500 = 0.0000\overline{000517263675158412}.

We can try other numerators too, we just have to make sure they are relatively prime to 19332500. For example,

\displaystyle 1500007 / 19332500 = 0.0775\overline{899133583344109659}.

In my next post I’ll talk about how to find the repetend length!

Posted in number theory, pattern | Tagged , , , , | 3 Comments

Finding prefix and repetend length

We interrupt your regularly scheduled primality testing to bring you something else fun I’ve been thinking about. It’s well-known that any rational number a/b has a decimal expansion that either terminates, or is eventually periodic—that is, the digits after the decimal point consist of some initial sequence of digits, followed by a sequence of digits that repeats forever:

a/b = 0.p_1 p_2 \dots p_k \overline{r_1 r_2 \dots r_n}

(Let’s assume a < b; if a > b then we can just pull out the integer part before analyzing the part after the decimal point.) We’ll call p_1 \dots p_k the prefix, which has k digits, and r_1 \dots r_n is the n-digit repetend.

The question is, given a fraction a/b, how long will the prefix and repetend be (i.e. what are the smallest possible values of k and n)? In particular, it possible to compute k and n without simply doing long division?

It turns out that it is possible, and I’d like to explain how it can be done. I wrote about this a long time ago (exactly ten years and two days ago, actually!!) but I think I can do a better job explaining it now.

An example

Let’s start by looking at the fraction

\displaystyle \frac{89}{420} = 0.21\overline{190476}

It starts with a two-digit prefix 21 (that is, k = 2), and after that it repeats the sequence of n = 6 digits 190476 forever.

Let’s play with this a bit. First of all, let’s multiply by 10^2 to shift the prefix over to the left of the decimal point:

\displaystyle 10^2 \cdot \frac{89}{420} = 21.\overline{190476}

Now if we multiply by another 10^6, we shift one entire copy of the repetend to the left of the decimal point as well:

\displaystyle 10^2 \cdot 10^6 \cdot \frac{89}{420} = 21190476.\overline{190476}

If we subtract these, the infinite repeating parts to the right of the decimal point will cancel, and we will be left with an integer:

\displaystyle 10^2 \cdot 10^6 \cdot \frac{89}{420} - 10^2 \cdot \frac{89}{420} = 21190476.\overline{190476} - 21.\overline{190476} = \text{an integer}.

(Of course in this case the integer is 21190476 - 21 = 21190455, but we don’t really care: since we’re only interested in the length of the prefix and repetend, it turns out that it doesn’t actually matter what the integer is, only the fact that it is one!)

We can now factor the left-hand side a bit to get

\displaystyle 10^2 \cdot (10^6 - 1) \cdot \frac{89}{420} = \text{an integer}.

Let’s think about why this is an integer. Note that 420 = 10 \cdot 2 \cdot 21 = 2^2 \cdot 3 \cdot 5 \cdot 7. First, the 10^2 = 2^2 \cdot 5^2 cancels with the 2^2 and 5 in 420, leaving

\displaystyle 5 \cdot (10^6 - 1) \cdot \frac{89}{21}.

Now note that 10^6 - 1 = 999999 = 3^3 \cdot 7 \cdot 11 \cdot 13 \cdot 37 is divisible by 21, so the remaining denominator cancels and we are left with an integer. In fact, as you can check, 6 is the smallest value of n such that 10^n - 1 is divisible by 21.

Generalizing

Let’s generalize: suppose we have

\displaystyle \frac{a}{b} = 0.p_1 \dots p_k \overline{r_1 \dots r_n}

and assume that a/b is in lowest terms, that is, a and b share no common factors. Multiplying by 10^k shifts the prefix to the left of the decimal point,

\displaystyle 10^k \cdot \frac{a}{b} = p_1 \dots p_k.\overline{r_1 \dots r_n},

then multiplying by 10^n and subtracting cancels the repeating part to the right of the decimal point:

\displaystyle 10^k \cdot 10^n \cdot \frac{a}{b} - 10^k \cdot \frac{a}{b} = \text{an integer}.

Again, we can factor the left-hand side, yielding

\displaystyle 10^k \cdot (10^n - 1) \cdot \frac{a}{b} = \text{an integer}.

We want to find the smallest values of k and n which make this work. Note that since we assumed a and b share no common factors, a is actually irrelevant: it doesn’t contribute to cancelling b at all. (This explains why repetends are always the same length for a given denominator.) So in the end, the question becomes:

What are the smallest values of k and n such that 10^k \cdot (10^n - 1) is evenly divisible by b?

Or, put another way, how can we choose k and n in such a way that every prime factor of b also shows up in 10^k \cdot (10^n - 1)? I’ll continue in future posts; for now, I leave you with a few questions:

  • Can you see why we get to determine the values of k and n separately, i.e. neither value influences the other at all? (Hint: which prime factors of b could possibly be canceled by 10^k? Which could be canceled by 10^n - 1?)
  • Can you figure out how to find the right value of k?
  • Can you say anything at all about the right value of n?

(Hints: finding k turns out to be much easier than finding n, and requires only knowing some basic facts about divisibility. Saying useful things about n requires knowing some number theory and/or group theory.)

Posted in number theory, pattern | Tagged , , , | 2 Comments

More on Fermat witnesses and liars

In my previous post I stated, without proof, the following theorem:

Theorem: if n is composite and there exists at least one Fermat witness for n, then at least half of the numbers relatively prime to n are Fermat witnesses.

Were you able to prove this? Here’s one way to do it.

Suppose n is composite and a is a Fermat witness for n—that is, a^{n-1} \not\equiv 1 \pmod n. Let b be some Fermat liar for n, that is, b is relatively prime to n but b^{n-1} \equiv 1 \pmod n. (How do we know there exists a Fermat liar for n, you ask? Well, we don’t, but if there aren’t any then the theorem is obviously true.) Then I claim that ab is also a Fermat witness for n:

(ab)^{n-1} = a^{n-1} b^{n-1} \equiv a^{n-1} \cdot 1 \not \equiv 1 \pmod n

So for every Fermat liar b there is a corresponding Fermat witness ab. The only thing we might worry about is that some of these Fermat witnesses might not be distinct. But in fact, since a is relatively prime to n, multiplication by a modulo n is invertible, so ab_1 and ab_2 must be distinct modulo n whenever b_1 and b_2 are. This proves that there are at least as many Fermat witnesses as there are liars; hence at least half are witnesses.

This means that, as long as there is at least one Fermat witness for n, each a we pick has a probability of at least 1/2 of revealing that n is composite. So if we pick k different values for a and all of them yield a^{n-1} \equiv 1 \pmod n, we can conclude that there is only a 1/2^k chance that a is composite. That’s pretty good, and it’s nice that the probability is independent of n.

However, there’s one big flaw, which relates to my third question from the previous post: can there be composite values of n with no Fermat witnesses? More in my next post!

Posted in computation, number theory, primes | Tagged , , , , , | Leave a comment