Union of Sum and Divisors

2017 2017 is a prime number, so the sum of all its positive divisors is 1 + 2017 = 2018. 1+2017= 2018.

Is there another positive integer such that the sum of all its positive divisors is also 2018 ? 2018?

Yes No

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

Chris Lewis
Nov 12, 2018

Let's say there's another solution, n 2017 n\neq2017 , so that d ( n ) = 2018 d(n)=2018 , where d ( n ) d(n) is the sum of the divisors of n n . We can immediately observe that n n must be composite, as d ( p ) = p + 1 d(p)=p+1 for any prime p p .

We can also eliminate the possibility that n 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 p^0=1 ), so d ( p k ) = p k + p k 1 + + 1 d(p^k) = p^k+p^{k-1}+\cdots +1 . From this, d ( p k ) 1 d(p^k)-1 is a multiple of p p . But in this case, d ( n ) 1 = 2017 d(n)-1=2017 , which is itself a prime. In other words, n n must have more than one prime factor.

A key property of the function d d is that it is multiplicative - ie, for any two coprime integers a a and b b we have d ( a b ) = d ( a ) d ( b ) d(ab)=d(a)d(b) .

The prime factorisation of 2018 2018 is 2 1009 2\cdot1009 .

Any number with more than one prime factor can be written in at least one way in the form n = a b n=ab , with a a and b b coprime and b > a > 1 b>a>1 .

Putting all this together, we must have d ( a ) = 2 d(a)=2 and d ( b ) = 1009 d(b)=1009 . But d ( a ) = 2 d(a)=2 clearly has no solutions; contradiction. And so there are no such n n .

Yay! Super neat solution! So is the following generalization true?

(Using the same notations) If d ( n ) = p + 1 d(n) = p + 1 , then n = p n=p only.

Pi Han Goh - 2 years, 7 months ago

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.

Chris Lewis - 2 years, 7 months ago

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)

Chris Lewis - 2 years, 7 months ago

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.

Pi Han Goh - 2 years, 7 months ago

Edited to include the case of prime powers

Chris Lewis - 2 years, 7 months ago

Log in to reply

Yay! <3 \quad

Pi Han Goh - 2 years, 7 months ago
Antoine Crbs
Nov 12, 2018

Simple brute force solution using Python 3 .

1
2
for a in range(1, 2018):
    if sum([d for d in range(1, a+1) if a%d==0]) == 2018: print(a)

output : 2017

Since the only output is 2017 the correct answer is N o \boxed{No}

This works too!

Pi Han Goh - 2 years, 7 months ago

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.

Paul Cockburn - 2 years, 6 months ago

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 :)

Antoine Crbs - 2 years, 6 months ago

cheater!!!

יונתן לוי - 2 years, 6 months ago

Log in to reply

Proof by exhausting all possibilities is valid. It works well in finite cases.

Jerry Barrington - 2 years, 6 months ago

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.

Pi Han Goh - 2 years, 6 months ago

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.

Paul Evans - 2 years, 6 months ago
Naren Bhandari
Nov 4, 2018

The prime factorization of positive number N 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 N =\prod_{k=1}^{n} p_k^{e_k}= p_1^{e_1}\cdot p_2^{e_2}\cdots p_{n-1}^{e_{n-1}}\cdot p_n^{e_n} where e 1 , e 2 , e n e_1,e_2,\cdots 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 e k + 1 1 p k 1 ) = 1 × 2018 = 2 × 1009 \prod_{k=1}^{n} \left(\sum_{h=0}^{e_k}p^h_k\right) =\prod_{k=1}^{n}\left(\dfrac{p^{e_k+1}-1}{p_k-1}\right) =1\times 2018=2\times 1009 Since 2 , 1009 2, 1009 are primes with power 1 each which implies that product cannot proceed more than once or twice ie n 2 n\leq 2 . Here we can write it as either ( p e 1 + 1 1 p 1 1 ) = 2018 ( ) or ( p e 1 + 1 1 p 1 1 ) ( p e 2 + 1 1 p 2 1 ) = 2 × 1009 ( ) \begin{aligned} \left(\dfrac{p^{e_1+1}-1}{p_1-1}\right) & = 2018(*) \\ \text{or} \left(\dfrac{p^{e_1+1}-1}{p_1-1} \right)\left(\dfrac{p^{e_2+1}-1}{p_2-1}\right)&=2\times 1009(**)\end{aligned} For the first case ( ) (*) we can observe that p e 1 + 1 2018 p = 2017 p ( 2018 p e 1 ) = 2017 p = 2017 , e 1 = 1 \begin{aligned} p^{e_1+1} -2018p & =-2017 \\ p(2018-p^{e_1})& =2017\implies p=2017 \ ,e_1=1 \end{aligned} For the second case ( ) (**) { p 1 e 1 + 1 1 p 1 1 = 2 p 1 ( 2 p e 1 ) = 1 no solutions p 2 e 2 + 1 1 p 2 1 = 1009 p 2 ( 1009 p 2 e 2 ) = 1008 = 2 4 3 2 7 \begin{cases} \dfrac{p_1^{e_1+1}-1}{p_1-1}=2\implies p_1(2-p^{e_1})=1\implies \text{no solutions}\\\dfrac{p_2^{e_2+1}-1}{p_2-1}=1009\implies p_2(1009-p_2^{e_2})=1008=2^4\cdot3^2 \cdot 7 \end{cases} Solving we obtain p 2 = 7 p_2=7 and 1009 7 e 2 = 144 1009-7^{e_2}= 144 or 7 e 2 = 865 e 2 = log ( 865 ) 7 ∉ N 7^{e_2}=865\implies e_2 = \dfrac{\log (865)}{7}\not\in\mathbb N .

Hence, only the solution that exist , N = 2017 N=2017 . Therefore, the answer is No .

Almost perfect!

Careful, it should be k = 1 n ( h = 0 n p k e h + 1 1 p k 1 ) = \displaystyle \prod_{k=1}^n \left( \sum_{{\color{#D61F06}{h=0}}}^n \dfrac{p_k^{e_h+1} - 1}{p_k - 1} \right) = \cdots .

Plus, for your second case, since you already know that there's no solution for p 1 p_1 , there isn't a need to solve for p 2 p_2 because it's already impossible for the second case to have a valid solution.

Pi Han Goh - 2 years, 7 months ago

Log in to reply

Your first "correction" is not formulated correctly. I agree with your second point.

Tom Verhoeff - 2 years, 6 months ago

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?

Roger Garrido Vilallave - 2 years, 6 months ago

Log in to reply

See sum of factors .

Pi Han Goh - 2 years, 6 months ago
K T
Nov 12, 2018

For a number n with prime decomposition n = k p k a k n=\prod_k{p_k^{a_k}} , the sum of its divisors is k ( 1 + p k + . . . + p k a k ) \prod_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 1+p+...+p^{a} , we are looking for single prime p p such that 2018 = 1 + p + . . . + p a = p a + 1 1 p 1 2018=1+p+...+p^a= \frac{p^{a+1}-1}{p-1} , and hence 1 + 2018 ( p 1 ) = p a + 1 1+2018(p-1) = p^{a+1} 2018 2017 p = p a \Rightarrow 2018-\frac{2017}{p} = p^{a} So we need p p to be a prime divisor of 2017 2017 , which is a prime number itself. Trying p = 2017 p=2017 we find 2018 = 1 + p 2018=1+p , which was given in the problem.We just showed it to be the only solution.

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...