Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.forth > #10457

Re: Special Squares

Show all headers | 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