Prime power triples

2015-10-30

Problem 087: Prime power triples

Description:

The smallest number expressible as the sum of a prime square, prime cube, and prime fourth power is 28. In fact, there are exactly four numbers below fifty that can be expressed in such a way:

28 = 2^2 + 2^3 + 2^4
33 = 3^2 + 2^3 + 2^4
49 = 5^2 + 2^3 + 2^4
47 = 2^2 + 3^3 + 2^4

How many numbers below fifty million can be expressed as the sum of a prime square, prime cube, and prime fourth power?

Solution:

v000000000
################################################################
# ... #
. . . .
.  .  .
. . . .
# ... #

>150p0>:50g::+50p\1pv
      |-">":+1      <
v    $<
>"}"8* :   8   : 2v>"X"\:10g%\10g/2+p:40 v
v222p040p03*p01\p0<:vp+2/g01\%g01:p04+1:g<
>10g%\10g/2+g " "- |>:::50p+>:30g\`!#v_:" "\: v
|-g03:::         +1<        ^+g05p+2/ g01\%g01<
>$$$"o"9*:20p10g*:v^                $<
vp050p08*9"e"-1p03<
>:0\:10g%\1 v
|+1:-1p+3/g0<            v+1                           >#  v#     $$<                 <
>$"}}P("***90p0>:2g:*60p0>:80g\`!#v_:2g::**60g+:70p90g`#v_0>:80g\`!#^_:2g:*:*70g+:90g`|
               |-g08:+1$          <                    #<v1+1%"<"\g+3/g01\%g01:/"<":::<
         @.g05$<                                         >g%\"<"%1g/#v_::"<"/:10g%\10g/3+g\"<"%1g+v
                                                       ^+1          $<0p05+1g05p+3/g01\%g01:/"<"\ <

Download

This program is too big to display/execute here, click [download] to get the full program.

Explanation:

Here we iterate quite simply through all the primes[a]^2 + primes[b]^3 + primes[c]^4 combinations and remember the already found ones.

The prime numbers are generated with the help from our old friend the Sieve of Eratosthenes (i improved my befunge snippet for this algorithm a little bit. It's now a bit faster and smaller in size).

The main problem was that we needed an bit-array with an size of fifty million bits. Normally I would simply use an array of size fifty million. But we need to only store Boolean information. So I used a "trick" were I stored sixty bits per cell (these are 64-bit values, but I wanted to prevent signed/unsigned problems and I had the problem that the stack is also only 64-bit). Unfortunately befunge has no bit operators. So we had to re-invent bit-setting and bit-getting with division, modulo and addition operators.

In the end this didn't make the program fast, but the file size is under 1MB. And I think the run time is acceptable.

Interpreter steps:	181 436 097
Execution time (BefunExec):	27s (6.70 MHz)
Program size:	1000 x 1018
Solution:	1097343
Solved at:	2015-10-30