From: rusin@vesuvius.math.niu.edu (Dave Rusin) Newsgroups: sci.math.num-analysis,sci.math Subject: Re: Integer roots Date: 28 Feb 1998 09:52:27 GMT Juan Martin wrote: >I want know if in the equation : > >(2i+a)^n-2(i+a)^n-a^n=0 > >a and 2i can be both integers positives. Perhaps no one has answered this here because this is a question in number theory, not numerical analysis. Newsgroups like sci.math would be better. (Follow-ups set.) I suspect the answer to your question is that there are no such positive integers a,i for any integer n. I can recast the question, into a form which probably admits an answer; but I didn't complete the investigation. Setting x = i/a in your equation shows you are simply looking for a positive rational solution x to the equation (2x+1)^n - 2 (x+1)^n - 1 = 0 Note that all coefficients are even integers, so we divide by two. Then by the rational root test, any such x has numerator +-1 and denominator dividing N = 2^(n-1) - 1. This is easy enough to test for any n: try all divisors d of N and see if any has a reciprocal which is a root x. We can be more efficient: let f(x) = (2x+1)^n - 2 (x+1)^n - 1 so we seek positive zeros of f. Now, f'(x) = 2n(2x+1)^(n-1) - 2n(x+1)^(n-1) is never zero except when x=0, and is positive if x=1, so f is increasing on (0, oo). Clearly f is negative when x=0 and approaches +oo when x does, so f has precisely one positive real root r. We can estimate r: letting x = y/n we see we are asking for solutions to (2y/n+1)^n - 2 (y/n+1)^n - 1 = 0; for large n these terms are roughly exp(2y) and exp(y), respectively, so we have to solve a quadratic in exp(y), and so see y must be around ln(1+sqrt(2)); that is, the root r is approximately ln(1+sqrt(2)) / n That isn't really a fair analysis, but the conclusion is valid; indeed, an asymptotic formula for the root r can be obtained: r = ln(1+sqrt(2)) / n + (4+sqrt(2))ln(1+sqrt(2))^2 / 4n^2 + O(1/n^3) Thus the number d = 1/r which must be an integral divisor of N=2^(n-1) - 1 is approximately n/ln(1+sqrt(2)); more precisely, it's d = a n + b + c/n + O(1/n^2) where a = 1/ln(1+sqrt(2)) = 1.13459 b = -(1 + sqrt(2)/4) = -1.35355 c = (1/a)*(20 - 3sqrt(2)/a)/96 = 0.14929 Of course, the original question only has an affirmative answer if this number d is an _integer_, which must then be the nearest integer to R = a n + b (for large n, e.g. n> 2 !) and in fact must be a little greater than R. So it's now trivial to check for the rationality of roots of f: 1. Compute R above 2. If ceiling(R)-R isn't just over 0, then f has no rational roots. 3. Otherwise, compute d=round(R); this divides N iff f has rational roots. I carried out the computations for n up to about 100000. Interestingly, I never got to step 3; that is, R was never close enough to an integer. We are only interested in cases in which d is an integer, so that R is just c/n + O(1/n^2) shy of an integer, i.e., the quantity S=c/(ceiling(R)-R)/n will have to be about 1 (really 1 + O(1/n); with some effort I'm sure this could be transformed into a statement like "if d is an integer than S > 0.9, for n >> 0". ) Well, in some cases, R came fairly close to being an integer, but S was never very close to 1. I found examples (n,S)=(62, 0.27), (545, 0.49), and (28444, 0.36), but a search up to n=100000 found no other S>0.2, and only a handful of cases which could even muster S>0.1 (namely n=114, 597, 1392, 2239, 29291, 80059). To prove that we never have S > 1/2, it would suffice to show that there are no pairs of integers (n,m) for which | a n + b + m | < 2c/n. (A few known small cases can be excluded.) I don't remember enough of Transcendental Number Theory to know whether this is true, although I suppose a careful reading of Baker's book would help. Of course it's quite possible I've overlooked some simple divisibility condition, for example, which would preclude having f(1/d)=0 for some integral divisor d of N=2^(n-1)-1. dave