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.

111
21111
31113   37
4111111   101
51111141   271
61111113   7   11   13   37
71111111239   4649
81111111111   73   101   137
911111111132   37   333667
10111111111111   41   271   9091
111111111111121649   513239
121111111111113   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!

111
21111
3111111
4111111   101
51111111111
611111111   111   1#1
711111111111111
81111111111   101   10001
9111111111111   1001001
10111111111111   11111   1#1#1
111111111111111111111111
1211111111111111   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.)

11#321
211113
31113   377
41011015
51111141   27131
61#17   133
71111111239   4649127
81000173   13717
910010013   33366773
101#1#1909111
111111111111121649   51323923   89
1210#01990113

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, …

151#01#10#1
211#01#010#10#1
331#01#01#01#10#10#10#1

… some have other, stranger patterns, …

30110###011
351#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)