[seqfan] Re: n consecutive perfect powers sum to a perfect power

[Tim Peters]

I'll attach a Python program that works to cut off sums when it becomes
futile to pursue them. I assume your algorithm isn't doing that, because
this only takes about 2 seconds to finish 10^10 (running under PyPy).

At 10^14 it took noticeable (very noticeable ;-) ) time, but still didn't
find a solution for sums of 9 or 10 consecutive powers. It found 744
solutions in all, the longest being a sum of 59924 consecutive powers,
starting at 37711881, summing to 92121066512784 (the square of 9597972).

The code:

from math import isqrt

TOP = 10**10
SHOW_DELETES = False

ppset = {1}
for i in range(2, isqrt(TOP) + 1):
   power = i
   while (power := power * i) <= TOP:
       ppset.add(power)
pp = sorted(ppset)
npp = len(pp)
MAXPP = pp[-1]
print(f"len(pp)={npp:_} through {TOP=:_}; {MAXPP=:_}")

sums = pp[:]
nterms = 0
delta = 1
while sums:
##    # Crucial invariant, but expensive to check.
##    assert all(sums[i] == sum(pp[i : i + delta])
##               for i in range(len(sums)))
    winner = -1
    for i, s in enumerate(sums):
        if s in ppset:
            winner = s
            assert sum(pp[i : i + delta]) == s
            break
    if winner > 0:
        nterms += 1
        print(nterms, delta, winner,
              f"starting at pp[{i}] = {pp[i]}, {len(sums)=:_}")
    if len(sums) + delta > npp:
        sums.pop()
        assert len(sums) + delta == npp
    for i in range(len(sums)):
        sums[i] += pp[i + delta]
        if sums[i] > MAXPP:
            if SHOW_DELETES:
                print("    deleting", len(sums) - i,
                      "of", len(sums),
                      "at delta", delta)
            del sums[i:]
            break
##    assert sums == sorted(set(sums))
    delta += 1

On Wed, Dec 13, 2023 at 12:44 AM jnthn stdhr <jstdhr at gmail.com> wrote:

> Howdy, all.
>
>   What is the least perfect power m (in A001597) that is the sum of n
> consecutive perfect powers.
>
>   The sequence isn't in the database, and begins 1, 25, 441, 100, 169, 289,
> 121, 2395417249, -1, -1, 676, 232324, -1, -1, -1, 64866916, 3721,
> 3622354596, 279936, ..., with -1 representing no solution found up to
> ~10^10.
>
>   For the first few terms, we have:
>
> {1}=1, {9+16}=25, {128+144+169}=441, {16+25+27+32}=100, etc.
>
>   Should I add this? If so, up to a(8) only, or include the -1s?
>
>  When I first searched for solutions, the maximum value of the set of
> perfect powers was ~10^8, and both a(8) and a(18) came out -1.  But when I
> increased the max to 10^10 solutions for those two terms were found.  At
> 10^8 I was able to get to 100+ terms in a somewhat reasonable time, with
> solutions becoming more and more sparse.  At 10^10, things get very bogged
> down, but more solutions are found along the way.  Also, the erratic nature
> of the terms seems to persist.
>
>   Can a solution always be found if the set of perfect powers is large
> enough?
>
> -Jonathan
>
> --
> Seqfan Mailing list - http://list.seqfan.eu/
>