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?

There’s no way to tell, at least not that humans know of. But if we don’t mind some redundancy, we can say that, apart from two and three, all prime numbers are either one more or one less than a whole multiple of six, so we could use seven and eleven, thirteen and nineteen, twenty-one and twenty-five, and so on, up to the square root of the targeted number.

Ah, but! Twenty-one and twenty-five aren’t nearly prime, and that shows an inefficiency in this system. We’d be dividing by numbers we don’t need to divide by and wasting our time. Could we do better?

Sure. We could list all the prime numbers, from two up through soem sufficiently big number. Computers are very good at holding lists of numbers, and can run through them quite nicely. But how big does my list need to be to cover my basic number-factoring needs? If I knew the largest number I was likely to want to factor I’d be fine, but obviously, I haven’t been paying attention to that or I’d have figured out why I keep wanting to factor numbers.

Well, but I could say that my list of prime numbers goes up to some number, call it M, and therefore, the biggest number I can be sure I can factor is M times … or M plus … ah, what, exactly? And after a good while spent pondering this and trying out short lists of prime numbers to see what the first thing I can’t factor correctly is, I find that I’ve probably hit some nice simple-looking problem in number theory, the field of mathematics entirely devoted to forming nice simple-looking problems that nobody can solve.

So, having felt myself to be sufficiently more foolish, I tallied it as a program which would have been very successful had I written it, and went on to wonder why I come up with so many numbers I need to factor anyway.