Art
Computing
Contact info
CV
Electronics
Geek culture
Home brewing
Math
Music
Physics
Rants
Ψ/Φ
Style
Teaching
Theatre
WHAT'S UP
[2015-12-20] Project halted due to lack of results and interest (including mine).
Server status and client download
The Nagell-Ljunggren equation is a Diophantine equation of the form
1 + x + x2 + ... + xn-1 = yqor more compactly
(xn - 1)/(x - 1) = yqadmitting integer solutions x, y, q ≥ 2, n ≥ 3.
It has three known solutions (x, y, n, q):
(3, 11, 5, 2)The existence of other solutions remains an open question, thus making this an interesting target for computational search.
(7, 20, 4, 2)
(18, 7, 3, 3)
The problem space consists of points (x, n, q) fulfilling the aforementioned criteria. From each triplet we compute the corresponding y, and check if it is an integer. The latter is not quite as trivial as it seems here, since we are dealing with bignums and need to worry about rounding issues, but the basic idea is a rather brute-force search. Hence the problem ends up being more about work division and distribution than the bare math. To see that this method works, a test program is available.
[2014-12-28] A preliminary test based on Fermat's Little Theorem is now implemented, as suggested by R. Gerbicz. It has more than doubled overall speed, by weeding out candidates before going into bignums. Indeed, such tests with different moduli might be able to eliminate bignums altogether (cf. Hasse principle).
[2015-01-28] The pretest now uses up to 20 different prime moduli for a drastic speedup, eliminating bignums almost completely. As a consequence I had to increase the work unit size 400-fold :-j
Starting December 2014, I am looking for volunteers to run the client and join the quest for new solutions.
You can participate without any registration, just pick a username and download the client.
At the moment, this is only a personal project, and I promise nothing besides eternal gratitude. However, if a new solution is found, this is big news for the math community. In that case, you will be credited as a co-discoverer, whether or not you actually discovered it.
Regardless of any solutions found, this is basic research that may end up in publications/theses or otherwise attain fame and fortune :)
As of 2014-12-30, the software makes use of multiple CPUs. The network client manages multiple worker processes, one for each work unit.
For a technical background: Julia has very nice provisions for parallelism, but it remains faster overall to run one worker per CPU. Parallelism in Python is even harder; for example, Python threads all run within a single process on one CPU. On the other hand, Python threads are useful here for the subprocess management.
Naturally, you can run the client on any number of different machines.
For now, there is only a username to provide some minimal identification. Besides being lazy on the server side, this idea actually follows from classical projects, such as Distributed.net, where you need not register to contribute.
In case of a failed connection, the client will generate a random work unit. Results are saved into files for sending later.
In addition, the state of the client is periodically saved, so you will not lose much work in a crash or a planned downtime.
Work units live in a 2D plane with the coordinates (x, n). Currently, each work units is 40000 x 40000 points. For each x, the client works out the list of permissible q's, and the range of n's is likewise filtered.
The current aim is that work units take a couple of hours to complete. However, your shiny new CPU might be a little faster, while older CPUs may take closer to a day on the larger units.
Note that older CPUs are indeed welcome; my crunchers range from an Atom to a Core 2 Duo. IMHO, one key point of these distributed projects is to show that a group of dedicated amateurs can stand up to supercomputers :) If it's 64-bit, it's probably fast enough for this.
The worker features a checksum for possible later verification that a given range has been completed. It represents the cumulative distance to an exact integer solution, and it is one of the key reasons why I did away with user registration.
The checksum is also a handy development feature to ensure consistency across changes in programming, given the same math. Unfortunately, it is not consistent between the Python and Julia workers, presumably due to subtle differences in rounding in the bignum libraries. This is why the client reports the worker language with results. Nevertheless, the rounding issue should not affect the veracity of actual solutions, as is evident from the test programs.
Generally, a project like this needs all kinds of help besides running the client, for example