## The Summer 2017 Mathematics A To Z: Sárközy’s Theorem

Gaurish, of For the love of Mathematics, gives me another chance to talk number theory today. Let’s see how that turns out.

# Sárközy’s Theorem.

I have two pieces to assemble for this. One is in factors. We can take any counting number, a positive whole number, and write it as the product of prime numbers. 2038 is equal to the prime 2 times the prime 1019. 4312 is equal to 2 raised to the third power times 7 raised to the second times 11. 1040 is 2 to the fourth power times 5 times 13. 455 is 5 times 7 times 13.

There are many ways to divide up numbers like this. Here’s one. Is there a square number among its factors? 2038 and 455 don’t have any. They’re each a product of prime numbers that are never repeated. 1040 has a square among its factors. 2 times 2 divides into 1040. 4312, similarly, has a square: we can write it as 2 squared times 2 times 7 squared times 11. So that is my first piece. We can divide counting numbers into squarefree and not-squarefree.

The other piece is in binomial coefficients. These are numbers, often quite big numbers, that get dumped on the high school algebra student as she tries to work with some expression like $(a + b)^n$. They’re also dumped on the poor student in calculus, as something about Newton’s binomial coefficient theorem. Which we hear is something really important. In my experience it wasn’t explained why this should rank up there with, like, the differential calculus. (Spoiler: it’s because of polynomials.) But it’s got some great stuff to it.

Binomial coefficients are among those utility players in mathematics. They turn up in weird places. In dealing with polynomials, of course. They also turn up in combinatorics, and through that, probability. If you run, for example, 10 experiments each of which could succeed or fail, the chance you’ll get exactly five successes is going to be proportional to one of these binomial coefficients. That they touch on polynomials and probability is a sign we’re looking at a thing woven into the whole universe of mathematics. We saw them some in talking, last A-To-Z around, about Yang Hui’s Triangle. That’s also known as Pascal’s Triangle. It has more names too, since it’s been found many times over.

The theorem under discussion is about central binomial coefficients. These are one specific coefficient in a row. The ones that appear, in the triangle, along the line of symmetry. They’re easy to describe in formulas. for a whole number ‘n’ that’s greater than or equal to zero, evaluate what we call 2n choose n:

${{2n} \choose{n}} = \frac{(2n)!}{(n!)^2}$

If ‘n’ is zero, this number is $\frac{0!}{(0!)^2}$ or 1. If ‘n’ is 1, this number is $\frac{2!}{(1!)^2}$ or 2. If ‘n’ is 2, this number is $\frac{4!}{(2!)^2}$ 6. If ‘n’ is 3, this number is (sparing the formula) 20. The numbers keep growing. 70, 252, 924, 3432, 12870, and so on.

So. 1 and 2 and 6 are squarefree numbers. Not much arguing that. But 20? That’s 2 squared times 5. 70? 2 times 5 times 7. 252? 2 squared times 3 squared times 7. 924? That’s 2 squared times 3 times 7 times 11. 3432? 2 cubed times 3 times 11 times 13; there’s a 2 squared in there. 12870? 2 times 3 squared times it doesn’t matter anymore. It’s not a squarefree number.

There’s a bunch of not-squarefree numbers in there. The question: do we ever stop seeing squarefree numbers here?

So here’s Sárközy’s Theorem. It says that this central binomial coefficient ${{2n} \choose{n}}$ is never squarefree as long as ‘n’ is big enough. András Sárközy showed in 1985 that this was true. How big is big enough? … We have a bound, at least, for this theorem. If ‘n’ is larger than the number $2^{8000}$ then the corresponding coefficient can’t be squarefree. It might not surprise you that the formulas involved here feature the Riemann Zeta function. That always seems to turn up for questions about large prime numbers.

