Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
Associated Topics || Dr. Math Home || Search Dr. Math
_____________________________________________

Formula for Factors of a Number


Date: 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/   
    
Associated Topics:
High School Discrete Mathematics
High School Euclidean/Plane Geometry
High School Geometry
High School Number Theory
High School Puzzles

Search the Dr. Math Library:


Find items containing (put spaces between keywords):
 
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/