Euler problem #63

[Anton Ertl]

Still small enough to solve in a few lines:

http://www.complang.tuwien.ac.at/forth/programs/euler/63.fs

\ Problem:
\ The 5-digit number, 16807=75, is also a fifth power. Similarly, the
\ 9-digit number, 134217728=89, is a ninth power.

\ How many n-digit positive integers exist which are also an nth power?
\ They don't count 0^1 (0 is not deemed to be positive)

\ Solution:
\ 10^n produces a n+1-digit integer, so we need only look at bases 0-9.

: n-digits { n -- n2 }
\ number of n-th powers with n digits
\ for n=1, it does not count 0 and 1 (I correct for the 1 below)
\ this works by just seeing what the lowest x is that fits in
\ 10^(n-1), and then rounding x up to an integer
n 1- 0 d>f n 0 d>f f/ falog f>d drop 9 swap - ;

: solve ( -- )
1 1 begin ( n sum )
over n-digits dup 0> while
+ swap 1+ swap repeat
drop nip ;

solve . cr

- anton
--
M. Anton Ertl http://www.complang.tuwien.ac.at/anton/home.html
comp.lang.forth FAQs: http://www.complang.tuwien.ac.at/forth/faq/toc.html
New standard: http://www.forth200x.org/forth200x.html
EuroForth 2008: http://www.complang.tuwien.ac.at/anton/euroforth/ef08.html

[William James]

On May 5, 11:49 am, an...@mips.complang.tuwien.ac.at (Anton Ertl)
wrote:

> Still small enough to solve in a few lines:
>
> http://www.complang.tuwien.ac.at/forth/programs/euler/63.fs
>
> \ Problem:
> \ The 5-digit number, 16807=75, is also a fifth power. Similarly, the
> \ 9-digit number, 134217728=89, is a ninth power.
>
> \ How many n-digit positive integers exist which are also an nth power?
> \ They don't count 0^1 (0 is not deemed to be positive)
>
> \ Solution:
> \ 10^n produces a n+1-digit integer, so we need only look at bases 0-9.
>
> : n-digits { n -- n2 }
> \ number of n-th powers with n digits
> \ for n=1, it does not count 0 and 1 (I correct for the 1 below)
> \ this works by just seeing what the lowest x is that fits in
> \ 10^(n-1), and then rounding x up to an integer
> n 1- 0 d>f n 0 d>f f/ falog f>d drop 9 swap - ;

Clever, but the stack makes it hard to follow the code.

>
> : solve ( -- )
> 1 1 begin ( n sum )
> over n-digits dup 0> while
> + swap 1+ swap repeat
> drop nip ;

Again, the stack makes it very difficult to follow.
When one sees the +, he can't easily tell what two
items are being added together. This code is hard
to understand and to modify.

Ruby:

def n_digits n
9 - ( 10 ** ((n-1.0) / n) ).to_i
end

sum = 1
(1 .. 9999).each{|i|
n = n_digits(i)
break if n < 1
sum += n }
p sum

[Anton Ertl]

William James <w_a_...@yahoo.com> writes:
>On May 5, 11:49 am, an...@mips.complang.tuwien.ac.at (Anton Ertl)

>> : n-digits { n -- n2 }
>> \ number of n-th powers with n digits
>> \ for n=1, it does not count 0 and 1 (I correct for the 1 below)
>> \ this works by just seeing what the lowest x is that fits in
>> \ 10^(n-1), and then rounding x up to an integer
>> n 1- 0 d>f n 0 d>f f/ falog f>d drop 9 swap - ;
>
>Clever, but the stack makes it hard to follow the code.

I find that the conversion between integer and FP, with a double-cell
intermediate step makes it a little bit convoluted. One can fix that
with factoring (and using FLOOR, which I have hitherto overlooked):

: u>f 0 d>f ;
: f>u f>d drop ;
: nnf/ ( n1 n2 -- f ) swap u>f u>f f/ ;
: n-digits1 { n -- r }
9e n 1- n nnf/ falog floor f- ;

>> : solve ( -- )
>> 1 1 begin ( n sum )
>> over n-digits dup 0> while
>> + swap 1+ swap repeat
>> drop nip ;
>
>Again, the stack makes it very difficult to follow.
>When one sees the +, he can't easily tell what two
>items are being added together. This code is hard
>to understand and to modify.

With N-DIGITS1, it becomes a little easier:

: solve ( -- r )
1 1e begin ( n rsum )
dup n-digits1 fdup f0> while ( n rsum r )
f+ 1+ repeat
fdrop drop ;

Or you can use locals to reduce the stack load:

: solve ( -- r )
1 1e begin { n f: rsum }
n n-digits1 { f: r }
r f0> while
n 1+ r rsum f+ repeat
rsum ;

But given the tone of your posting, I guess you think that the stack
makes that difficult to follow, too. Then you have two options:

1) Get some more practice in reading Forth or other stack-based
languages. You may eventually get the hang of it.

2) Conclude that stack-based languages are not for you and stick with
whatever other language you like.

[Albert van der Horst]

In article <67930447-88f9-4fdc...@m3g2000hsc.googlegroups.com>,

Please don't publish spoilers without the words spoiler in
the subject line.

Groetjes Albert

--
--
Albert van der Horst, UTRECHT,THE NETHERLANDS
Economic growth -- like all pyramid schemes -- ultimately falters.
albert@spe&ar&c.xs4all.nl &=n http://home.hccnet.nl/a.w.m.van.der.horst