That’s a common state of affairs for number theory problems. Very often we can show that something is true for big enough numbers. I’m not sure there’s a clear reason why. When numbers get large enough it can be more convenient to deal with their logarithms, I suppose. And those look more like the real numbers than the integers. And real numbers are typically easier to prove stuff about. Maybe that’s it. This is vague, yes. But to ask ‘why’ some things are easy and some are hard to prove is a hard question. What is a satisfying ’cause’ here?

It’s tempting to say that since we know this is true for all ‘n’ above a bound, we’re done. We can just test all the numbers below that bound, and the rest is done. You can do a satisfying proof this way: show that eventually the statement is true, and show all the special little cases before it is. This particular result is kind of useless, though. $2^{8000}$ is a number that’s something like 241 digits long. For comparison, the total number of things in the universe is something like a number about 80 digits long. Certainly not more than 90. It’d take too long to test all those cases.

That’s all right. Since Sárközy’s proof in 1985 there’ve been other breakthroughs. In 1988 P Goetgheluck proved it was true for a big range of numbers: every ‘n’ that’s larger than 4 and less than $2^{42,205,184}$. That’s a number something more than 12 million digits long. In 1991 I Vardi proved we had no squarefree central binomial coefficients for ‘n’ greater than 4 and less than $2^{774,840,978}$, which is a number about 233 million digits long. And then in 1996 Andrew Granville and Olivier Ramare showed directly that this was so for all ‘n’ larger than 4.

So that 70 that turned up just a few lines in is the last squarefree one of these coefficients.

Is this surprising? Maybe, maybe not. I’ll bet most of you didn’t have an opinion on this topic twenty minutes ago. Let me share something that did surprise me, and continues to surprise me. In 1974 David Singmaster proved that any integer divides almost all the binomial coefficients out there. “Almost all” is here a term of art, but it means just about what you’d expect. Imagine the giant list of all the numbers that can be binomial coefficients. Then pick any positive integer you like. The number you picked will divide into so many of the giant list that the exceptions won’t be noticeable. So that square numbers like 4 and 9 and 16 and 25 should divide into most binomial coefficients? … That’s to be expected, suddenly. Into the central binomial coefficients? That’s not so obvious to me. But then so much of number theory is strange and surprising and not so obvious.

## The Summer 2017 Mathematics A To Z: Gaussian Primes

Once more do I have Gaurish to thank for the day’s topic. (There’ll be two more chances this week, providing I keep my writing just enough ahead of deadline.) This one doesn’t touch category theory or topology.

# Gaussian Primes.

I keep touching on group theory here. It’s a field that’s about what kinds of things can work like arithmetic does. A group is a set of things that you can add together. At least, you can do something that works like adding regular numbers together does. A ring is a set of things that you can add and multiply together.

There are many interesting rings. Here’s one. It’s called the Gaussian Integers. They’re made of numbers we can write as $a + b\imath$, where ‘a’ and ‘b’ are some integers. $\imath$ is what you figure, that number that multiplied by itself is -1. These aren’t the complex-valued numbers, you notice, because ‘a’ and ‘b’ are always integers. But you add them together the way you add complex-valued numbers together. That is, $a + b\imath$ plus $c + d\imath$ is the number $(a + c) + (b + d)\imath$. And you multiply them the way you multiply complex-valued numbers together. That is, $a + b\imath$ times $c + d\imath$ is the number $(a\cdot c - b\cdot d) + (a\cdot d + b\cdot c)\imath$.

We created something that has addition and multiplication. It picks up subtraction for free. It doesn’t have division. We can create rings that do, but this one won’t, any more than regular old integers have division. But we can ask what other normal-arithmetic-like stuff these Gaussian integers do have. For instance, can we factor numbers?

