## 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.

## MJ Howard (@random_bunny) 1:41 am

onWednesday, 26 October, 2011 Permalink |Just in case you don’t know. http://www.wolframalpha.com/input/?i=factor+272250

As an aside, prime factorization is something I find myself doing while stuck in traffic.

LikeLike

## nebusresearch 3:02 am

onWednesday, 26 October, 2011 Permalink |I had no idea about that site. That almost completely saves me from having to write anything of use on my own. Thank you.

After publishing this I started to wonder how closely my little puzzle was tied to the McNuggets Problem.

LikeLike

## MJ Howard (@random_bunny) 3:15 am

onWednesday, 26 October, 2011 Permalink |The McNuggets Problem?

That probably sounds much cooler in German.

LikeLike

## nebusresearch 10:59 am

onWednesday, 26 October, 2011 Permalink |It must; in German it’d join the ranks of things like eigenfunctions and Zustandssummes. And those inclined might get it with a McBier. (If that’s still served; I haven’t been in a German McDonalds in a long long while.)

LikeLike

## 43 McNuggets Made Difficult | nebusresearch 3:00 am

onThursday, 27 October, 2011 Permalink |[…] September 2011 Overused TagsAncient Egypt best fit binomial calculus Christiaan Huygens christohper hibbert Christopher Hibbert commodore 64 compound interest continuity coordinate system differential equations distributive law divisibility factorization finite elements Florian Cajori Francis Sheppard George III Gottfried Wilhelm Leibniz imaginary numbers in-joke induction Leonhard Euler logarithm math Mathematics In Civilization meaningless precision million billion trillion multiplication New York Thruway notation number line number names pi polynomials prices quaternions repeating digits robert benchley statistics test uniform spacing William Herschel Wolfgang Schivelbusch « How I Make Myself Look Foolish | […]

LikeLike

## bugq 1:34 am

onSunday, 30 October, 2011 Permalink |Well, if you only have n primes to work with, the nth of which is M, then you should be able to factor everything up to the (n+1)th prime (let’s call it N). Since N is the first multiple of N, it’s also the first number to have a factor of N, so everything below it should be able to be factored completely by primes M and smaller. Of course, that means that the only way to find out how many numbers you can factor with a certain number of primes is to add to your list of primes. :P

LikeLike

## nebusresearch 3:38 pm

onTuesday, 1 November, 2011 Permalink |Yes, that’s the problem. If I have all the prime numbers listed up to N, then I know I can factor everything up to N+1. It’d be nice if I could say I can certainly factor up to, say, 1.5 times N, or at least have a 50-50 chance of factoring everything up to twice N, or something that extends the range some. Too bad.

LikeLike