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