Project Euler with Befunge


Fork me on GitHub
2015-07-08

Problem 063: Powerful digit counts

Description:

The 5-digit number, 16807=7^5, is also a fifth power. Similarly, the 9-digit number, 134217728=8^9, is a ninth power.

How many n-digit positive integers exist which are also an nth power?


Solution:
v XXXX   #######################################################################
  XX
                          v1\1p12::+1   \+g2<
0                 v9p03p02<         \g12:+1<^2\p22_v
1          >v     v              <  v-\"P"<       :$
>        :v1v>0p>9>:"0"\0p1+:"O"-|>:0g"0"-||!`g12<-$
          :p\3v p050p04"O"<p0\"1"<^+>#1 $#< :21g-|\.
          211p> 40g0g"0"-2 0g*50g+:55+%"0"v>$55+0v+@
          >^20|-8p04:-1g04 p05/+5 #5p0g04+<>5#$5#<^
            >^>30g1-:30p #^_9     ^
Start
??
Pause
Reset
Output:
Stack:   (0)

Explanation:

After all the previous programs, this one is surprisingly ... dense (the main code-block is 54x8).

The algorithm is quickly explained for each length n we calculate the numbers 1^n, 2^n ... until 9^n and see which have a length of n. (From 10^n upwards the condition is impossible, because 10^n has (n+1) digits).

The main problem is that the numbers exceed Int64. So we need to implement long multiplication ... again. (see problem 16, 20, 29, 56 and 57)


Interpreter steps: 8 880 369
Execution time (BefunExec): 2.76s (3.22 MHz)
Program size: 80 x 10 (fully conform befunge-93)
Solution: 49
Solved at: 2015-07-08



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