Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I have used Stack Overflow but I'm new to this site so I apologize if this is a trivial question. I am creating mathematics software using javascript. I am using a for loop to find all factors for a given integer (n) as follows (simplified version):

n = someInteger;

for (i = 1; i <= n; i++) {
    if (n % i == 0) {
        var msg = 'The numbers ' + i + ' and ' + (n / i) + ' are factors of n';
        alert(msg);
    }
}

In brief, the loop cycles through all integers 1 to n and for each integer, calculates n mod i. If the modulus is 0, the pair i and n/i is a pair of factors for n. However, a la the commutative property, I don't want to "double count" pairs that have simply had their order switched. For example, in my method, if e.g. n = 10, 2 x 5 is a unique pair of factors but so is 5 x 2.

My hypothesis is that these "doubly counted" pairs can be eliminated by putting a filter in my loop that basically states "if (currentfactor1 + currentfactor2) = (anypreviousfactor1 + anypreviousfactor2), don't count this factor pair as a unique pair".

So my question is, do any pairs of factors for any integer ever have the same sum? My suspicion is no but I can't find proof of this. I took a couple of sample integers with several pairs of factors (two examples):

144 (1 x 144 (sum = 145), 2 x 72 (sum = 74), 3 x 48 (sum = 51), 4 x 36 (sum = 40), 6 x 24 (sum = 30), 8 x 18 (sum = 26), 9 x 16 (sum = 25), 12 x 12 (sum = 24) )

300 (1 x 300 (sum = 301), 2 x 150 (sum = 152), 3 x 100 (sum = 103), 4 x 75 (sum = 79), 5 x 60 (sum = 65), 6 x 50 (sum = 56), 10 x 30 (sum = 40), 12 x 25 (sum = 37), 15 x 20 (sum = 35) )

Can anyone please shed some light on this? Thanks for any help

share|improve this question
1  
This doesn't answer your final question, but if you're worried about double counting, why don't you just divide your final result by two? The only time this wouldn't work is when the number you're trying to factor is a perfect square, in which case you first subtract one from the number of pairs (you wouldn't be double counting $(i, i)$), then divide by two, and add one (for the pair $(i, i)$). Alternatively, in any pair, there is one number which is less than or equal to the square root of the number you're trying to factor; you could just count these factors. –  Michael Albanese Jun 5 at 14:45
    
Having said all that, you should probably ignore these possibilities until you've figured out whether your current strategy will work. –  Michael Albanese Jun 5 at 14:49
    
Thanks @MichaelAlbanese...at about the same time you posted this the same thought came to my mind. You're right...that is a valid solution that can be implemented and will work. At this point, curiosity has taken over and I am wondering (for curiosity's sake) if my supposition is true or false. –  The One and Only ChemistryBlob Jun 5 at 14:53
1  
The easy way to avoid the double counting is to make your loop condition $i \le \sqrt n$ instead of $i \le n$. It will finish much sooner too, because it has to run many fewer times. –  MJD Jun 5 at 15:03
    
OK...I see. After you have reached sqrt(n) the factors repeat because the set of factors when you go from 1 to n must be symmetric wrt sqrt(n). Nice. –  The One and Only ChemistryBlob Jun 5 at 15:08

3 Answers 3

up vote 1 down vote accepted

The answer to your question is no. Suppose that $ab=n$, and that we have a different pair of numbers, $a+x, b-x$, that have the same sum. Their product is $(a+x)(b-x)=ab+x(b-a-x)=n+x(b-a-x)$. If this product is again $n$, then $$x(b-a-x)=0$$

If the product is zero, then either $x=0$ (and the new numbers are the same as the old ones) or $b-a-x=0$, or $x=b-a$ (and $a,b$ simply switched places).

share|improve this answer
    
Excellent proof...This site is great. I earned my PhD in chemistry but minored in mathematics in college...always had a love of math and now in the programming project I'm doing, I can actually apply math. Your answer helps me understand this problem without the use of a graph...thanks for your help. –  The One and Only ChemistryBlob Jun 5 at 15:25
    
Although each answer was uniquely excellent, I voted this as the best answer because I am biased towards analyzing functions by graphs, but despite this bias this solution really helped me "graphlessly" (new word) understand the question I was asking –  The One and Only ChemistryBlob Jun 5 at 15:39

Let $n$ be positive. Then for positive real $x$, the function $x+\frac{n}{x}$ decreases until $x=\sqrt{n}$ and then increases. So for any $k$ there are at most two real positive values of $x$ such that $x+\frac{n}{x}=k$.

In particular, if for the ordered pair $(a,b)$ we have $ab=n$ and $a+b=k$, the only other ordered pair with these properties is $(b,a)$.

share|improve this answer
    
I like Mark Bennet's somewhat better. But mine has the virtue of being more explicitly geometrical. –  André Nicolas Jun 5 at 15:26
    
Wow...great solution. Focusing on x > 0, dy/dx = 1 - (n/x^2), which = 0 when x = sqrt(n). This is a local minimum since (n/x^2) must be less than one when x > sqrt(n) and thus dy/dx > 0 (and when x < sqrt(n), dy/dx < 0), and f(x) increasing beyond x > sqrt(n), so any horizontal line drawn through f(x) will only intersect f(x) at one set of unique points –  The One and Only ChemistryBlob Jun 5 at 15:42

If $a+b=p$ and $ab=q$ then $a,b$ are roots of the quadratic equation $$(x-a)(x-b)=x^2-px+q=0$$If $c\neq a; c\neq b$ then $(c-a)(c-b)\neq 0$ and $c$ is not a root. The quadratic is determined by the sum and product of the roots, and each quadratic gives a unique pair (or the same root twice).

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.