3
\$\begingroup\$

Inspired by this question, I was curios, if I could solve it for large n. For n=6209, its fifth power overflows long and I decided to stop below such numbers. The current algorithm reimplements the one from the linked question (the description, not the code) and could use some optimizations (but I'm not asking specifically about them as I'm having an idea already). For n=1000, the computation takes half an hour and the complexity is cubic, so there's no reason to look any further before optimizations.

Feel free to ignore slightly deviating coding conventions. My goal was to quickly create a solver and to keep the code short and the effort small. The next time I'll do the optimizations.

My biggest concern is understandability. I wrote nearly as much Javadoc as code and it took me longer, but I'm unsatisfied with the result (although I only care about clarity for people having read the linked question).

import static com.google.common.base.Preconditions.checkArgument;
import static com.google.common.base.Verify.verify;

import java.util.Collection;
import java.util.Map;
import java.util.Set;

import lombok.Getter;
import lombok.RequiredArgsConstructor;
import lombok.ToString;

import com.google.common.collect.ComparisonChain;
import com.google.common.collect.HashMultimap;
import com.google.common.collect.Multimap;
import com.google.common.collect.Sets;

public class Diophantinus1 {
    @RequiredArgsConstructor @Getter @ToString private static class Triple {
        private final int x, y, z;
    }

    @RequiredArgsConstructor @Getter @ToString static class Solution implements Comparable<Solution> {
        boolean isValid() {
            return pow5(a) + pow5(b) + pow5(c) + pow5(d) + pow5(e) == pow5(f);
        }

        @Override public int compareTo(Solution o) {
            return ComparisonChain
                    .start()
                    .compare(a, o.a)
                    .compare(b, o.b)
                    .compare(c, o.c)
                    .compare(d, o.d)
                    .compare(e, o.e)
                    .compare(f, o.f)
                    .result();
        }

        private final int a, b, c, d, e, f;
    }

    /**
     * Find all integer solutions of {@code a**5 + b**5 + c**5 + d**5 + e**5 = f**5}
     * with {@code 1 <= a <= b <= c <= d <= e <= f <= n}.
     */
    static Set<Solution> findSolutions(int n) {
        // TODO Replace the magic constant by some computation.
        return findSolutions(n, 12);
    }

    /**
     * Find all integer solutions of {@code a**5 + b**5 + c**5 + d**5 + e**5 = f**5}
     * with {@code 1 <= a <= b <= c <= d <= e <= f <= n}.
     *
     * <p>The algorithm goes as described in https://codereview.stackexchange.com/q/18720/14363
     * For triples {@code a, b, c} it evaluates {@code value = a**5 + b**5 + c**5} and
     * for triples {@code d, e, f} it evaluates {@code value = f**5 - d**5 - e**5}.
     *
     * <p>The algorithm gathers and matches the values.
     * Because of huge memory requirements, the solution set is partitioned into {@code 2**maskBits} subsets.
     * In the n-th step, only values congruent to n modulo 2**maskBits are considered.
     */
    private static Set<Solution> findSolutions(int n, int maskBits) {
        checkArgument(1 <= maskBits && maskBits <= 30);
        final Set<Solution> result = Sets.newTreeSet();
        for (int maskValue=0; maskValue < (1<<maskBits); ++maskValue) {
            final Multimap<Long, Triple> abcMultimap = computeSums(n, false, maskBits, maskValue);
            final Multimap<Long, Triple> defMultimap = computeSums(n, true, maskBits, maskValue);

            for (final Map.Entry<Long, Collection<Triple>> entry : abcMultimap.asMap().entrySet()) {
                final Long key = entry.getKey();
                final Collection<Triple> second = defMultimap.get(key);
                if (second.isEmpty()) continue;
                final Collection<Triple> first = entry.getValue();
                for (final Triple abc : first) {
                    for (final Triple def : second) {
                        if (abc.z() > def.x()) continue;
                        final boolean added =
                                result.add(new Solution(abc.x(), abc.y(), abc.z(), def.x(), def.y(), def.z()));
                        verify(added);
                    }
                }
            }
        }
        return result;
    }

