Re: LOGO-L> Last 2 Digits of 2^999

["Tom Lynn" <thl22@cam.ac.uk>]

On 20 Sep 98, at 16:40, Yehuda wrote:

> Hello Logo friends,
> 
> Logo is a great program to do arithmetics too - a fact that is sometimes
> overlooked. Last week, a friend asked me what were the last 2 digits of
> 2^999 (2 raised to the power of 999).

Your friend might have been hoping that you wouldn't need a computer :)

A method of doing this on paper would be as follows:
Write down this table:

 n  Last 2 digits of 2^n
========================
 0  01
 1  02
 2  04
 3  08
 4  16
etc.

Eventually, you will find a pair of last two digits (LTDs) which have 
occurred in the table before.  For example, the LTDs of 2^24 are 16, which 
are also the LTDs of 2^4.  So the LTDs of 2^25 will be 32, the LTDs of 2^26 
will be 64 and so on.  But we also know that the LTDs of 2^44 will be 16, 
as will the LTDs of 2^64, 2^84, 2^104, etc. So you can look up the LTDs for 
any 2^x by just counting on ((x-4) mod 20) places in the table starting 
from 2^4.

Having worked out that it can be done on paper, here's an implementation of 
this idea in Logo, as paper is far too messy :).  It could be made more 
efficient by using a 100-element array, but it doesn't generalise as well 
as Yehuda's original code because it uses a lot of memory.  It is possible 
to do without the table altogether though... I'll try to post an example of 
this in a few days if no-one else wants to give it a go.


to aaa
; Calculates the last two digits of powers of two for high powers.

  local [table repeat.position]
  make "table []
  make "repeat.position buildtable 01
  print list "Table: :table
  print (list ~
    "Last "two "digits "of "2^999 "are
    lastdigits 999
  )
end

to buildtable :prev.digits [:n 2]
  local [next.digits after.repeat]
  make "next.digits remainder :n*:prev.digits 100
  make "after.repeat member :next.digits :table
  ifelse emptyp :after.repeat [
    make "table lput :next.digits :table
    op (buildtable :next.digits :n)
  ][
    op (count :table) - (count :after.repeat) + 1
      ; Returns position in table at which repeat occurs
  ]
end

to lastdigits :x [:n 2]
  ifelse :x > :repeat.position [
    op zeropad item :repeat.position + remainder :x - ~
     :repeat.position (count :table)-:repeat.position+1 :table
  ][
    op zeropad item :x :table
  ]
end

to zeropad :x
; Adds a zero to the front if only one digit
  op ifelse :x < 10 [ifelse :x = 0 ["00][word "0 :x]][:x]
end


Tom                                               end ;-)
---------------------------------------------------------------
Please post messages to the Logo forum to logo-l@gsn.org.  Mail
questions about the list administration to logofdn@gsn.org.  To
unsubscribe send    unsubscribe logo-l    to majordomo@gsn.org.