Formula for Factors of a NumberDate: 11/3/96 at 12:0:16 From: Daniel Subject: Factors in a number Hi, I've been working on a puzzle this last week and though I have a solution of sorts, I'm not really satisfied with it. First I'll explain the original problem: You have a square grid of dots of size (x*x). How many triangles can you draw in this grid? I went about this by finding out how many combinations of lines you can have in a grid in terms of "x", then subtracting all the combinations where all 3 points fall on a straight line. It is this last part which is giving me problems. I can get nearly all the instances where all three points are on a straight line in terms of "x" except one. The lines I can't get an equation for are ones such as a line going through points (0,6) (1,4) (2,2) (3,0). I can get an equation which uses the sum of the number of factors of "x" and some other ugly terms, but not one in terms of "x" alone. What I need is an equation for the number of factors in a number "x" in terms of "x". Can you help me here? Thanks in anticipation, Dan, England Date: 11/17/96 at 23:09:59 From: Doctor Lynn Subject: Re: Factors in a number Dan, I'm afraid there isn't such an equation. There may be one which uses some very high level maths, but that wouldn't be of much use to you. You can see that there wouldn't be a simple formula if you compare the number of factors of, say, 144 and 143. It comes down to the same difficulties that exist when trying to find all of the prime numbers. Prime numbers are numbers which have only one factor (excluding 1), so if you had a formula which gave the number of factors of a particular number, you'd be well on the way to finding all the prime numbers as well. In fact, there is a well-known computer security system, called RSA, which relies on the fact that it is so difficult to find all the factors of a number. Getting back to your problem, however, it would probably be fine to just put F(x) in your equation, if you say that F(x) means the number of factors of x. I find it a little difficult to see what you want this equation to do. If it's any help, the equation of a line through the two points (a,b) and (c,d) can be calculated as follows: y(a-c)=(b-d)x+ad-bc The number of points on a line is the HCF (Highest Common Factor) of |a-c| and |b-d|, plus the two end points. For example, on the line you gave, there are HCF(6,3)=2 points between (0,6) and (3,0). While there is no formula for finding the HCF, there is an algorithm. It goes like this: HCF(0,y)=y HCF(x,y)=HCF(y mod x,x) where y mod x means the remainder when dividing y by x, and it expects y to be greater than x. For example, HCF(75,120) = HCF(45,75) = HCF(30,45) = HCF(15,30) = HCF(0,15) = 15 So there would be 15 points on the line between (0,0) and (75,120), not counting those two points. The method works because any factor of two numbers is a factor of their difference. The relation between the HCF of the numbers and the number of points on the line occurs because in actuality, by using this method, you are trying to split the line into as many equal lengths as possible. This means that the end of each line falls on a dot, so you end up finding the largest number (factor) of line segments which "go into" the line. I hope that helps. If you have any queries or any other questions, please write back. -Doctor Lynn, The Math Forum Check out our web site! http://mathforum.org/dr.math/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/