Search for Equal Sums of Like Powers

Update: Version 1.3.2 of SumsBKZ, which includes a number of new options, has been released. It can be downloaded via the links below. The old versions can be found here.

n^k = a₁* 1^k + a₂* 2^k + a₃* 3^k + ... + a_n-1* (n-1)^k

I suggested rewriting this as

0 = a₁* 1^k + a₂* 2^k + a₃* 3^k + ... + a_n-1* (n-1)^k + a_n* n^k

and solving this using one of many Integer Relations algorithms. Joe Crump ran with this idea, and, using the LLL algorithm, quickly broke all records for k > 12! I have since broken most of his records.  I originally used PARI-GP to search for solutions. The PARI-GP 2.0.20 code I slapped together is rough, but feel free to use and modify it as you wish.  However, more recently, I've had more success using the BKZ algorithm in NTL.

Joe Crump's page gives a good introduction to using lattice reduction to search for solutions.  My NTL code uses that search method with a randomly ordered basis.  The advantage over PARI is NTL is much more efficient, both in time and size of vectors returned!

If you are interested in trying this program yourself, you can either compile the source with the NTL library, or download precompiled Windows or Linux x86 binaries.  Either way, be sure to check out the readme.

An excellent program for Windows for verifying solutions is CHECK. It will verify all solutions are correct and output the best solutions found sorted by power and left terms.

Updated December 29, 2000

Counter added 10/20/2000