Re: [FWP] Golf (7 strokes is par!)

[Ilmari Karonen <iltzu@sci.fi>]

On Mon, 1 May 2000, Ilmari Karonen wrote:
> On 1 May 2000, Ariel Scolnicov wrote:
> > Jeff Pinyan <jeffp@crusoe.net> writes:
> > > Challenge: determine if $_ is an integral power of 2 (1,2,4,8,16,...)
> > > I have it down to 7 characters.  Can anyone beat that?
> > 
> > print"$_ is a power of 2"unless$_&$_-1;
> 
> Another answer with 7 strokes: $_&~-$_
> 
> Six strokes seems impossible to me - I'll get back as soon as my
> exhaustive search finishes..

Well, it did finish at last.  No 6-stroke answers, but I did find a third
7-stroke solution.  All three are listed below - there are of course also 
three more trivial solutions obtained by swapping the operands for &.

 1.  $_ & $_ - 1
 2.  $_ & ~ - $_
 3.  $_ & $_ / 3

The first answer is Jeff's original, and proof of its correctness has
already been given.  The second is identical to the first assuming ones'
complement arithmetic, since ~$x == -$x - 1.


The third answer is a bit more interesting.  It is trivially obvious that 
it must evaluate to zero whenever $_ is a power of 2.  To prove that the
converse is true, we'll begin by assuming that the number has been shifted
right enough that the second highest set bit is the LSB.

This lets us consider only numbers of the form 2**n + 1, where n is a
positive integer.  We must prove that for all n

  ((2**n + 1) / 3) & 1

is non-zero, that is, that the LSB remains set even after the division.
The following two statements are equivalent to the one above:

  ((2**n + 1) / 3) % 1 >= 1 
  
        (2**n + 1) % 6 >= 3

This is true if n == 1, since 2**n + 1 == 3.  Now, if a == 2**n + 1, then
2**(n+1) + 1 == 2*a - 1, and also (2**(n+1) + 1) % 6 == (2*a - 1) % 6.

Building a table of all the possible values, we see that:

  a % 6 == 0  =>  (2*a - 1) % 6 == 5
  a % 6 == 1  =>  (2*a - 1) % 6 == 1
  a % 6 == 2  =>  (2*a - 1) % 6 == 3
  a % 6 == 3  =>  (2*a - 1) % 6 == 5  (*)
  a % 6 == 4  =>  (2*a - 1) % 6 == 1
  a % 6 == 5  =>  (2*a - 1) % 6 == 3  (*)

The lines marked with (*) indicate that, if (2**n + 1) % 6 belongs to the
set {3, 5}, then so will (2**(n+1) + 1) % 6.  Since we have shown that
this is true for (2**1 + 1) % 6, by induction it must hold for all n, QED.

-- 
Ilmari Karonen
http://www.sci.fi/~iltzu/


==== Want to unsubscribe from Fun With Perl?  Well, if you insist...
==== Send email to <fwp-request@technofile.org> with message _body_
====   unsubscribe