This isn’t an obvious one. No, we can’t expect to be able to divide one Gaussian integer by another. But we can’t expect to divide a regular old integer by another, not and get an integer out of it. That doesn’t mean we can’t factor them. It means we divide the regular old integers into a couple classes. There’s prime numbers. There’s composites. There’s the unit, the number 1. There’s zero. We know prime numbers; they’re 2, 3, 5, 7, and so on. Composite numbers are the ones you get by multiplying prime numbers together: 4, 6, 8, 9, 10, and so on. 1 and 0 are off on their own. Leave them there. We can’t divide any old integer by any old integer. But we can say an integer is equal to this string of prime numbers multiplied together. This gives us a handle by which we can prove a lot of interesting results.

We can do the same with Gaussian integers. We can divide them up into Gaussian primes, Gaussian composites, units, and zero. The words mean what they mean for regular old integers. A Gaussian composite can be factored into the multiples of Gaussian primes. Gaussian primes can’t be factored any further.

If we know what the prime numbers are for regular old integers we can tell whether something’s a Gaussian prime. Admittedly, knowing all the prime numbers is a challenge. But a Gaussian integer $a + b\imath$ will be prime whenever a couple simple-to-test conditions are true. First is if ‘a’ and ‘b’ are both not zero, but $a^2 + b^2$ is a prime number. So, for example, $5 + 4\imath$ is a Gaussian prime.

You might ask, hey, would $-5 - 4\imath$ also be a Gaussian prime? That’s also got components that are integers, and the squares of them add up to a prime number (41). Well-spotted. Gaussian primes appear in quartets. If $a + b\imath$ is a Gaussian prime, so is $-a -b\imath$. And so are $-b + a\imath$ and $b - a\imath$.

There’s another group of Gaussian primes. These are the numbers $a + b\imath$ where either ‘a’ or ‘b’ is zero. Then the other one is, if positive, three more than a whole multiple of four. If it’s negative, then it’s three less than a whole multiple of four. So ‘3’ is a Gaussian prime, as is -3, and as is $3\imath$ and so is $-3\imath$.

This has strange effects. Like, ‘3’ is a prime number in the regular old scheme of things. It’s also a Gaussian prime. But familiar other prime numbers like ‘2’ and ‘5’? Not anymore. Two is equal to $(1 + \imath) \cdot (1 - \imath)$; both of those terms are Gaussian primes. Five is equal to $(2 + \imath) \cdot (2 - \imath)$. There are similar shocking results for 13. But, roughly, the world of composites and prime numbers translates into Gaussian composites and Gaussian primes. In this slightly exotic structure we have everything familiar about factoring numbers.

You might have some nagging thoughts. Like, sure, two is equal to $(1 + \imath) \cdot (1 - \imath)$. But isn’t it also equal to $(1 + \imath) \cdot (1 - \imath) \cdot \imath \cdot (-\imath)$? One of the important things about prime numbers is that every composite number is the product of a unique string of prime numbers. Do we have to give that up for Gaussian integers?

Good nag. But no; the doubt is coming about because you’ve forgotten the difference between “the positive integers” and “all the integers”. If we stick to positive whole numbers then, yeah, (say) ten is equal to two times five and no other combination of prime numbers. But suppose we have all the integers, positive and negative. Then ten is equal to either two times five or it’s equal to negative two times negative five. Or, better, it’s equal to negative one times two times negative one times five. Or suffix times any even number of negative ones.

Remember that bit about separating ‘one’ out from the world of primes and composites? That’s because the number one screws up these unique factorizations. You can always toss in extra factors of one, to taste, without changing the product of something. If we have positive and negative integers to use, then negative one does almost the same trick. We can toss in any even number of extra negative ones without changing the product. This is why we separate “units” out of the numbers. They’re not part of the prime factorization of any numbers.

For the Gaussian integers there are four units. 1 and -1, $\imath$ and $-\imath$. They are neither primes nor composites, and we don’t worry about how they would otherwise multiply the number of factorizations we get.

But let me close with a neat, easy-to-understand puzzle. It’s called the moat-crossing problem. In the regular old integers it’s this: imagine that the prime numbers are islands in a dangerous sea. You start on the number ‘2’. Imagine you have a board that can be set down and safely crossed, then picked up to be put down again. Could you get from the start and go off to safety, which is infinitely far away? If your board is some, fixed, finite length?

