1
$\begingroup$

From link:

Find integers a, b and c such that:

987654321a + 123456789b + c = (a + b + c)³

$\endgroup$
3
  • $\begingroup$ The link you provided has solutions on it, together with code for a brute force search. Are you asking for a general algorithm to find integer points on cubic surfaces? $\endgroup$
    – S. Carnahan
    Oct 12, 2009 at 0:57
  • $\begingroup$ How are the limits in that program derived? $\endgroup$
    – Cade Roux
    Oct 12, 2009 at 2:36
  • $\begingroup$ As far as I can tell, 31427 was chosen because it is the smallest number whose square is larger than 987654321. This covers all cases where a,b, and c are nonnegative. I would not be surprised if there were additional solutions where a and b have opposite signs. $\endgroup$
    – S. Carnahan
    Oct 12, 2009 at 6:09

2 Answers 2

3
$\begingroup$

Note that x^3 - x = (x-1)x(x+1). Now let x = (a+b+c) and rewrite the equation as (x-1)x(x+1) = 987654320*a + 123456788*b.
Let D be gcd(987654320,123456788) = 16. There are integers A, B so that 987654320*A + 123456788*B = D,
e.g (1, -8). Pick your favorite x so that x^3 - x is a multiple of D, say kD, let a = kA and b = kB, and then set c to (x - (a+b)). If you need a and b to be positive, choose x large enough so that kD is big enough so that you can subtract multiples of 987654320*123456788/D^2 from, say ka and add them to kb. If you need c to be positive as well, then pick x not too large, as RHS < 10^9 * (a+b) < 10^9 x, so x larger than 10^5 will not get you positive values of c.

Gerhard "Ask Me About System Design" Paseman, 2010.01.12

$\endgroup$
1
$\begingroup$

Well, the numbers cannot be more then something like 10^5, so a simple program that cycles through all possible a and b and sees if there's a corresponding c might give you an answer pretty fast -- I dunno, from a minute to a day depending on your computer and programming language.

This also depends on whether you also implement some trivial checks, like try it modulo 2, 3 and 5 first.

$\endgroup$
3
  • $\begingroup$ Can you prove analytically that the answers have to be divisible by 10 (not including the trivial answers)? $\endgroup$
    – Cade Roux
    Oct 12, 2009 at 2:37
  • $\begingroup$ No, I can't. The answer I posted goes in a completely different direction, but of course it's quite stupid. If you know and are able to prove that these numbers indeed must be divisible by 10, then you're solving it in a smarter way, congrats! $\endgroup$ Oct 12, 2009 at 17:49
  • $\begingroup$ I believe it should be possible, and I think it has something to do with 123456789 + 987654321 = 1111111110. I've looked at transforming using c -> x - a - b and looking at the solutions of the standard cubic for x in terms of a and b. $\endgroup$
    – Cade Roux
    Oct 13, 2009 at 18:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.