A number theory puzzle (or maybe triviality?)

Hi all.

In the decimal number system, the largest positive integer
one can express with N digits is

M_10(N) = 10^0 + 10^1 + 10^2 + ... + 10^(N-1) = 10*10^N -1.

Similarly, the largest positive binary integer one can express
with N bits is

M_2(N) = 2^0 + 2^1 + 2^2 + ... + 2^(N-1) = 2*2^N -1.

This empirical evidence suggestes to me that the largest
positive integer that can be expressed with N coefficients(?)
in a base B number system is

M_B(N) = B^0 + B^1 + B^2 + ... + B^(N-1) = B*B^N -1.

Is this correct? If so, how does one prove it?

Rune

Rune Allnor said the following on 30/09/2006 16:34:
> Hi all.
> 
> In the decimal number system, the largest positive integer
> one can express with N digits is
> 
> M_10(N) = 10^0 + 10^1 + 10^2 + ... + 10^(N-1) = 10*10^N -1.

This should be:

     9 * [10^0 + 10^1 + 10^2 + ... + 10^(N-1)] = 10^N - 1
> 
> Similarly, the largest positive binary integer one can express
> with N bits is
> 
> M_2(N) = 2^0 + 2^1 + 2^2 + ... + 2^(N-1) = 2*2^N -1.
> 
> This empirical evidence suggestes to me that the largest
> positive integer that can be expressed with N coefficients(?)
> in a base B number system is
> 
> M_B(N) = B^0 + B^1 + B^2 + ... + B^(N-1) = B*B^N -1.

(B-1) * [B^0 + B^1 + B^2 + ... + B^(N-1)] = B^N - 1
> 
> Is this correct? If so, how does one prove it?

These are truncated geometric series, given by:

     S = a (1 - r^n) / (1 - r)

where a is the first number in the series, r is the multiplier, and n-1 
is the highest power.  In your examples, a = (B-1), r = B, n = N.

     S = (B - 1) * (1 - B^N) / (1 - B)
       = B^N - 1


-- 
Oli

"Rune Allnor" <allnor@tele.ntnu.no> writes:

> Hi all.
>
> In the decimal number system, the largest positive integer
> one can express with N digits is
>
> M_10(N) = 10^0 + 10^1 + 10^2 + ... + 10^(N-1) = 10*10^N -1.
>
> Similarly, the largest positive binary integer one can express
> with N bits is
>
> M_2(N) = 2^0 + 2^1 + 2^2 + ... + 2^(N-1) = 2*2^N -1.
>
> This empirical evidence suggestes to me that the largest
> positive integer that can be expressed with N coefficients(?)
> in a base B number system is
>
> M_B(N) = B^0 + B^1 + B^2 + ... + B^(N-1) = B*B^N -1.
>
> Is this correct? 

Rune,

Yes

> If so, how does one prove it?

The implicit question we need to make explicit is this: Can any number
n be represented in base B, and is this representation unique?

The answer to both questions is yes, and it is established by the
basis representation theorem [numbertheory].

Once that is established, the rest of the proof is trivial.

--Randy

@BOOK{numbertheory,
  title = "Number Theory",
  author = "George E. Andrews",
  publisher = "Dover",
  year = "1971"}
-- 
%  Randy Yates                  % "Maybe one day I'll feel her cold embrace,
%% Fuquay-Varina, NC            %                    and kiss her interface, 
%%% 919-577-9882                %            til then, I'll leave her alone."
%%%% <yates@ieee.org>           %        'Yours Truly, 2095', *Time*, ELO   
http://home.earthlink.net/~yatescr

Randy Yates skrev:
> "Rune Allnor" <allnor@tele.ntnu.no> writes:
>
> > Hi all.
> >
> > In the decimal number system, the largest positive integer
> > one can express with N digits is
> >
> > M_10(N) = 10^0 + 10^1 + 10^2 + ... + 10^(N-1) = 10*10^N -1.
> >
> > Similarly, the largest positive binary integer one can express
> > with N bits is
> >
> > M_2(N) = 2^0 + 2^1 + 2^2 + ... + 2^(N-1) = 2*2^N -1.
> >
> > This empirical evidence suggestes to me that the largest
> > positive integer that can be expressed with N coefficients(?)
> > in a base B number system is
> >
> > M_B(N) = B^0 + B^1 + B^2 + ... + B^(N-1) = B*B^N -1.
> >
> > Is this correct?
>
> Rune,
>
> Yes
>
> > If so, how does one prove it?
>
> The implicit question we need to make explicit is this: Can any number
> n be represented in base B, and is this representation unique?
>
> The answer to both questions is yes, and it is established by the
> basis representation theorem [numbertheory].
>
> Once that is established, the rest of the proof is trivial.
>
> --Randy

...so trivial that I wonder what on earth was the problem with
it in the first place...

Thanks.

Rune

Rune Allnor:
> M_10(N) = 10^0 + 10^1 + 10^2 + ... + 10^(N-1) = 10*10^N -1.
> 
> Similarly, the largest positive binary integer one can express
> with N bits is
> 
> M_2(N) = 2^0 + 2^1 + 2^2 + ... + 2^(N-1) = 2*2^N -1.