No, you can’t. The problem amounts to how big the gap between one prime number and the next largest prime number can be. It turns out there’s no limit to that. That is, you give me a number, as small or as large as you like. I can find some prime number that’s more than your number less than its successor. There are infinitely large gaps between prime numbers.

Gaussian primes, though? Since a Gaussian prime might have nearest neighbors in any direction? Nobody knows. We know there are arbitrarily large gaps. Pick a moat size; we can (eventually) find a Gaussian prime that’s at least that far away from its nearest neighbors. But this does not say whether it’s impossible to get from the smallest Gaussian primes — $1 + \imath$ and its companions $-1 + \imath$ and on — infinitely far away. We know there’s a moat of width 6 separating the origin of things from infinity. We don’t know that there’s bigger ones.

You’re not going to solve this problem. Unless I have more brilliant readers than I know about; if I have ones who can solve this problem then I might be too intimidated to write anything more. But there is surely a pleasant pastime, maybe a charming game, to be made from this. Try finding the biggest possible moats around some set of Gaussian prime island.

Ellen Gethner, Stan Wagon, and Brian Wick’s A Stroll Through the Gaussian Primes describes this moat problem. It also sports some fine pictures of where the Gaussian primes are and what kinds of moats you can find. If you don’t follow the reasoning, you can still enjoy the illustrations.

## Proper.

So there’s this family of mathematical jokes. They run about like this:

A couple people are in a hot air balloon that’s drifted off course. They’re floating towards a hill, and they can barely make out a person on the hill. They cry out, “Where are we?” And the person stares at them, and thinks, and watches the balloon sail aimlessly on. Just as the balloon is about to leave shouting range, the person cries out, “You are in a balloon!” And one of the balloonists says, “Great, we would have to get a mathematician.” “How do you know that was a mathematician?” “The person gave us an answer that’s perfectly true, is completely useless, and took a long time to produce.”

(There are equivalent jokes told about lawyers and consultants and many other sorts of people.)

A lot of mathematical questions have multiple answers. Factoring is a nice familiar example. If I ask “what’s a factor of 5,280”, you can answer “1” or “2” or “55” or “1,320” or some 44 other answers, each of them right. But some answers are boring. For example, 1 is a factor of every whole number. And any number is a factor of itself; you can divide 5,280 by 5,280 and get 1. The answers are right, yes, but they don’t tell you anything interesting. You know these two answers before you’ve even heard the question. So a boring answer like that we often write off as trivial.

A proper solution, then, is one that isn’t boring. The word runs through mathematics, attaching to many concepts. What exactly it means depends on the concept, but the general idea is the same: it means “not one of the obvious, useless answers”. A proper factor, for example, excludes the original number. Sometimes it excludes “1”, sometimes not. Depends on who’s writing the textbook. For another example, consider sets, which are collections of things. A subset is a collection of things all of which are already in a set. Every set is therefore a subset of itself. To be a proper subset, there has to be at least one thing in the original set that isn’t in the proper subset.

## A Forest of 240 Factor Trees

I admit this is a little self-indulgent, but, what the heck. You might also like the factor trees for the extremely factorable number 240 that Ivasallay’s put up at Find The Factors.

• 240 is a composite number.
• Prime factorization: 240 = 2 x 2 x 2 x 2 x 3 x 5, which can be written (2^4) x 3 x 5
• The exponents in the prime factorization are 4, 1 and 1. Adding one to each and multiplying we get (4 + 1)(1 + 1)(1 + 1) = 5 x 2 x 2 = 20. Therefore 240 has 20 factors.
• Factors of 240: 1, 2, 3, 4, 5, 6, 8, 10, 12, 15, 16, 20, 24, 30, 40, 48, 60, 80, 120, 240
• Factor pairs: 240 = 1 x 240, 2 x 120, 3 x 80, 4 x 60, 5 x 48, 6 x 40, 8 x 30, 10 x 24, 12 x 20, or 15 x 16
• Taking the factor pair with the largest square number factor, we get √240 = (√16)(√15) = 4√15 ≈ 15.492.

