We have so much in common

Let S S be the set of all positive integers n n such that each of n n and n + 1 n + 1 have exactly four divisors and have their divisors add to the same value.

Let m m be the number of elements in S S and b b be the sum of these m m elements.

Find m + b . m + b.


Inspired by Paul Ryan Longhas


The answer is 15.

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

4 solutions

First, we know that one of n n or n + 1 n + 1 is even. Suppose n n is even; then the divisors of n n are 1 , 2 , n 2 1, 2, \frac{n}{2} and n n . The divisors of n + 1 n + 1 will then be 1 , p , n + 1 p 1, p, \frac{n + 1}{p} and n + 1 n + 1 for some prime p > 2. p \gt 2. For the divisors of both numbers to have the same sum we must have

1 + 2 + n 2 + n = 1 + p + n + 1 p + ( n + 1 ) 1 + 2 + \frac{n}{2} + n = 1 + p + \frac{n + 1}{p} + (n + 1)

1 + n 2 = p + n + 1 p \Longrightarrow 1 + \frac{n}{2} = p + \frac{n + 1}{p}

n 2 n p = p + 1 p 1 \Longrightarrow \frac{n}{2} - \frac{n}{p} = p + \frac{1}{p} - 1

n = 2 ( p 2 p + 1 ) p 2 = 2 ( p + 1 ) + 6 p 2 . \Longrightarrow n = \dfrac{2(p^{2} - p + 1)}{p - 2} = 2(p + 1) + \dfrac{6}{p - 2}.

We see that n n will be integral only for p = 3 p = 3 and p = 5 p = 5 , which both yield n = 14. n = 14.

If it were n + 1 n + 1 that were even, then the divisor sums would be such that

1 + 2 + n + 1 2 + ( n + 1 ) = 1 + p + n p + n 1 + 2 + \frac{n + 1}{2} + (n + 1) = 1 + p + \frac{n}{p} + n

n 2 n p = p 7 2 \Longrightarrow \frac{n}{2} - \frac{n}{p} = p - \frac{7}{2}

n = p ( 2 p 7 ) p 2 = 2 p 3 6 p 2 . \Longrightarrow n = \dfrac{p(2p - 7)}{p - 2} = 2p - 3 - \dfrac{6}{p - 2}.

We see that n n will be integral only for p = 3 p = 3 and p = 5 p = 5 , but this time the corresponding values for n n will be 3 -3 and 5 5 , neither of which has four divisors, so this case can be discarded.

Thus there is only one element in S S , namely 14 14 , and so m + b = 1 + 14 = 15 . m + b = 1 + 14 = \boxed{15}.

Thanks...awesomely explained :) :)

Pranay Kumar - 5 years, 9 months ago

Hi Brian. My solution was basically equivalent to yours. The only thing I'd like to add is that I think it's worth taking a moment at the beginning to relabel. E.g. if you define { E , O } = { n , n + 1 } \{E, O \} = \{n, n+1\} so that E E is even and O O is odd, then the similarities between your two cases ( n n even or odd) become much more apparent.

Peter Byers - 5 years, 11 months ago

This question is a rephrasing of this question .

Brian Charlesworth - 6 years, 3 months ago

Log in to reply

About the tenth line wouldnt n be equal to a integer with p=8 too?

Mr Yovan - 4 years, 11 months ago

Log in to reply

Yes, it would, but earlier in the proof it was specified that p p must be a prime.

Brian Charlesworth - 4 years, 11 months ago

I think there is a slight problem in the question. Actually there are infinite numbers which satisfy the given condition.Here's how

Here the question says that the two consecutive numbers n and n+1 have exactly four divisors and have the divisors add up to the same value. I observed that the number which is derived by the product of two numbers always has 4 divisors(1 , the number itself and the two other primes). So let the two numbers satisfying the above condition be n and n+1.

Let n = ab and n+1=cd where a,b,c,d are prime numbers.

