July 2018

[Dr Sardonicus]

Originally Posted by uau

I haven't watched the video, but from the textual description, the approach in it must be significantly worse than the Python script I posted above - the video description says 30 minutes and and 13 GB RAM, the script takes less than a minute with interpreted Python and less than 100 MB RAM.

The approach was to create an array of pairs (S, P) of sums S and products P of triples of numbers up to n -- so, a 3n by n^3 array. The guy did say that this was really bad as far as space was concerned. The (S, P) entry of the array was incremented if a triple (a, b, c) produced the sum S and product P. Obscurity could then be checked by seeing whether the entry (S,P) was greater than 1.

That was fine for n = 100, it took about a second IIRC. But when he changed n to 1200, the array size was too large, so he went to the "red black tree." That job used the 13GB and took the extra time.

My bugbear was how to check whether a given triple was "obscure." I did the dull, plodding thing of finding all triples a <= b <= c with a given product, and storing those with equal sums.

I did not think of any nice theoretical way to characterize "obscure triples." It appeared that the number of such triples with product up to X was somewhere around 0.4*X when X got somewhere into the tens of thousands, and stayed near there as X got up to 2 million.

[uau]

So he just wanted to find the entry for each pair of (sum, product)? A red-black tree is a bad choice of data structure for that. A hash table is much better. Trees are mainly useful when the ordering of keys matters (you have operations like "find smallest key >= this given value"); when the only operation is "find value corresponding to this key", hash tables are superior.

If he stored all the possible sums/products simultaneously, that's a major source of unnecessary memory use. You can easily generate just the triples that have one particular sum, and can then filter those that have a repeated product within the same-sum set. So you never need to store non-obscure triples for two different sums simultaneously.

The Youtube comment from Thomas Egense sounds similar to how the script works, except it sounds like his implementation of detecting runs of obscure triples was somewhat clumsier. It sounds like he stored the obscure triples for 6 consecutive years and then always checked if they shared anything, which also means he needs a separate check for 7 years. All pairs (a, b, c), (a+1, b+1, c+1) etc in a run have the same pair (b-a, c-a). The script keeps a list of such pairs which were obscure for the previous sum, and how many years they've been obscure for. If a pair is no longer obscure for the latest sum, then you know how long its run was, and it's removed from the list. This works for any length of run with no special handling.

[Dr Sardonicus]

Amusingly, triples (a, b, c) can be "disambiguated" by the value a*b + a*c + b*c.

This is because the cubic polynomial

(x - a)*(x - b)*(x - c) is

x^2 - (a + b + c)*x^2 + (a*b + a*c + b*c)*x - a*b*c.

Obviously, this idea generalizes -- a set of k numerical values (though not their order) is determined by the numerical values of the elementary symmetric polynomials in k variables.

[Dr Sardonicus]

Since part of the solution in the video created an array for all possible pairs (s, p) of sum and product of three natural numbers a, b, c, I decided to look at the cubic polynomial idea, purely from a theoretical standpoint. I use

s = a + b + c,

p = a*b*c, and

z = a*b + a*c + b*c. Then,

(x - a)*(x - b)*(x - c) is the cubic polynomial

f = x^3 - s*x^2 + z*x - p

which has discriminant

D = -4*z^3 + s^2*z^2 + 18*p*s*z + (-4*p*s^3 - 27*p^2).

Now if f has zeroes a, b, and c, then

D = (a - b)^2 * (a - c)^2 * (b - c)^2

so if a, b, and c are integers, we have an integer pair (z, y) on the elliptic curve

y^2 = -4*z^3 + s^2*z^2 + 18*p*s*z + (-4*p*s^3 - 27*p^2).

Using these ideas to determine whether a random pair (s, p) is actually the sum and product of a triple of integers (a, b, c) is probably not optimal from a computational standpoint.

Suppose, however, that you have different triples (a, b, c) and (a', b', c') with the same s and p, ("obscure triples") and you want to check whether

(a + 1, b + 1, c + 1) or (a' + 1, b' + 1, c' + 1)

are ambiguous.

An obvious approach is to look at the product

P = (a+1)*(b+1)*(c+1)

and see whether there is another way of expressing P as a product of three factors with the same sum; and similarly for a', b', and c'

But you also have elliptic curves as above, with

P = (a+1)*(b+1)*(c+1), S = a + b + c + 3, and known integer point

z = (a + 1)*(b + 1)*(c + 1), y^2 = (a - b)^2 * (a - c)^2 * (b - c)^2.

and similarly for a', b', c'. Note that adding the same value to each of a, b, and c does not affect the value of y^2.

I note that ambiguous triples (a, b, c) that persist for k years would produce, correspondingly, k+1 elliptic curves with multiple integer points, and these curves would all have at least one integer point (z, y) with z = (a + t)*(b + t) + (a + t)*(c + t) + (b + t)*(c + t), t = 0 to k, and the common value of

y^2 = (a - b)^2 * (a - c)^2 * (b - c)^2.

I don't know a whole lot about elliptic curves, but the fact that "persistently" obscure triples produce several elliptic curves with integer points (z, y) having a common value of y^2 may have something to do with the notable increase in size from "four more years" to "five more years."