divisors

[miriam_e]

Here is something weird. I ran a quick little program today to see what numbers up to 1,000 are most divisible by other numbers. After collecting the results and running them through a sort I became a little puzzled at how the number of divisors seems to collect around certain particular amounts, so I charted the unsorted results to take advantage of our wonderful visual pattern perception. What I saw was a bit of a surprise. It looks really familiar, and I'm not quite sure why.

The horizontal axis lists the numbers between 1 and 1,000 examined.
The vertical axis how many other numbers the number could be divided by. The number itself and 1 were not included, so prime numbers get listed as having zero divisors.

The really interesting numbers here are the ones on the top of the curve, which are (going from top right down to bottom left):
840, 720, 360, 240, 180, 120, 90, 48, 36, 24, 12, and 6
Next time you wonder if the Babylonians had rocks in their heads sticking us with such crazy numbers for calculating angles, think again. They are brilliant numbers. They divide up more easily than any others.

There are some really noteworthy things.
Primes are pretty uncommon, you'd think, but there are 168 of them. Far more uncommon are almost-primes -- numbers that have only one other divisor. There are only 11 of them in the first 1,000 numbers (4, 9, 25, 49, 121, 169, 289, 361, 529, 841, 961).
Only 3 numbers have just 3 divisors (16, 81, 625).
Only 2 numbers have 5 divisors (64 and 729).
There are no numbers below 1,000 with 9 or 11 or 15 divisors, with many more higher up (the gaps become more frequent as you look for greater numbers of divisors).

I wonder why the number of divisors falls into such prominent bands on 0 (prime), 2, 4, 6, 10, 14, and 22. Especially 14! That is such an odd number. It is nothing like the almost random distribution I'd have expected.

Comments

[annie-lyne.livejournal.com]

Any number of the form p^k will have k+1 divisors, where p is prime. The smallest number which has 11 divisors then is 2^10 = 1024.

There can be more work done to show that any number of the form p^kq^j can never have 11 divisors, etc.

[miriam-e.livejournal.com]

Cool! That is interesting. Great food for thought. Thank you.

I've just realised I made a small oversight. In my list I only considered numbers that have simple factors of just 2 numbers multiplied together. I didn't consider those that result from 3 numbers multiplied together (for instance 12 can result from 2*6 or from 3*4, but it can also result from 2*3*2) or greater amounts of numbers multiplied together. The list is still interesting though because of the number of things that come naturally out of such simple two-part operations (for example much of cryptography involves deliberately restricting stuff to just 2 parties).

I'm starting to understand the patterns now. There may be some simple mathematical way of looking at it, but I see it from a procedural standpoint. The pattern grows because of the way some numbers are more divisible than others, and why they are.

For instance:

The numbers that have 0 divisors -- the primes -- there are a lot more of them than I'd expected, but they are like the foundation for everything else.

The numbers with 1 divisor are squares of primes. It doesn't take long for them to grow beyond 1000 -- 31, the 11th prime (not counting 1) squared is 961 already, so it's easy to see why there would be very few of them (only 11 in the positive integers less than 1,000).

The numbers with 2 divisors -- there are lots of them (292) -- are the product of two primes. There are lots of primes so you'd expect lots of numbers with 2 divisors. I haven't looked at them properly yet.

The numbers with 3 divisors are weird. There are only 3 of them (16, 81, 625) and their factors are a prime, the square of that prime, and the cube of that prime. This is because they are the fourth power of a prime (2, 3, 5). It is easy to see why there would be so few of them. The multiplication n*n*n*n can be broken down just 2 ways: (n*n)*(n*n) and n*(n*n*n). There you have your 3 factors.

There are 110 numbers with 4 divisors. I'd expect there to be lots, but I haven't really looked at them yet.

More interesting is why there are only 2 with 5 divisors: 64 and 729. It is easier to see why when you look at them. 64: 2 4 8 16 32 and 729: 3 9 27 81 243 They are progressions of powers like the numbers with 3 divisors and they break apart exactly the same way. They are the 6th power of a prime. n*n*n*n*n*n They can be broken apart as simple multiples of two numbers only 3 ways to give 5 different numbers: n*(n*n*n*n*n), (n*n)*(n*n*n*n), (n*n*n)*(n*n*n). What makes this arrangement so uncommon is that having an even power means that one of the pairings must be a square, and squares grow out of control really quickly.

and so on...

It is like a messy, but interesting, sieve. The way the groups of numbers dance around and pair up is quite pretty, but at times a bit overwhelming.

Oh god I waste time, don't I?
I'm supposed to be working on a picture and looking into whether I can do some VR work for a friend in Western Australia.
Gah!!!

[annie-lyne.livejournal.com]

Here is a trick if you want to work out why certain numbers have so few divisors. Each number can be written as 2^a 3^b 5^c ... p^k, and so on -- the prime decompositions. The number of divisors can be found by multiplying each exponent plus 1 together.

For example: 2^2*3*5^3 = 1500. 1500 has (2+1)(1+1)(3+1) divisors.