Distinct powers

2014-09-20

Problem 029: Distinct powers

Description:

Consider all integer combinations of ab for 2 <= a <= 5 and 2 <= b <= 5:

2^2=4,  2^3=8,   2^4=16,  2^5=32
3^2=9,  3^3=27,  3^4=81,  3^5=243
4^2=16, 4^3=64,  4^4=256, 4^5=1024
5^2=25, 5^3=125, 5^4=625, 5^5=3125

If they are then placed in numerical order, with any repeats removed, we get the following sequence of 15 distinct terms:

4, 8, 9, 16, 25, 27, 32, 64, 81, 125, 243, 256, 625, 1024, 3125

How many distinct terms are in the sequence generated by ab for 2 <= a <= 100 and 2 <= b <= 100?

Solution:

v
000
###
. .
  .
. .
###

> "]M~A~~~~~h!"++++++*+**10p":~+"+*55+0p"d"2*1+20pv
v                                                 <                                                                                                                   v                                               <     "4"<               @.g0+55$<
       v                   <   "4"<                 >       $v                    v                    p05/+55p06<               v                            <                       >-!#v_             v
>20g"4">80p:0\80gp80g1-:1-#^_$1-:#^_$"dd">80p:80g\20 g>:0\1pv>120g1p40p>050p20g60p>60g1g40g*50g+:55+%60g1p60g1-:#^_$$1-:#v_$0170p>9*70g1g+10g%70g1+:70p20g-1-#^_20g"4">90p30p:30g90gg:|   >55+0g1-55+0p$v>30g90g1-:1-#^_$1-:1-#^_@>80g1-:1-#v_$1-:1-#v_^
                                                    ^_^#!:-1<          ^                                                 <                                                            >$30g90gp$        >                         ^
                                         ^                                                                                                                                                                                                  <"d"     <

Download

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

Explanation:

This problem is really not made for Befunge. The numbers become quickly too big to be stored in a 64 bit field, and you need to remember a lot of them.

My solution is probably a bit hacky/cheaty: We calculate the numbers via long multiplication and 200 single fields. Then we calculate a hash of that number and store the hash.
The cheaty part is that I needed to be sure there are no hash collisions in our set of numbers - so I tested it beforehand in a quick C# solution. And on a side note: Its disturbing how easy these problems are in a high-level language after working with Befunge for such a log time :(

Interpreter steps:	6 439 429 168
Execution time (BefunExec):	23min (4.52 MHz)
Program size:	248 x 59
Solution:	9183
Solved at:	2014-09-20