Re: compositing / decomposing numbers

From: Keith A. Lewis (lewis_at_spyder.mitre.org)
Date: 06/07/04 

Date: Mon, 7 Jun 2004 17:54:29 +0000 (UTC)

=?ISO-8859-1?Q?Daniel_Sj=F6blom?= <dsjoblom@mbnet.fi_NOSPAM> writes in article <40c44f8e$0$12816$7b6a8dc4@news.mbnet.fi> dated Mon, 07 Jun 2004 14:21:49 +0300:
>Matthijs Blaas <<remthis>thijs_blaas wrote:
>> Hi All,
>>
>> I want to construct a number from X values and do something with each number
>> so I can calculate a value on position P back.
>>
>> number 1: 5
>> number 2: 8
>> number 3: 9
>> total: 22
>>
>> For example, is there a way I could calculate number 2 back to 8 given the
>> total nr of values(3) and some kind of logic (like multiplying with
>> sequentially ordered prime numbers or something)? I don't think there's any
>> way of doing this with multiplication, but my knowledge of math is limited
>> (maybe there is some method available) and I need something similar to this
>> for an computer program Im writting...
>
>Assuming all the numbers are positive, you could do the following:
>
>First label each number x with a label i, starting from 1. Then for each
>x construct a number y so that
>
>y = i-th prime ^ x
>
>Then compose a number z that is the product of all y. To find x given i
>and z, do the following:
>
>Factor z into standard form:
>
>p0 ^ x0 * p1 ^ x1 * ... * pn ^ xn
>
> From that factoring find the prime pn that is the i-th prime. Then x is
>the xn corresponding to that pn.

That works great and even gives you the number of values. But it tends to
make some large numbers -- the example (5,8,9) would give 410,062,500,000.

If you have a range for your numbers the job is easier. If you specify that
all numbers must be in the range 0-9 you could encode the example as
x1+x2*10^1+x3*10^2 which comes out to 985.

--Keith Lewis klewis {at} mitre.org
The above may not (yet) represent the opinions of my employer.