Because 240 has so many factors, it is possible…

View original post 185 more words

## Factor Finding

I imagine everyone in the world has seen this already, but, over on the Find The factors blog is a string of mathematics puzzles. The one to which I link amounts to writing out a multiplication table, where the rows and columns have been scrambled, and you have to work out which row is which based on the select handful of numbers in the table. That is, the first row might be the multiples of 6, the next row the multiples of 9, the next row the multiples of 4; and the first column the multiples of 4, the second column multiples of 5, the third column multiples of 2, and so on.

I think this is a fun exercise. It’s more challenging than the day’s Jumble (which this year has had a disturbing number of ones that can be solved on sight, without any unscrambling of words), without being so time-consuming as Sudoku, and if you’re trying to learn the times tables (which I admit probably few readers around here are trying to do) there’s a lot of chance to think about what the multiplication tables are to work out the puzzle. There’s a fresh puzzle every week, as well as a good number of tools for people learning multiplication.

## Reblog: More Factorization Diagrams

The Math Less Traveled has followed up the factorization diagrams post — rendering visually the integers multiplied together to get an integer — of a month ago with an expansion of the idea. This version includes not just arranging points into regular polygons, and polygons of polygons, but into colored polygons.

At least some of these charts, or charts inspired by them, belong on classroom walls.

My post on factorization diagrams from a month ago turned out to be (unexpectedly) quite popular! I got ten times as many hits as usual the day it was published, and since then quite a few other people have created their own variations. The purpose of this post is twofold: first, to round up links to a bunch of the variations, and second, to show off some new and improved factorization diagrams!

I should mention a couple of my inspirations: first, the book You Can Count on Monsters does something similar, though it takes a more artistic and representational approach, in contrast to my strictly geometric approach. My other inspiration was Sondra Eklund’s super-cool prime factorization sweater (and other prime factorization visualizations) which uses a different color to represent each prime.

Not long after I published my original factorization diagrams post, the Internet got right to work creating the…

View original post 1,048 more words

## Reblog: Factorization diagrams

The Math Less Traveled over here shows off a lovely way of visualizing the factoring of integers by putting them into patterns inspired by the regular polygons. Some numbers factor into wonderfully obvious patterns; some turn into muddles of dots because integers just work that way. They’re all attractive ways to look at numbers, though.

In an idle moment a while ago I wrote a program to generate "factorization diagrams". Here’s 700:

It’s easy to see (I hope), just by looking at the arrangement of dots, that there are $latex 7 \times 5 \times 5 \times 2 \times 2$ in total.

Here’s how I did it. First, a few imports: a function to do factorization of integers, and a library to draw pictures (yes, this is the library I wrote myself; I promise to write more about it soon!).

>moduleFactorizationwhere>>importMath.NumberTheory.Primes.Factorisation(factorise)>>importDiagrams.Prelude>importDiagrams.Backend.Cairo.CmdLine>>typePicture=DiagramCairoR2

The primeLayout function takes an integer n (assumed to be a prime number) and some sort of picture, and symmetrically arranges n copies of the picture.

View original post 583 more words

## Something I Didn’t Know About Trapezoids

I have a little iPad app for keeping track of how this blog is doing, and I’m even able to use it to compose new entries and make comments. (The entry about the lottery was one of them.) Mostly it provides a way for me to watch the count of unique visits per day, so I can grow neurotic wondering why it’s not higher. But it also provides supplementary data, such as, what search queries have brought people to the site. The “Trapezoid Week” flurry of posts has proved to be very good at bringing in search referrals, with topics like “picture of a trapezoid” or “how do I draw a trapezoid” or “similar triangles trapezoid” bringing literally several people right to me.

