July 2018

[uau]

Originally Posted by EdH

I guess I didn't have the horsepower and my c++ programs were way too inefficient.

That had to be an inefficient algorithm, a single-threaded Python program was enough to find six consecutive in a reasonable time. Here's the code I used:

#!/usr/bin/python3

def search(ceil, minsum, ceilsum):
    for m in range(3):
        runs = {}
        for s in range(minsum + m, ceilsum, 3):
            d = {}
            t = set()
            for a in range(ceil):
                for b in range(max(a, s-a-ceil+1), min(ceil, (s-a)//2 + 1)):
                    c = s - a - b
                    k = a * b * c
                    if k in d:
                        t.add(d[k])
                        t.add(((b-a) << 16) + (c-a))
                    else:
                        d[k] = ((b-a) << 16) + (c-a)
            d = set(runs)
            d.difference_update(t)
            for k in d:
                r = runs[k]
                if r >= 5:
                    b, c = k >> 16, k & 65535
                    a = (s - b - c) // 3
                    print(r, a - r, b+a-r, c+a-r)
                    if r >= 6:
                        print('***********************************')
                del runs[k]
            for k in t:
                runs[k] = runs.setdefault(k, 0) + 1
        for k in runs:
            if runs[k] >= 5:
                print("run at end:", runs[k], k>>16, k&65535)

for i in range(0, 9000, 400):
    print(i)
    search(3000, i, i + 420)

[henryzz]

Products from sums is better than the sums from factorizations of products that I was doing.

If you look at the comments in https://www.youtube.com/watch?v=m0f1p5Aj7Qc you will see that someone tested upto 32k. Does anyone have any ideas for extending past that search depth?

[uau]

Originally Posted by henryzz

someone tested upto 32k. Does anyone have any ideas for extending past that search depth?

You could easily partition the search space by product size too (require A <= product < B; all products involved in the run have to be of roughly similar size, so ranges with some overlap work). Adding that to an implementation like my Python code should keep memory use down even for significantly larger sums.

But if the issue becomes that it's just too slow to search higher and higher sums, I haven't thought of any significant improvements for that.

[henryzz]

I think there are methods of speeding up a fair bit. Currently your search will find all obscure triples while all we are interested in are ones where there are consecutive triples.
It should be possible to only check every 6 sums to find 5 consecutive(in groups of 3). If an obscure triple is found it will then be necessary to extend it downwards as well as upwards to get the full length. Every 8 would be possible to find the elusive 7 consecutive although it might miss some 6s then which would be a shame.

Have you profiled this code to see where the slow bits are? Is that possible in python? Would compiling the python code using cython or similar help?

Is your code maxed at 65536?

[uau]

I considered that once-every-6-sums thing after posting my last message, but that would still only be a constant speedup by less than a factor of 6. If you're seriously interested in searching large values writing the equivalent in C is probably worth it (mainly requires taking a hash table implementation from somewhere). The code has no natural size limits - the Python variables are all arbitrary-size integers.

[uau]

Forgot to mention that the code does shift by 16 to save time/memory (basically store two integers in one Python integer object, rather than create a separate tuple object), which can overflow - but you could just increase that to an arbitrary size.

[henryzz]

Originally Posted by uau

I considered that once-every-6-sums thing after posting my last message, but that would still only be a constant speedup by less than a factor of 6. If you're seriously interested in searching large values writing the equivalent in C is probably worth it (mainly requires taking a hash table implementation from somewhere). The code has no natural size limits - the Python variables are all arbitrary-size integers.

It was the shifting 16 all over the place that made me think there was a limit. Changing it to fixed size integers might be the obvious speedup that can often add a lot of overhead. I might have a go at converting your implementation to C#. This will get most of the benefit of c and has a hashset built in. I will also be able to profile the code to enable me to spot the slow points easily.

[henryzz]

Using pypy got me an instant 4x speedup

[EdH]

You guys are obviously way above my capabilities in knowledge of things like tables, etc. I really haven't programmed in a long time and it was always a simple hobby, other than my first ever assembly program long, long ago, which was actually useful at the time and made me a tiny amount of money that cost me more in taxes than I made from the sale.


The inefficiency of my programs was from the nested loops. The abc loops initiated all the sums and products, which were tested by the ijk loops. If an obscure triple was found, another set of loops checked subsequent abc's.


My assembly program was constructed in much the same way.


I did use loop breakers when the sum of ijk overtook the sum of abc.


Oh, well, enough of what didn't work! On to study what has been posted that worked...

[Dr Sardonicus]

I never would have thought of the approach described in the video, and had never heard of a "red black tree," so it was educational for me.

I also don't have anywhere near 13GB of RAM...

[uau]

Originally Posted by Dr Sardonicus

I never would have thought of the approach described in the video

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.