Thursday, September 29, 2011

More divisor function thoughts

I had some time to sit down with a pen and paper to figure out a better way of getting all the divisors out of a number.

I don't think there are any clever tricks using recursion I can use. I went down that path because it worked for something else but I don't think it will work here.

This makes sense in hindsight (and it's a testament to how poor at basic arithmetic I am) that I only need to test to half the number.

For example, the number 90 has 10 divisors: 1, 2, 3, 5, 9, 10, 18, 30, 45, 90. Obviously I don't need to test beyond half the number (which holds true for odd numbers, too).

I might have even stumbled upon a way of detecting square numbers.

64's divisors are 1, 2, 8, 16, 32, 64. If you see the symmetry in both 90 and 64's divisors you can see a pattern.

90: 1,2,3,5,9,10,18,30,45,90
Taking the outer numbers and working out way pairwise inward we have:
(1,90)(2,45)(3,30)(5,18)(9,10)
These are factors of 90.

64:1,2,4,8,16,32,64
Doing the same thing we find a slight difference - there are an odd number of divisors.
(1,64)(2,32)(4,16)(8,?)
We of course know that 8*8 is 64. This makes me wonder if all squares have an odd number of divisors, or if there are number with an odd number of divisors that
aren't squares.

25 is a square and has an odd number: 1,5,25

So, just some thoughts. I could quickly spin off my program to test for stuff like that.

Anyways I can quickly change my program to only loop n mod x and test for 0 such that x only goes to half of n instead of all the way up to n.

No comments:

Post a Comment