Let us now transfer the given condition from english to mathematics.

ab=cd+1 (1)

and

1+a+b+ab=1+c+d+cd

a+b+cd+1=c+d+cd (from 1)

So a+b = c+d+1

(a+b) - (c+d) = 1

So the sum of two different primes should be 1 more than the sum of the other two primes.(condition 1)

Now let us list down a few prime numbers.....

2,3,5,7,11,13,17,19,23,29............

Consider 2,3 to be a set .Now if we pick twin primes and group it in such a way that the larger number goes with two and the smaller number goes with three,then we will have a pair which satisfies condition 1. Which implies that the product of these two numbers in a pair will yield two numbers which satisfy the given condition in the problem.

For example

5,7 are a twin prime pair.(7+2) - (5+3) = 1.

7x2=14 5x3=15.

14,15 have four factors and the sum of their divisors is equal to 24.

Similarly there can be many numbers possible.(Since there are infinite twin primes) So we cannot determine the number of elements in set S.

Am I wrong??? If I am can you correct me.....

Hari prasad Varadarajan - 6 years, 3 months ago

Log in to reply

But look at the twin primes 11 11 and 13 13 , for example. ( 2 + 13 ) ( 3 + 11 ) = 1 (2 + 13) - (3 + 11) = 1 but 2 13 = 26 2*13 = 26 and 3 11 = 33 3*11 = 33 are not consecutive. In general, when we have such a pairing as you describe, i.e., ( 2 + ( p + 2 ) ) ( 3 + p ) = 1 (2 + (p + 2)) - (3 + p) = 1 for some p p which is the lesser of a twin prime pairing, to satisfy the conditions of the question we also require that either 2 ( p + 2 ) = 3 p 1 2(p + 2) = 3p - 1 or 2 ( p + 2 ) = 3 p + 1. 2(p + 2) = 3p + 1.

In the first case we end up with p = 5 p = 5 , which yields n = 14 , n + 1 = 15 n = 14, n + 1 = 15 , both of which do have 4 divisors with these divisors adding to the same value, namely 24. 24.

In the second case we end up with p = 3 p = 3 , which would yield n = 9 , n + 1 = 10 n = 9, n + 1 = 10 . However, n = 9 n = 9 only has 3 divisors, so does not satisfy all the conditions.

So a b = c d + 1 ab = cd + 1 combined with 1 + a + b + a b = 1 + c + d + c d 1 + a + b + ab = 1 + c + d + cd does imply ( a + b ) ( c + d ) = 1 (a + b) - (c + d) = 1 , but the implication does not go in reverse, i.e., we can find a , b , c , d a,b,c,d such that ( a + b ) ( c + d ) = 1 (a + b) - (c + d) = 1 but not a b = c d + 1. ab = cd + 1. Thus the connection with twin primes does not hold.

(Note that there are integers with 4 divisors that only have one prime factor, namely all perfect cubes. Also note that it is only conjecture that there are an infinite number of twin prime pairings; the evidence is extremely strong that there are, but the proof remains elusive. This is the open problem I find most intriguing.)

I'm working on a problem similar to this where instead of consecutive integers n , n + 1 n, n + 1 , I am looking at pairings n , n + 2 n, n + 2 such that each has 4 divisors and the sums of these divisors are the same value. The only pairing I've found thus far is 33 , 35 33, 35 . My sense is that this is the only pairing, but proof methods similar to the one I used in this problem and also to the approach you took have not been conclusive. Twin primes seem to figure more strongly in this variation, so I'm finding it quite interesting to work on. Any thoughts you might have would be welcome. :)

Brian Charlesworth - 6 years, 3 months ago

Log in to reply