## Eliminating Your Footprints

When last we discussed divisibility rules, particularly, rules for just adding up the digits in a number to tell what it might divide by, we had worked out rules for testing divisibility by eight. In that, we take the sum of four times the hundreds digit, plus two times the tens digit, plus the units digit, and if that sum is divisible by eight, then so was the original number. This hasn’t got the slick, smooth memorability of the rules for three and nine — just add all the numbers up — or the simplicity of checking for divisibility by ten, five, or two — just look at the last digit — but it’s not a complicated rule either.

Still, we came at it through an experimental method, fiddling around with possible rules until we found one which seemed to work. It seemed to work, and since we found out there are only a thousand possible cases to consider we can check that it works in every one of those cases. That’s tiresome to do, but functions, and it’s a legitimate way of forming mathematical rules. Quite a number of proofs amount to dividing a problem into several different cases and show that whatever we mean to prove is so in each ase.

Let’s see what we can do to tidy up the proof, though, and see if we can make it work without having to test out so many cases. We can, or I’d have been foolish to start this essay rather than another; along the way, though, we can remove the traces that show the experimenting that lead to the technique. We can put forth the cleaned-up reasoning and look all the more clever because it isn’t so obvious how we got there. This is another common property of proofs; the most attractive or elegant method of presenting them can leave the reader wondering how it was ever imagined.

## What Makes Eight Different From Nine?

When last speaking about divisibility rules, we had finally worked out why it is that adding up the digits in a number will tell you whether the number is divisible by nine, or by three. We take the digits in the number, and add them up. If that sum is itself divisible by nine or three, so is the original number.

It’s a great trick. We have to want to do more. In one direction this is easy to expand. Last time we showed it explicitly by working on three-digit numbers; but we could show that adding a forth digit doesn’t change the reasoning which makes it work. Nor does adding a fifth, nor a sixth. We can carry on until we lose interest in showing longer numbers still work. However long the number is we can just add up its digits and the same divisibile-by-three or divisible-by-nine trick works.

Of course that isn’t enough. We want to check divisibility of more numbers. The obvious thing, at least the thing obvious to me in elementary school when I checked this, was to try other numbers. For example, how about divisibility by eight? And we test quickly … well, 14, one plus four is 5, that doesn’t divide by eight, and neither does fourteen. OK so far. 15 gives us similarly optimistic results. For 16, one plus six is 7, which doesn’t divide by eight, but 16 does, so, ah, obviously there’s something more we have to look at here. Maybe we need to patch up the rule, and look at the sum of the digits plus one and whether that divides eight.

This may sound a little fishy, but it’s at least a normal part of discovering mathematics, at least in my experience: notice a pattern, and try out little cases, and see if that suggests some overall rule. Sometimes it does; sometimes we find exceptions right away; sometimes a rule looks initially like it’s there and we learn something interesting by finding how it doesn’t.

## How To Recognize Multiples Of 100 From Not So Far Away

MJ Howard last week answered my little demonstration that it was easy to tell multiples of two, five, and ten by looking at just the last digit of a whole number, but that there weren’t any ways to tell from just the last digit whether it was divisible by four. He pointed out we could look at the last two digits, and if those were divisible by four, then the entire number would be. This is perfectly true, and it’s only by asserting that I was looking for a rule based on the last digit alone that my forecast of doom about an instant check for divisibility-by-four could be sustained.

Remember the reasoning by which we wrote out a whole number as some string of digits which I call R followed by whatever goes in the units column, which I call a. (I had been thinking of R as in the “rest” of the number, but it struck me over the week that R is also the symbol used in organic chemistry to denote a chain of carbon atoms when one doesn’t really care how many of them are lined up. This interests me as I got on this thread with a set of numbers I called “alcoholic” due to their structural resemblance to organic chemistry’s idea of alcohols.) Since we’re writing in base ten, then, the number written as Ra is ten times R plus a. Ten times R can’t help being divisible by ten, or by any of the factors of ten, which are two and five (and one, which nobody cares about).

