At 1:45 PM -0500 12/1/00, Porter, Allen H wrote:
>If I have a series such as
[ the powers of 2 ]
>
>and I add any combination of these numbers together (4 + 16 = 20) the only
>way I can come up with the number 20 is by adding 4 and 16.  Now how do I do
>this in reverse?  If I know the sum is 81, how do I determine that the
>numbers that make up this sum are 1 + 16 + 64?


To which Tom Emerson replied:

>set aside a value of '1'
>recursively DIVIDE your number by 2:
>   if the remainder is 1, then the number "set aside" is one of the numbers
>that makes up the "sum" you're after
>   double the "set aside" number
>repeat until the target number is zero.
>
>Using your example (81) we have:
>
>number (/2) rem  set aside   result set
>----------------------------------------
>  81    40   1      1        1,
>  40    20   0      2        1,
>  20    10   0      4        1,
>  10     5   0      8        1,
>   5     2   1     16        1, 16,
>   2     1   0     32        1, 16,
>   1     0   1     64        1, 16, 64,
>   0     -   -     --        1, 16, 64.


Ted Ashton responded similarly, and added:

>This will also work for other powers:
>
>  81 / 5 = 16 r 1      1
>  16 / 5 =  3 r 1      5
>   3 / 5 =  0 r 3     25
>
>giving 81 = 1 + 5 + 75


Well, I couldn't resist...below is an MPE script that does this. By default
it works in "base 2" mode, but will work in any base if you specifiy it in
the second parameter. Also for bases larger than 2 you can specify "detail"
as the third parameter which shows you when the remainder at a particular
power is greater than 1 (see examples for what I mean). For lack of a
better name I call the script "powersum", since we're summing the powers of
a given base to arrive at the result. This is a "bare bones" script with no
error checking of any kind.

  :print powersum.cmd
  parm num=0, base=2, format=concise

  setvar power     1
  setvar result    ""
  setvar cur_val   !num

  while cur_val > 0
     setvar mod_val cur_val mod !base
     if mod_val > 0
        if len(result) > 0
           setvar result result + "+"
        endif
        if UPS("!format")="DETAIL" and mod_val > 1
           setvar result result + "(!mod_val*!power)"
        else
           setvar result result + "![mod_val * power]"
        endif
     endif
     setvar power power * !base
     setvar cur_val cur_val / !base
  endwhile

  echo !num = !result
  :
  :powersum 81
  81 = 1+16+64
  :powersum 81,5
  81 = 1+5+75
  :powersum 81,5,detail
  81 = 1+5+(3*25)
  :powersum 31
  31 = 1+2+4+8+16
  :powersum 31,5
  31 = 1+5+25
  :powersum 4095
  4095 = 1+2+4+8+16+32+64+128+256+512+1024+2048
  :powersum 4095,8
  4095 = 7+56+448+3584
  :powersum 4095,8,detail
  4095 = (7*1)+(7*8)+(7*64)+(7*512)
  :powersum 4096
  4096 = 4096
  :powersum 4096,8
  4096 = 4096
  :

Enjoy!


Barry Lake                              [log in to unmask]
Allegro Consultants, Inc.               www.bogus.allegro.com
(408)252-2330
--------
Attempting to reduce spam influx.
Remove ".bogus" to create valid address.