For your related problem, if p , 3 p + 13 2 , p + 4 , 3 p + 1 2 p, \frac{3p+13}2, p+4, \frac{3p+1}2 are all distinct primes, then n = p ( 3 p + 13 ) 2 n = \frac{p(3p+13)}2 should work. For instance n = 67 107 n = 67 \cdot 107 , n + 2 = 71 101 n+2 = 71 \cdot 101 . My computer says we can take p = 67 , 127 , 307 , 907 , p = 67, 127, 307, 907, \ldots (and probably infinitely many more, although proving it would probably be harder than proving the twin prime conjecture).

There should be more families as well.

Patrick Corn - 6 years, 3 months ago

Log in to reply

@Patrick Corn Excellent! Thanks for this analysis, Patrick. I guess my initial instinct was wrong. And yes, as these prime pairs are rarer than twin primes I suppose it probably would be more difficult to prove their infinitude, although I can imagine some graduate student somewhere is trying to do just that for their thesis. :)

Brian Charlesworth - 6 years, 3 months ago

i actually did case bashing with primes :o

Héctor Andrés Parra Vega - 4 years, 5 months ago
Arjen Vreugdenhil
Oct 24, 2015

If a number has four divisors, it is of the form n = p q n = pq with p q p\not=q prime or n = p 3 n = p^3 with p p prime. We can treat these cases together by writing n = p q σ ( n ) = ( p + 1 ) ( q + 1 ) p prime and q = p 2 or q prime . n = pq\ \ \ \ \ \sigma(n) = (p+1)(q+1)\ \ \ \ \ p\ \text{prime and}\ q = p^2\ \text{or}\ q\ \text{prime}. Now n + 1 n+1 must be of the same form. It is also clear that either n n or n + 1 n+1 is even, and therefore has 2 as a prime factor. We take both possibilities together by transforming ( n , n + 1 ) ( n 1 , n ) (n,n+1)\to(n-1,n) . n ± 1 = 3 r σ ( n ± 1 ) = ( 2 + 1 ) ( r + 1 ) r prime or r = 2 2 = 4. n\pm 1 = 3r\ \ \ \ \ \ \sigma(n\pm1) = (2+1)(r+1)\ \ \ \ \ \ r\ \text{prime or}\ r = 2^2 = 4. The sums of divisors are equal: ( p + 1 ) ( q + 1 ) = 3 ( r + 1 ) ; p q + p + q = 3 r + 2. (p+1)(q+1) = 3(r+1); \ \ \ \ \ \ \ \ pq + p + q = 3r + 2. Substitute r = 1 2 ( p q ± 1 ) r = \tfrac12(pq\pm1) : p q + p + q = 3 2 ( p q ± 1 ) + 2 ; 1 2 p q p q + 2 ± 3 2 = 0. pq + p + q = \tfrac32(pq\pm1) + 2;\ \ \ \ \ \ \ \tfrac12pq - p - q + 2 \pm\tfrac32 = 0. We factor 1 2 ( p 2 ) ( q 2 ) = 3 2 ; \tfrac12(p - 2)(q - 2) = \mp\tfrac32; Since p , q > 2 p, q > 2 , we choose the positive sign (corresponding to a minus sign in the original choice) and get ( p 2 ) ( q 2 ) = 3 ; p = 3 , q = 5 or vice versa . (p - 2)(q - 2) = 3; \ \ \ \ \ p = 3, q = 5\ \ \text{or vice versa}. Thus n = 3 5 = 15 ; 2 r = n 1 = 14 , r = 7. n = 3\cdot 5 = 15;\ \ 2r = n-1 = 14, r = 7. p , q , r p, q, r are prime and therefore satisfy our conditions. We check the divisors: 15 gives 1 + 3 + 5 + 15 = 24 , 1 + 3 + 5 + 15 = 24, and 14 gives 1 + 2 + 7 + 14 = 24. 1 + 2 + 7 + 14 = 24.

Conclusion: n = 14 n = 14 and there is only one such solution.

Sean Sullivan
Jul 19, 2015