## How To Recognize Multiples Of Ten From Quite A Long Way Away

I got so caught up last week talking about the different possible bases that I forgot to the interesting thing I had wanted to talk about those bases. I suppose that will happen as long as I write to passion rather than plan. It gives me something to speak about today, at least.

Here is one thing implied by having a consistent base for all these numbers in which position is relevant: a one in each column represents the base-number of units of whatever the next column over represents. That is, in base ten, a one in the tens column represents ten units of one; a one in the thousands column represents ten units of one hundred. I mention this obvious point because it is so familiar and simple as to pass into invisibility. (It also extends past the decimal point; a one in the hundredths column is equivalent to ten units of a thousandth. But I want to talk about divisibility, in the whole numbers, and so leave fractions for some later time.)

This is tidy, in a way that we don’t see in variable bases. It will give us one tool for neat little divisibility rules. That tool appears just by writing things in the appropriate way, which is the best sort of tool. It saves on time trying to prove it works.

## How I Make Myself Look Foolish

It seems to me that I need to factor numbers more often than most people do. I can’t even attribute this to my being a mathematician, since I don’t think along the lines of anything like mathematical work; I just find that I need to know, say, that 272,250 is what you get by multiplying 2 and 3 to the second power and 5 to the third power and 11 to the second power. And I reliably go to places I know will do calculations quickly, like the desktop Calculator application or what you get from typing mathematical expressions into Google, and find that since the last time I looked they still haven’t added a factorization tool. I have tools I can use, particularly Matlab or its open-source work-just-enough-alike-to-make-swapping-code-difficult replica Octave, which takes a long time to start up for one lousy number.

So I got to thinking: I’ve wanted to learn a bit about writing apps, and surely, writing a factorization app is both easy and quick and would prove I could write something. The routine is easy, too: take a number (272,250) as input; then divide by two as many times as you can (just one, giving 136,125), then divide by three as many times as you can (twice, giving 15,125), then by five as many times as you can (three times, reaching 121), then by seven (you can’t), then eleven (twice, reaching 1), until you’ve run the whole number down. You just need to divide repeatedly by the prime numbers, starting at two, and going up only to the square root of whatever your input number is.

Without bothering to program, then, I thought about how I could make this a more efficient routine. Figuring out more efficient ways to code is good practice, because if you think long enough about how to code efficiently, you can feel satisfied that you would have written a very good program and never bother to actually do it, which would only spoil the beauty of the code anyway. Here’s where the possible inefficiency sets in: how do you know what all the prime numbers up to the square root of whatever you’re interested in is?

## Something Cute With 9’s and a 6.

After the last few essays I’d like to take a moment for a distinct, cute little problem of no practical use but cute.

Write down as many 9’s as you like, and when finished with that place a 6 at the right end. The result is divisible by 6.

That is, whatever number you’ve written, divided by 6, produces a whole number. Divisibility is one of those things which turns up whenever you have a collection of things which can be multiplied, and one thing is divisible by the second if you can find something in your collection so that the second multiplied by your find equals the first. It’s most often used to talk about the integers — the positive counting numbers, their negative counterparts, and zero if we didn’t include that already — and if it isn’t said divisible-with-respect-to-what then integers are what is usually meant. Partly that’s because integers are the first thing where divisibility stands out: if we look at the real numbers, everything is divisible by everything else (as long as that “else” is not zero), and a property that’s (almost) always true is usually too dull to mention. The next topic where divisibility gets mentioned much is usually polynomials, with a few eccentrics holding out for the complex numbers where the real part and the imaginary part are both integers.

There are several ways to prove this string of 9’s followed by 6 is divisible by 6. Here’s a proof which I like.