f ( x ) = 2 x + 2 0 1 7 3 x + 2 0 1 8
How many integers x are there such that f ( x ) is an integer?
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.
Plz explain the last line..how can u say that the number of integers is 16.
Log in to reply
I've edited my solution for further explanation, please let me know if I've any mistake, thanks!
Log in to reply
Ok..thanks..I've understood now.
You could use Euclid's algorithm to get x + 1 ∣ 2 0 1 5 , and then just do the same as what you did at the end.
Hello Jian. In my solution I use the expression (6x+4036)/(2x+2017). You didn't like it. That's OK, but Binky posted later a solution based on the same expression. You liked it a lot. Is that fair?
Log in to reply
Solutions are voted on by users - the author isn't the one who decides which solutions appear at the top. Also, if you look at the solutions to many of the problems on brilliant, you will see duplicate solutions - sometimes explained a little differently that resonates better, sometimes a few votes makes one solution appear at the top more than others. Please continue to provide solutions, because even if it isn't voted up, someone might not understand a higher solution and then see yours.
Log in to reply
I just overreacted! Sorry and thank you for the advice.
f(1)=3(1) + 2018/2(1)+2017=2021/2019 So , f(1) is not integer ....
Log in to reply
Note that he doesn't say x = 1 is a solution, but rather 2 x + 2 0 1 7 = 1 . Solve for x to find the x -values.
I could find only one integer solution: -1. There can't be any integer solution larger than that because f(x) would be strictly increasing. And f(1) and f(0) are not integers and f(x) cant be greater than 3/2. It cannot be a negative number less than -1 because then the numerator would be less than the denominator.
Log in to reply
Yes, I absolutely agree. I found the other 15 solutions that were proposed to only come close to an integer for f(x). All one has to do is to plug the other 15 solutions into the equation to find that they do not yield an exact integer.
You are correct, "There can't be any integer solution larger than that"... And indeed all other 15 values are smaller than -1. MUCH smaller, really, the next one is -807.
Have you actually tried substituting those values for 2 x + 2 0 1 7 ?
its important these factors are odd, since an even factor would not yield a solution
Log in to reply
since 2015 is an odd number, so it won't have even factors.
Does this means that "x" can take any of those 16 values and "f(x)" will be an integer number?
Log in to reply
2 x + 2 0 1 7 can take any of those 16 values, not x . You can figure out the corresponding values of x from that though.
Is subtracting 1007.5 arbitrary?
f ( x ) = 2 x + 2 0 1 7 3 x + 2 0 1 8 Multiply both sides by 2 , and rearrange the top of the fraction to match the divisor: 2 × f ( x ) = 2 x + 2 0 1 7 6 x + 4 0 3 6 = 2 x + 2 0 1 7 6 x + 6 0 5 1 − 2 0 1 5 = 2 x + 2 0 1 7 6 x + 6 0 5 1 − 2 x + 2 0 1 7 2 0 1 5 = 3 − 2 x + 2 0 1 7 2 0 1 5 Which can be rearranged to: 2 0 1 5 = ( 3 − 2 × f ( x ) ) × ( 2 x + 2 0 1 7 ) As f ( x ) and x are both integers, 3 − 2 × f ( x ) and 2 x + 2 0 1 7 must be cofactors of 2 0 1 5 , and also must be odd. Since all factors of 2 0 1 5 are odd, they are all viable solutions, and so the number of possible solutions is equal to the number of cofactor pairs of 2 0 1 5 , which is 1 6 .
Thanks for providing another beautiful solution!
Hi Binky Mh. My solution is based on the same expression (6x+4036)/(2x+2017), and it was posted earlier (on August 5). Do you think using the same idea is fair???
Log in to reply
Sorry, I didn't see your solution when I was checking if this solution had already been shown.
Log in to reply
I had a look at your solution, and although we have similar ideas on how to approach the problem, it looks like we went about finding the solution a little differently.
Hi Binky, I am trying to understand how the 2015 enters the solution process. Could you please elaborate? I would be most grateful. Thank you for your step by step solution process.
Log in to reply
We want to make the top a multiple of (2x+2017), and since 6x is triple 2x, we want the top to be 3*(2x+2017). This equals (6x+6051). In order to turn 4036 into 6051, we must then subtract 2015 so the equation stays true. Hope that helps.
I think you dropped a minus sign in your rearrangement, though I suspect it doesn't matter...
Hi Binky, can you please explain that why factors of 2015 are equal to the number of factors of f(x)?
Log in to reply
From the equation 2015 = (3 - 2 * f(x)) * (2x + 2017)...
Each pair of factors of 2015 have their respective unique values of f(x) and x. For example:
2015 = 13 * 155
(3 - 2 * f(x)) = 13
(2x + 2017) = 155
f(x) = -(13 - 3)/2
x = (155 - 2017)/2
If (2x + 2017) is not a factor of 2015, then (3 - 2 * f(x)) will have to be a non-integer to balance the equation out. This will result in f(x) also being a non-integer, which means it is not a valid solution. (This also applies in the opposite direction, if f(x) is not a factor).
This means the only cases in which both x and f(x) are integer solutions is when (3 - 2 * f(x)) and (2x + 2017) are cofactors of 2015.
I hope that helps!
Brute force solution using PHP to yield 16 factors:
Sadly this fails if x would have a solution with abs(x)>30000. Or can you prove that there are no such solutions?
Log in to reply
Such a proof would be quite trivial:
For solutions f ( x ) = 2 x + 2 0 1 7 3 x + 2 0 1 8 must be an integer. For x → ± ∞ it goes to 2 3 .
Solving for f ( x ) = 1 gives x = − 1 . For all x ≥ 0 , 1 < f ( x ) < 1 . 5 , i.e. not an integer.
Solving for f ( x ) = 2 gives x = − 2 0 1 6 . For all x ≤ − 2 0 1 7 , 1 . 5 < f ( x ) < 2 , i.e. not an integer.
In conclusion, if ∣ x ∣ > 2 0 1 6 there will be no solutions, and the list found with this brute force approach is complete.
Best solution ever, attempted almost the same way and succeed ;)
Log in to reply
I did it with pen and paper and an ordinary calculator, by finding the values of x corresponding to small values of f(x) and then testing the remaining values of x around -1000. The 16 solutions have a neat separation with respect to each other. Both the steps in f(x) and in x are values in this list: {1,2,4,9,17,45,124,806,-2015}, and this list occurs once left-to-right and once right-to-left (not repeating the end elements).
Exactly my results (done in bc )
I think it is cheating
When replacing x=1 in the formula we obtain f(x)=2021 / 2019, which is not an integer. Probably we need to revisit this answer.
python solution :
count=0
for x in range(-100000,0):
if (((3*x)+2018)%((2*x)+2017)) == 0 :
count+=1
print(count)
Lol! You still need to prove no solution is possible beyond your search window... which is easy with differential calculus as f asymptotically approximates to 3/2 on both sides.
Rewrite f ( x ) = 2 x + 2 0 1 7 3 x + 2 0 1 8 = 2 x + 2 0 1 7 x + 1 + 1 , for this to be an integer, 2 x + 2 0 1 7 x + 1 has to be an integer.
Let 2 x + 2 0 1 7 x + 1 = k where k is an integer, we have, by Simon's Favorite Factoring Trick :
x + 1 = 2 x k + 2 0 1 7 k 2 x k − x + 2 0 1 7 k − 1 = 0 4 x k − 2 x + 4 0 3 4 k − 2 = 0 ( 2 x + 2 0 1 7 ) ( 2 k − 1 ) = − 2 0 1 5
Now since 2 0 1 5 = 5 × 1 3 × 3 1 , it has 2 × 2 × 2 = 8 factors, that means if we include the negatives, − 2 0 1 5 will have 1 6 factors. Every factor is odd, which matches the parity of the terms ( 2 x + 2 0 1 7 ) and ( 2 k − 1 ) , which are both also odd. Therefore the number of integers x such that f ( x ) is an integer equals to the number of factorizations of − 2 0 1 5 , which is 1 6 .
If 2 n + 2 0 1 7 divides 3 n + 2 0 1 8 , then it divides also 3 ⋅ ( 2 0 1 7 + 2 n ) − 2 ⋅ ( 3 n + 2 0 1 8 ) ) which is 2 0 1 5 . The expression 2 0 1 7 + 2 n ranges over the odd integers (try plugging in n = − 1 , n = − 2 , . . . and you will obtain 2 0 1 5 , 2 0 1 3 , . . . .
Since 2 0 1 5 = 5 ⋅ 1 3 ⋅ 3 1 , it has a total number of 2 ⋅ 2 ⋅ 2 = 8 odd positive divisors. Now you can choose the sign of each positive divisor (if 6 5 divides 2 0 1 5 so does − 6 5 ) leading to 2 ⋅ 8 = 1 6 possibilities, which can all be realized varying n .
If the last part is unclear, try constructing a divisor of 2 0 1 5 from its prime factors: you can choose if you want to include 5 or not (two options) and the same goes for other factors (when you choose none, you obtain 5 0 ⋅ 1 3 0 ⋅ 3 1 0 = 1 .
Generalizing this reasoning, a number whose prime factorization is p 1 a 1 ⋅ p 2 a 2 ⋅ ⋯ ⋅ p m a m has ( a 1 + 1 ) ⋅ ⋯ ⋅ ( a m + 1 ) positive divisors.
2015 = 5 * 13 * 31 without 403 but with the negative ones
Log in to reply
Thanks for pointing it out, now the solution should be correct
We need to have 2 0 1 7 + 2 n 2 0 1 8 + 3 n = k for some integer k . Multiply out the denominator:
2 0 1 8 + 3 n = 2 0 1 7 k + 2 n k ,
and group all the terms together on one side and set the other side equal to zero:
2 0 1 7 k + 2 n k − 3 n − 2 0 1 8 = 0 .
Dividing everything by 2 gives:
n k − 2 3 n + 2 2 0 1 7 k − 1 0 0 9 = 0 .
This almost looks like the setup for Simon's Favorite Factoring Trick . In this case we would have j = 2 2 0 1 7 , i = − 2 3 , but the problem is − 1 0 0 9 = i j = − 4 6 0 5 1 . To get this expression into the desired form, add − 4 6 0 5 1 to both sides and apply the factoring trick:
( k − 2 3 ) ( n + 2 2 0 1 7 ) − 1 0 0 9 = − 4 6 0 5 1 ,
( k − 2 3 ) ( n + 2 2 0 1 7 ) = 1 0 0 9 − 4 6 0 5 1 = − 4 2 0 1 5 ,
and multiplying both sides by 4 :
( 2 k − 3 ) ( 2 n + 2 0 1 7 ) = − 2 0 1 5 .
Because 2 0 1 5 = ( 5 1 ) ( 1 3 1 ) ( 3 1 1 ) it has ( 1 + 1 ) ∗ ( 1 + 1 ) ∗ ( 1 + 1 ) = 8 factors, so − 2 0 1 5 has 1 6 factors among the negative and positive integers. The expressions 2 k − 3 and 2 n + 2 0 1 7 must both correspond to a factor of − 2 0 1 5 , since both are integers. Thus there are 1 6 possible integral values for 2 n + 2 0 1 7 . n must take the form 2 − 2 0 1 7 ± m , where m is one of the 8 factors of 2 0 1 5 . So there are 1 6 corresponding possible values for n (they are: − 2 0 1 6 , − 1 , − 1 2 1 0 , − 8 0 7 , − 1 0 8 6 , − 9 3 1 , − 1 0 4 1 , − 9 7 6 , − 1 0 2 4 , − 9 9 3 , − 1 0 1 5 , − 1 0 0 2 , − 1 0 1 1 , − 1 0 0 6 , − 1 0 0 9 , − 1 0 0 8 ). So the answer is 1 6 .
Just use script "Diophantine y=(3x+2018)/(2x+2017) on integers" in WolframAlpha, and you get list of 16 pairs (x,y) of integers, Answer=16.
One line in Mathematica:
Reduce[3x+2018==n(2x+2017),{x,n},Integers]
Yeilds all 16 solutions
I first changed f ( x ′ ) = 2 x ′ + 2 0 1 7 3 x ′ + 2 0 1 8 into the equivalent fraction g ( x ) = 2 0 1 5 + 2 x 2 0 1 5 + 3 x where x' = x - 1 This just made the equation look simpler without changing the mathematics
Then I looked at 2 0 1 5 + 3 x ≡ 0 m o d ( 2 0 1 5 + 2 x ) considering that A + B ≡ 0 m o d ( 2 0 1 5 + 2 x ) we can look at the remainder from 2015 and 3x separately.
This allows for an interesting change of perspective 2015 mod(2015 + 2x) can be written as -2x mod(2015 + 2x) , because as 2015+2x increases 2015 stays constant and the remainder is simply -2x.
Rewriting 2 0 1 5 + 3 x ≡ 0 m o d ( 2 0 1 5 + 2 x ) gives − 2 x + 3 x ≡ 0 m o d ( 2 0 1 5 + 2 x ) or x ≡ 0 m o d ( 2 0 1 5 + 2 x ) This brings us to an interesting result as 2015 + 2x increases by 2, x is only increasing by one, and therefore the congruence does not hold for positive x values. Essentially as x approaches infinity we get a horizontal Asymptote at 3/2.
So we can think about negative x values. As x gets more negative in g(x) the numerator decreases faster to 0 than the denominator. Then when x = -806, the numerator is -403 and the denominator is 403. As x gets more and more negative we can reason that the denominator will get closer to 0, resulting in multiple integer solutions. After it passes 0, both the numerator and denominator will be negative, and just like the positive x solutions there will be a point where the numerator is moving faster than the denominator but not fast enough to illicit integer multiples of it.
From here I ran a small bit of java code to calculate the numbers
public static void congruence() {
ArrayList<Integer> solutions = new ArrayList<>();
int x = 0;
while(2015-2
x >-10000) {
for(int i =-10000;i<10000;i++){
if((2015-2
x)*i==x){
solutions.add(x);
}
}
x++;
}
System.out.print(solutions + "\n" + solutions.size() + "\n");
newbe(solutions);
}
public static void newbe(ArrayList<Integer> solutions) { for(Integer e:solutions){ int numerator = 3 (-e-1)+2018; int denominator = 2 (-e-1) + 2017; System.out.println(numerator + " " + denominator); } } }
The last x value I got was -2015 making g ( x ) = − 2 0 1 5 − 4 0 3 0 = 1 2 since g(x) is approaching a horizontal Asymptote of 3/2, there will not be a 1/1 fraction, and the 16 values the code generated are the only 16.
Another brute-force solution, using SAS this time (using more extreme values of x does not change the number of solutions):
data a; do x=-10000 to 10000; y= (3 x+2018) / (2 x+2017); if y-int(y)=0 then output; end; run;
proc contents data=a; run;
Let N be the result of (3x+2018)/(2x+2017).
Solving for x gives:
x=(2018-2017N)/(2N-3)
This converges to -1008.5 as N increases as -2017N/2N dominates.
Brute force inspection of positive and negative intergers for N as x approaches -1008.5 from above and below gives the result. Once we get x > -1009 and < -1008 from below and above we can stop. Not very sophisticated, but it gets there.
Problem Loading...
Note Loading...
Set Loading...
f ( x ) = 2 x + 2 0 1 7 3 x + 2 0 1 8 = 2 x + 2 0 1 7 3 x + 3 0 2 5 . 5 − 2 x + 2 0 1 7 1 0 0 7 . 5 = 2 3 ( x + 1 0 0 8 . 5 x + 1 0 0 8 . 5 ) − 2 1 ( 2 x + 2 0 1 7 2 0 1 5 ) = 2 3 − 2 1 ( 2 x + 2 0 1 7 2 0 1 5 )
f ( x ) is an integer ⟹ 2 x + 2 0 1 7 2 0 1 5 is an odd number ⟹ 2 x + 2 0 1 7 must be the factor of 2015.
2 0 1 5 = 5 1 × 1 3 1 × 3 1 1
From the above, we found that the factors of 2015 are ± 1 , ± 5 , ± 1 3 , ± 3 1 , ± 6 5 , ± 1 5 5 , ± 4 0 3 , ± 2 0 1 5 , total 1 6 factors.
Recall: 2 x + 2 0 1 7 must be the factor or 2015.
Hence, the number of integers x equal to the number of the factors of 2015 which is 1 6 . [Quick Solution —— Prime Number Decomposition Theorem]
Hence, the number of integers x = 2 × ( 1 + 1 ) × ( 1 + 1 ) × ( 1 + 1 ) = 1 6 .
Wiki: https://www.cut-the-knot.org/blue/NumberOfFactors.shtml