Powerful digit counts
2015-07-08
Problem 063: Powerful digit counts
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 ^
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 |