2 0 1 7 is a prime number, so the sum of all its positive divisors is 1 + 2 0 1 7 = 2 0 1 8 .
Is there another positive integer such that the sum of all its positive divisors is also 2 0 1 8 ?
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.
Yay! Super neat solution! So is the following generalization true?
(Using the same notations) If d ( n ) = p + 1 , then n = p only.
Log in to reply
Thanks! In general, no - the key point is that d(a)=2 has no solutions, and the only factorisations of 2018 are 1 * 2018 and 2 * 1009. The simplest counterexample is when p=11: d(11)=d(6)=12. The solution n=6 works here because of the factorisation 12=3*4, and we have d(2)=3, d(3)=4. However, there are other values of k such that d(a)=k has no solutions (k=5 or k=9, for example; or see this list: https://oeis.org/A007369 ). The generalisation is interesting - if all factorisations of p+1 into coprime factors include at least one member of the list of k values with no solutions to d(a)=k, then n=p is the only solution. There must be a neater way of expressing this! Also, the condition for uniqueness of the solution is not actually related to primes - d(n)=7 only has the solution n=4.
Log in to reply
Aha - OEIS also has a list of k such that d(n)=k has a unique solution: https://oeis.org/A007370 (though no formula or rule for generating it beyond its definition)
Log in to reply
@Chris Lewis – Yup. My first instinct to "my generalization question" was yes, but luckily I managed to find a small counterexample, d(6)=12.
Edited to include the case of prime powers
Simple brute force solution using Python 3 .
1 2 |
|
output : 2017
Since the only output is 2017 the correct answer is N o
This works too!
I'm still learning Python, so my brute force attempt (which did eventually succeed after much debugging) required eight lines of code instead of your two. I clearly still have much to learn.
Log in to reply
In fact, it could be made in only one line but it is better to have a readable code with few more line than a incomprehensible things. Good luck if you want to learn programming, you will see how helpful and interesting it is :)
cheater!!!
Log in to reply
Proof by exhausting all possibilities is valid. It works well in finite cases.
While I created this problem without the intention of it to be solved using programming, that doesn't mean that it's completely forbidden to do so.
My answer too +1. But you don't need list compression for the
sum
parameter, a straight up genexp (with no extra braces) works too.
The prime factorization of positive number N can be expressed as N = k = 1 ∏ n p k e k = p 1 e 1 ⋅ p 2 e 2 ⋯ p n − 1 e n − 1 ⋅ p n e n where e 1 , e 2 , ⋯ e n are integer (powers) and here we want to find the sum of all positive divisors such that it is equal to 2018 , ie ; k = 1 ∏ n ( h = 0 ∑ e k p k h ) = k = 1 ∏ n ( p k − 1 p e k + 1 − 1 ) = 1 × 2 0 1 8 = 2 × 1 0 0 9 Since 2 , 1 0 0 9 are primes with power 1 each which implies that product cannot proceed more than once or twice ie n ≤ 2 . Here we can write it as either ( p 1 − 1 p e 1 + 1 − 1 ) or ( p 1 − 1 p e 1 + 1 − 1 ) ( p 2 − 1 p e 2 + 1 − 1 ) = 2 0 1 8 ( ∗ ) = 2 × 1 0 0 9 ( ∗ ∗ ) For the first case ( ∗ ) we can observe that p e 1 + 1 − 2 0 1 8 p p ( 2 0 1 8 − p e 1 ) = − 2 0 1 7 = 2 0 1 7 ⟹ p = 2 0 1 7 , e 1 = 1 For the second case ( ∗ ∗ ) ⎩ ⎪ ⎪ ⎨ ⎪ ⎪ ⎧ p 1 − 1 p 1 e 1 + 1 − 1 = 2 ⟹ p 1 ( 2 − p e 1 ) = 1 ⟹ no solutions p 2 − 1 p 2 e 2 + 1 − 1 = 1 0 0 9 ⟹ p 2 ( 1 0 0 9 − p 2 e 2 ) = 1 0 0 8 = 2 4 ⋅ 3 2 ⋅ 7 Solving we obtain p 2 = 7 and 1 0 0 9 − 7 e 2 = 1 4 4 or 7 e 2 = 8 6 5 ⟹ e 2 = 7 lo g ( 8 6 5 ) ∈ N .
Hence, only the solution that exist , N = 2 0 1 7 . Therefore, the answer is No .
Almost perfect!
Careful, it should be k = 1 ∏ n ( h = 0 ∑ n p k − 1 p k e h + 1 − 1 ) = ⋯ .
Plus, for your second case, since you already know that there's no solution for p 1 , there isn't a need to solve for p 2 because it's already impossible for the second case to have a valid solution.
Log in to reply
Your first "correction" is not formulated correctly. I agree with your second point.
This solution looks very interesting. I'm trying to understand it, but I can't get the purpose of the second equation. Could you please explain it to me?
For a number n with prime decomposition n = ∏ k p k a k , the sum of its divisors is ∏ k ( 1 + p k + . . . + p k a k ) .
Our wanted divisor sum 2018 has prime decomposition 2×1009. Since the factor 2 cannot be expressed as 1 + p + . . . + p a , we are looking for single prime p such that 2 0 1 8 = 1 + p + . . . + p a = p − 1 p a + 1 − 1 , and hence 1 + 2 0 1 8 ( p − 1 ) = p a + 1 ⇒ 2 0 1 8 − p 2 0 1 7 = p a So we need p to be a prime divisor of 2 0 1 7 , which is a prime number itself. Trying p = 2 0 1 7 we find 2 0 1 8 = 1 + p , which was given in the problem.We just showed it to be the only solution.
Problem Loading...
Note Loading...
Set Loading...
Let's say there's another solution, n = 2 0 1 7 , so that d ( n ) = 2 0 1 8 , where d ( n ) is the sum of the divisors of n . We can immediately observe that n must be composite, as d ( p ) = p + 1 for any prime p .
We can also eliminate the possibility that n is a power of a prime. The factors of any power of a prime are just the smaller powers of that prime (including p 0 = 1 ), so d ( p k ) = p k + p k − 1 + ⋯ + 1 . From this, d ( p k ) − 1 is a multiple of p . But in this case, d ( n ) − 1 = 2 0 1 7 , which is itself a prime. In other words, n must have more than one prime factor.
A key property of the function d is that it is multiplicative - ie, for any two coprime integers a and b we have d ( a b ) = d ( a ) d ( b ) .
The prime factorisation of 2 0 1 8 is 2 ⋅ 1 0 0 9 .
Any number with more than one prime factor can be written in at least one way in the form n = a b , with a and b coprime and b > a > 1 .
Putting all this together, we must have d ( a ) = 2 and d ( b ) = 1 0 0 9 . But d ( a ) = 2 clearly has no solutions; contradiction. And so there are no such n .