N bits can be used to encode 2^N different numbers, characters or
whatever.  Zero is not a positive integer.  So N bits can be used to
express all the positive integer numbers beginning with 1
up to and including 2^N.

Rune Allnor wrote:

> In the decimal number system, the largest positive integer
> one can express with N digits is

> M_10(N) = 10^0 + 10^1 + 10^2 + ... + 10^(N-1) = 10*10^N -1.

> Similarly,

(snip for different bases)

Well, this is true with the assumption that zero and all the
values in between need to be expressed.  Without that constraint,
it could be very different.  With N digits, 10**N different values
can be represented, which can be used for numbers from 0 to 10**N-1,
but they could also be used in other ways.  Consider 10's complement
(or 9's complement) representation for signed numbers.

-- glen

Mirko,

The post started with "In the decimal number system" which I think we
all understand as prettty well defined and excluding your
interpretation.

As Glen alludes to, if you considered encoding with base 10 digits, not
using the decimal number system that we all know and love, simply
considering the numbers to represent symbols, there is no maximum for
the number representable (obviously with not all numbers from 1 up
represented). Once the code is defined, there would be a maximum for
that code, but that maximum could be made any positive integer in the
code definition.  But, clearly this has nothing to do with the intent
of the original posting.

Dirk

Dirk Bell
DSP Consultant


Mirko Liss wrote:
> Rune Allnor:
> > M_10(N) = 10^0 + 10^1 + 10^2 + ... + 10^(N-1) = 10*10^N -1.
> >
> > Similarly, the largest positive binary integer one can express
> > with N bits is
> >
> > M_2(N) = 2^0 + 2^1 + 2^2 + ... + 2^(N-1) = 2*2^N -1.
>
> N bits can be used to encode 2^N different numbers, characters or
> whatever.  Zero is not a positive integer.  So N bits can be used to
> express all the positive integer numbers beginning with 1
> up to and including 2^N.

On 2006-09-30, Rune Allnor <allnor@tele.ntnu.no> wrote:
>
> Similarly, the largest positive binary integer one can express
> with N bits is
>
> M_2(N) = 2^0 + 2^1 + 2^2 + ... + 2^(N-1) = 2*2^N -1.

Actually 2^N -1 (quick test, 2^0-1 = 0 with 0 bits, 2^1-1=1 with 1 bit, ok!)

You'd like Mersenne Primes.

-- 
Ben Jackson AD7GD
<ben@ben.com>
http://www.ben.com/

Ben Jackson skrev:
> On 2006-09-30, Rune Allnor <allnor@tele.ntnu.no> wrote:
> >
> > Similarly, the largest positive binary integer one can express
> > with N bits is
> >
> > M_2(N) = 2^0 + 2^1 + 2^2 + ... + 2^(N-1) = 2*2^N -1.
>
> Actually 2^N -1 (quick test, 2^0-1 = 0 with 0 bits, 2^1-1=1 with 1 bit, ok!)
>
> You'd like Mersenne Primes.

Nope. Number theory always seemed like black art to me,
as a quick glance through the terminology would suggest:

- Perfect number
- Rational number
- Irrational number
- Odd number
- Real number
- Imaginary number

I've never had any inclinations towards number theory, as this
thread ought to demonstrate without any shadow of a doubt...

Rune

"Rune Allnor" <allnor@tele.ntnu.no> wrote in message 
news:1159630498.348257.248400@c28g2000cwb.googlegroups.com...
> Hi all.
>
> In the decimal number system, the largest positive integer
> one can express with N digits is
>
> M_10(N) = 10^0 + 10^1 + 10^2 + ... + 10^(N-1) = 10*10^N -1.
>
> Similarly, the largest positive binary integer one can express
> with N bits is
>
> M_2(N) = 2^0 + 2^1 + 2^2 + ... + 2^(N-1) = 2*2^N -1.
>
> This empirical evidence suggestes to me that the largest
> positive integer that can be expressed with N coefficients(?)
> in a base B number system is
>
> M_B(N) = B^0 + B^1 + B^2 + ... + B^(N-1) = B*B^N -1.
>
> Is this correct? If so, how does one prove it?
>

Rune,

No, it isn't correct because you didn't consider floating point integers in 
those representations.

You postulated:

M_10(N) = 10^0 + 10^1 + 10^2 + ... + 10^(N-1) = 10*10^N -1

One could also postulate:

M_10(L,M) = [10^0 + 10^1 + 10^2 + ... + 10^(L-1)] * [10^0 + 10^1 + 10^2 + 
... + 10^(M-1)]
where L+M=N or something like that.

Then, in this case the largest integer depends on the size of M compared to 
N.  Granted that the granularity increases with increased M but you didn't 
specify anything about granularity of integers ... :-)

Allowing zero in the representation system:

If N=2, the first system gives you
0,1,2,3,4.....10^2-1 = 99

If N=2, L=1 and M=1, the second system gives you
0,1,2,3,4,5,6,7,8,9,10,20 ...100,200,...1000,2000, .... 9*10^9

And, this is just one mapping scheme, I suspect that there is no limit 
depending on the mapping scheme selected.  Of course, they become less 
useful in the *general case* if one does that - just as the floating point 
numbers have variable granularity.  Maybe that's useful and maybe it isn't.

Fred