Home

> urticator.net
Search

About This Site
> Domains
Glue
Stories

Computers
Driving
Games
Humor
Law
Math
> Numbers
Science

Powers and Fractions
Notes About Squares
Decimal Expansions
Repeat Length Again
Number Maze
Primes
Divisibility
Intrinsic Nature of Primes
> Other Topics
Other Topics (2)

Duodecimal
Hexadecimal
Base 60
Operations
 > Repunits
Negative Digits
Two Kinds of Odd

## Repunits

A repunit, or repeated unit, is a number consisting entirely of 1s. I don't like the name, but it seems to be standard, so I guess I'm stuck with it. Anyway, I've never been very familiar with repunits, but they've been turning up a lot recently, and I keep forgetting which ones have which factors, so just for reference I thought I'd make a table.

 1 1 1 2 11 11 3 111 3   37 4 1111 11   101 5 11111 41   271 6 111111 3   7   11   13   37 7 1111111 239   4649 8 11111111 11   73   101   137 9 111111111 32   37   333667 10 1111111111 11   41   271   9091 11 11111111111 21649   513239 12 111111111111 3   7   11   13   37   101   9901

There are some interesting patterns in there, but before I can explain them I'll need to remind you of a couple of things. First of all, when I was talking about fractions in base 2, I observed that repunits of composite length have nice factorizations that are really factorizations of polynomials, and suggested that it would be handy to have a digit that represents -1. Then, when I was talking about divisibility in other bases, I started using the hash mark as such a digit  not to be confused with the sharp sign from Sharps and Flats.

Knowing all that, we can break the repunits into irreducible polynomial factors without even specifying what the base is!

 1 1 1 2 11 11 3 111 111 4 1111 11   101 5 11111 11111 6 111111 11   111   1#1 7 1111111 1111111 8 11111111 11   101   10001 9 111111111 111   1001001 10 1111111111 11   11111   1#1#1 11 11111111111 11111111111 12 111111111111 11   111   101   1#1   10#01

The irreducible polynomial factors may break down further in particular bases; here's what happens in bases 10 and 2. (I've converted the base 2 results into base 10, hope that's not too confusing. For example, 111 in base 2 is the prime number 7.)

 1 1# 32 1 2 11 11 3 3 111 3   37 7 4 101 101 5 5 11111 41   271 31 6 1#1 7   13 3 7 1111111 239   4649 127 8 10001 73   137 17 9 1001001 3   333667 73 10 1#1#1 9091 11 11 11111111111 21649   513239 23   89 12 10#01 9901 13

Each repunit contains exactly one new irreducible polynomial  I'm not sure why that's true, but it is, and I've numbered the rows accordingly in the table.

Now I can explain the main pattern in the original table. Let's call the repunit of length n Rn, and the associated irreducible polynomial Pn. If n is divisible by some number m, then Rn is divisible by Rm because there's a nice factorization; and Rm in turn is divisible by Pm, by definition. So, the numbers that are factors of Pm in some base will be factors of Rn whenever n is a multiple of m.

Actually, that's not quite true  it fails for m = 1, because Rn is never divisible by P1. And where'd that polynomial P1 come from, anyway?! Well, I was planning ahead. Suppose we define one more set of polynomials by the rule Bn = Rn ื P1; then Bn, unlike Rn, really is divisible by Pm whenever n is divisible by m; and in fact Bn is equal to the product of all such Pm. That may sound complicated, but the polynomials Bn are actually extremely simple. For example,

B5 = R5 ื P1 = (b4 + b3 + b2 + b + 1)(b - 1) = b5 - 1.

The same cancellation happens every time, so that Bn = bn - 1 for all n.

Now, the roots of Bn are roots of unity, and roots of unity lie on the unit circle in the complex plane, so when we divide Bn into the parts Pm, we're dividing the circle  which is roughly why the parts Pm are called cyclotomic polynomials. (The roots of the word are cyclo-, as in cyclic, and -tomic, as in atomic, indivisible.) Just for fun, here are some pictures of the roots of Pm.

See how for example P1, P2, P3, and P6 combine to cover the sixth roots of unity?

That was fun, but let's get back to the subject of patterns. I think we've said all there is to say about the main pattern, the pattern in how the repunits break down into cyclotomic polynomials, but there are also a few patterns in how the cyclotomic polynomials break down into factors in base 10.

• The factor 239 in P7 is interesting  it has an unusually short repeat length because it's a factor of P7, but it's also involved in a rare triple exception, as I noted in The Usual Random Thoughts. (In short, 239 in base 13 is 155, and 1552 = 1CCCC = 20000-1.) There's no pattern there, I know, but I couldn't resist pointing it out.
• In both P7 and P11 the factors end in 239 and 649. I don't know what to make of that  that's a good combination for factoring repunits, because 239 ื 649 ≡ 111 mod 1000, but there's a similar combination for any other number in U1000; I don't know why that one should turn up twice.
• The factor 333667 in P9 begs to be explained  but that's easy enough! 1001001 is divisible by 3, since the digits add to 3 (see Divisibility); and when you divide, that's what you get. Why didn't we see a factor like that sooner? Well, we didn't get one from 10101 because 3367 isn't prime, and we didn't get one from 111 because  well, actually we did get one, we just didn't recognize 37 as part of a pattern. (By the way, the reason 3367 isn't prime is that 10101 factors in any base as 111 ื 1#1.)
• The factor 9901 in P12 is part of a similar series. 1#1 is 91, not prime; 10#01 is 9901; and 100#001 (P18) is 999001, not prime.
• The factor 9091 in P10 is part of a similar series, too. 1#1 is 91, still not prime; 1#1#1 is 9091; and 1#1#1#1 (P14) is 909091, prime.
• Now, all those 9s make me think it might be handy to have a digit that represents b-1 regardless of what the base actually is, so that 1#1#1 would be G0G1 (say), 10#01 would be GG01, and so on. The pattern is definitely there  1#1#1 and 10#01 are 2021 and 2201 in base 3, 1011 and 1101 in base 2. (That pretty well sums up why base 2 is weird!)

Finally, let me go back and clarify a couple of things. First, the idea of numbers being polynomials over some unspecified base isn't restricted to repunits and cyclotomic polynomials. For example, the number 299 is never prime, because

299 = 2b2 + 9b + 9 = (b + 3)(2b + 3),

and the number 156 is always an intermediate, because

156 = b2 + 5b + 6 = (b + 2)(b + 3) = (b + 2)#.

(See also the discussion of small factors and carries in Multiplication.)

Second, in spite of the evidence in the table, cyclotomic polynomials don't always consist of evenly-spaced 1s or evenly-spaced alternating 1s and #s against a background of 0s. Some have repeating triplets,

 15 1#01#10#1 21 1#01#010#10#1 33 1#01#01#01#10#10#10#1

some have other, stranger patterns,

 30 110###011 35 1#0001#1#01#1#10#1#1000#1

and some even have other digits! According to an article on cyclotomic polynomials, the first one of those occurs at 105 (for the same reason as in Number Maze!), and here it is, with X being a digit that represents -2.

11100##X##0011111100#0#0#0#0#0011111100##X##00111

See Also

History and Other Stuff
Multiplication in Base 10

@ May (2006)