Re: Special Squares

Path	csiph.com!v102.xanadu-bbs.net!xanadu-bbs.net!news.glorb.com!news-out.octanews.net!indigo.octanews.net!auth.beige.octanews.com.POSTED!not-for-mail
From	Paul Rubin <no.email@nospam.invalid>
Newsgroups	comp.lang.forth
Subject	Re: Special Squares
References	<96100310008435@frunobulax.edu>
Date	Sun, 25 Mar 2012 12:57:20 -0700
Message-ID	<7xpqc01mjj.fsf@ruckus.brouhaha.com> (permalink)
Organization	Nightsong/Fort GNOX
User-Agent	Gnus/5.13 (Gnus v5.13) Emacs/23.1 (gnu/linux)
Cancel-Lock	sha1:Wsr0HvtQ2jV/NfXvUDzWfnrya7w=
MIME-Version	1.0
Content-Type	text/plain; charset=us-ascii
Lines	33
NNTP-Posting-Date	25 Mar 2012 14:57:20 CDT
X-Complaints-To	abuse@octanews.net
Xref	csiph.com comp.lang.forth:10457

Show key headers only | View raw

mhx@iae.nl (Marcel Hendrix) writes:
> Is there an 18-digit whole number x, such that the last 18 digits of 
> x^2 are in fact the original number x? If yes, how many of these x's 
> exist? List it / them.
>
> Less than 18 digits is not interesting, Extra points for larger 
> numbers.

I couldn't make much sense of the code you posted, but I think most of
the complexity of doing that in Forth is from two places: 
1) multi-precision arithmetic needed to square 18 digit numbers,
2) starting with a list of solutions for n digits, finding the solutions
   for n+1 digits by checking through the n-digit list.  This is easiest
   in a language with primitive lists.  In Forth it might be interesting
   to do it instead with multitasking, with one task for each n, passing
   values through channels instead of making lists.

Anyway, here is my Haskell solution:

    check ndigits n = (n == (n*n)`mod`(10^ndigits))

    next (d,ns) = (nd, [v | k<-[0..9], n<-ns, let v=k*10^d+n, check nd v])
      where nd = d+1

    rs = (0,[0]) : map next rs

    main = print (rs !! 18)

The output is (18,[0,1,256259918212890625,743740081787109376])
and it prints this basically instantaneously.

I'll see if I can figure out a comparable Forth approach, but there's
too much distraction here right now to be able to think about it.

Back to comp.lang.forth | Previous | Next — Previous in thread | Next in thread | Find similar

Thread

Special Squares mhx@iae.nl (Marcel Hendrix) - 2012-03-25 00:25 +0200
  Re: Special Squares Paul Rubin <no.email@nospam.invalid> - 2012-03-25 12:57 -0700
    Re: Special Squares mhx@iae.nl (Marcel Hendrix) - 2012-03-25 23:12 +0200
      Re: Special Squares Paul Rubin <no.email@nospam.invalid> - 2012-03-25 19:16 -0700
    Re: Special Squares Bernd Paysan <bernd.paysan@gmx.de> - 2012-03-26 01:10 +0200
      Re: Special Squares Paul Rubin <no.email@nospam.invalid> - 2012-03-25 18:39 -0700
        Re: Special Squares Bernd Paysan <bernd.paysan@gmx.de> - 2012-03-26 18:05 +0200

csiph-web