    /**
     * For all {@code 1 <= x <= y <= z <= n} compute possible values of the expression
     * {@code value = (subtract ? -1 : 1) * (x**5 + y**5) + z**5}.
     *
     * <p>In order to conserve memory, discard values for which {@code (value & mask) != maskValue}
     * where {@code mask = (1 << maskBits) - 1} and also discard non-positive values.
     *
     * <p>If a value doesn't get discarded,
     * store it together with the {@code Triple(x, y, z)} in the result {@code Multimap}.
     *
     * <p>The algorithm is obviously inefficient as the vast majority of values gets discarded.
     */
    private static Multimap<Long, Triple> computeSums(int n, boolean subtract, int maskBits, int maskValue) {
        checkArgument(n < LIMIT, "n must be smaller than %s to prevent overflow, but was %s", LIMIT, n);
        checkArgument(1 <= maskBits && maskBits <= 30);
        final int mask = (1 << maskBits) - 1;
        checkArgument(0 <= maskValue && maskValue < mask);

        final Multimap<Long, Triple> result = HashMultimap.create();
        for (int x=1; x<n; ++x) {
            final long x5 = pow5(x);
            for (int y=x; y<n; ++y) {
                final long y5 = pow5(y);
                final int sign = subtract ? -1 : +1;
                final long sum = sign * (x5 + y5);
                for (int z=y; z<n; ++z) {
                    final long z5 = pow5(z);
                    final long value = sum + z5;
                    if ((value & mask) != maskValue) continue;
                    if (value <= 0) continue;
                    result.put(value, new Triple(x, y, z));
                }
            }
        }
        return result;
    }

    private static long pow5(int x) {
        assert x < LIMIT;
        final long x2 = (long) x * x;
        return x * x2 * x2;
    }

    private static final int LIMIT = (int) Math.floor(Math.pow(Long.MAX_VALUE, 1.0/5)) + 1;
}
\$\endgroup\$
1
\$\begingroup\$
  1. Your for loops are too nested - consider extracting them to separate private methods, something like:

    for (final Map.Entry<Long, Collection<Triple>> entry : abcMultimap.asMap().entrySet()) {
        analyzeEntry(entry);
    }
    
  2. Solution's constructor gets quite unreadable. I assume it is generated by Lombok, but still, new Solution(abc.x(), abc.y(), abc.z(), def.x(), def.y(), def.z()) is too long, and while quite clear, I guess you could add a more readable public Solution(Triple a, Triple b) constructor to improve readability.

  3. By convention, you should stick to using brackets for if's - it's what most coders would expect. That said, if (second.isEmpty()) continue; is not a huge abuser of that, but an abuser nonetheless.

  4. You've marked all your final variables as final - for me that's dead code, it only adds to the visual clutter.

  5. This code:

    private static long pow5(int x) {
        assert x < LIMIT;
        final long x2 = (long) x * x;
        return x * x2 * x2;
    }
    

    versus

    Math.pow(x, 5)
    
  6. This code:

    private static final int LIMIT = (int) Math.floor(Math.pow(Long.MAX_VALUE, 1.0/5)) + 1;
    

    versus

    private static final int LIMIT = 6209; // LIMIT^5 <= Long.MAX_VALUE
    
\$\endgroup\$
3
  • \$\begingroup\$ I actually mostly disagree: 3. I know and am actually using the opposite rule. 4. See this. 5. But I need a long and can't risk losing bits with double. 6. The expression is ugly but can be understood. Unlike 6209. You comment doesn't suffice. +++ However, thank you for the CR. \$\endgroup\$ – maaartinus May 15 '15 at 8:08
  • \$\begingroup\$ 3: Error-prone, but go ahead if you want to live dangerously. 4: Finals are fine, it's just that I personally don't like them, especially for local variables. 5: Valid point, but if you're interested in precision for large numbers, then you probably should consider using BigInteger and it's BigInteger.pow(int exp). 6: The expression is clear. It is, however, constant and I see no point in calculating it every time. As for the comment, it's just an example. \$\endgroup\$ – CptBartender May 15 '15 at 9:35
  • \$\begingroup\$ 3. I have had zero errors with using it for many years. I'm not careless and I never allow it to wrap into a second line or alike. Either a simple and clear one-liner or I go for braces. 5. I want speed so I stick with longs which are exact for inputs below 6209. I doubt that I'll ever be able to use inputs near my limit (as even 1000 takes very long). 6. OK, but given that any use of this class takes seconds or minutes, I don't want to optimize these few nanos. \$\endgroup\$ – maaartinus May 15 '15 at 11:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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