The number of divisors for n = p 1 a 1 p 2 a 2 p 3 a 3 . . . n=p_{1}^{a_{1}}p_{2}^{a_{2}}p_{3}^{a_{3}}... with p m p_{m} prime, is given by ( a 1 + 1 ) ( a 2 + 1 ) ( a 3 + 1 ) . . . (a_{1}+1)(a_{2}+1)(a_{3}+1)... . Any number with 4 4 divisors, then, must have either a 1 = 3 , a m = 0 a_{1}=3,a_{m}=0 for all other m m or a 1 = 1 , a 2 = 1 , a m = 0 a_{1}=1, a_{2}=1, a_{m}=0 for all other m m . Meaning both n n and n + 1 n+1 are of the form p 3 p^{3} or p q pq for primes p p and q q . If we take n n or n + 1 n+1 to be p 3 p^{3} then the other is either p 3 + 1 p^{3}+1 or p 3 1 p^{3}-1 which factor to have a terms either p + 1 p+1 or p 1 p-1 along with another factor larger than 1 1 , for primes larger than 3 3 , p + 1 p+1 and p 1 p-1 are both composite, meaning p 3 + 1 p^{3}+1 or p 3 1 p^{3}-1 has more than 4 4 factors. For either n n or n + 1 n+1 to be p 3 p^{3} , p p must be 2 2 or 3 3 . Checking these case by case yields ( n , n + 1 ) = ( 7 , 8 ) ( 8 , 9 ) , ( 26 , 27 ) , ( 27 , 28 ) (n,n+1)=(7,8)(8,9),(26,27),(27,28) . The only solution among these that conforms to each having 4 4 factors is ( 26 , 27 ) (26,27) but the factors of these two don't sum to the same amount, hence both n n and n + 1 n+1 are of the form p q pq for primes p p and q q

Since one of the two numbers must be even let the even one be 2 r 2r for prime r r and the other be p q pq . Now we have p q ± 1 = 2 r pq\pm1=2r . The sum of the factors for the even and odd one are ( 2 + 1 ) ( r + 1 ) = 3 ( r + 1 ) (2+1)(r+1)=3(r+1) and ( p + 1 ) ( q + 1 ) = p q + p + q + 1 (p+1)(q+1)=pq+p+q+1 respectively and these must be equal.

Substituting p q ± 1 2 = r \frac{pq\pm1}{2}=r into 3 ( r + 1 ) = p q + p + q + 1 3(r+1)=pq+p+q+1 yields 3 ( p q ± 1 ) 2 + 3 = p q + p + q + 1 \frac{3(pq\pm1)}{2}+3=pq+p+q+1

3 ( p q ± 1 ) + 6 = 2 p q + 2 p + 2 q + 2 \rightarrow 3(pq\pm1)+6=2pq+2p+2q+2

p q 2 p 2 q ± 3 + 4 = 0 \rightarrow pq-2p-2q\pm3+4=0

( p 2 ) ( q 2 ) = 3 \rightarrow (p-2)(q-2)=\mp3

( p 2 ) ( q 2 ) (p-2)(q-2) must be positive, ruling out p q + 1 = 2 r pq+1=2r so it must be that n = 2 r n=2r and n + 1 = p q n+1=pq .

( p 2 ) ( q 2 ) = 3 (p-2)(q-2)=3 gives p = 3 , q = 5 p=3,q=5 and consequently n = 14 n=14 as the only valid solution. This means S S has only one element, 14 14 , so m = 1 , b = 14 m=1,b=14 and m + b = 15 m+b=\boxed{15}

14 is a number n with 4 divisors....... 1,2,7,14........=n therefore n+1=15.... it has also 4 divisors 1,3,5,15........... number of elements m in the set of numbers with four divisors=1 [s belongs to{14}]=m sum of all the elements in set S is 14=b therefore m+b=14+1=15............ Ans..... 14 is the only n that satisfies that n and n+1 both have only 4 divisors

Moderator note:

Your solution has been marked incomplete for not showing that b b has only one unique value.

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...