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"     <
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

made with vanilla PHP and MySQL, no frameworks, no bootstrap, no unnecessary* javascript