The next exercise

The next exercise

[Michael Heerdegen]

Hello,

my exercise for today is something I stumbled across a few days ago but
that is very nice: Answer with only using Emacs (or maybe your school
knowledge?):

The first three decimal digits (from the left) of 1001^1000 - i.e. one
thousand and one to the one thousand's power,

  1001*1001*...*1001
  \________________/
          ^
     1000 factors

are of course:

 (a) 2 7 1, the first three digits of Euler's number e

 (b) 3 1 4, the first three digits of the mathematical constant pi

 (c) 1 0 0, or

 (d) none of these

What's your choice?  How would you solve this using Emacs (or maybe even
without)?


Michael.

Re: The next exercise

[tomas]

[-- Attachment #1: Type: text/plain, Size: 1046 bytes --]

On Fri, Dec 09, 2022 at 08:09:49PM +0100, Michael Heerdegen wrote:
> Hello,
> 
> my exercise for today is something I stumbled across a few days ago but
> that is very nice: Answer with only using Emacs (or maybe your school
> knowledge?):
> 
> The first three decimal digits (from the left) of 1001^1000 - i.e. one
> thousand and one to the one thousand's power,
> 
>   1001*1001*...*1001
>   \________________/
>           ^
>      1000 factors
> 
> are of course:
> 
>  (a) 2 7 1, the first three digits of Euler's number e
> 
>  (b) 3 1 4, the first three digits of the mathematical constant pi
> 
>  (c) 1 0 0, or
> 
>  (d) none of these
> 
> What's your choice?  How would you solve this using Emacs (or maybe even
> without)?

My choice was school maths. But I cheated, because I
studied physics later, so those maths were kept warm
for some longer while ;-)

To test my conjecture (old physicist, after all), I
resorted to guile, then to Emacs: by golly, that gmp
thingy is... fast :)

Cheers
-- 
t

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 195 bytes --]

Re: The next exercise

[Michael Heerdegen]

<tomas@tuxteam.de> writes:

> My choice was school maths. But I cheated, because I
> studied physics later, so those maths were kept warm
> for some longer while ;-)

Ok, I owe the mathematical background, at least a bit.  The general
background is that

  /n + 1\ n
  |- - -|   --> e
  \  n  /

and if you set n := 1000 you get that 1001^1000 is approximately
e*1000^1000 (*).

Regards,

Michael.



(*) But is this enough to be sure that the first three digits are those
of e?  To be really sure you either check with some sort of calculator
which can calculate such large numbers - there are several ways in Emacs
as we saw!

Or you remember how e can be introduced: with

         /    1\ n               /   1\ n+1
  a_n := |1 + -|   and   b_n := |1 + -|  
         \    n/                 \   n/  

you got that a_n is strictly monotonously increasing, b_n strictly
monotonously decreasing, and b_n - a_n --> 0, so they both converge and
the limit is called e.  From a_n < e < b_n you then also see that

  e    b_n   n+1       b_n   b_n   n+1
 --- < --- = ---  and  --- < --- = ---
 a_n   a_n    n         e    a_n    n

and from that you can even conclude how good the approximation is.  For
n=1000 the exact value must fulfill

   1
 ----- *e*1000^1000 < 1001^1000 < 1.001*e*1000^1000
 1.001

which is good enough for three digits 271 from e.

This is a quite surprising thing, I mean, here are no functions and
derivatives, no fractions, no combinatorics etc involved.  Still,
(1+10^n)^(10^n), a simple product of natural numbers, always starts with
the first n digits of e for every n.  More and more the larger n gets.

Ok - I really apologize for the little mathematical excursion.  Have a
look at M-x calc (it's built in) if you haven't yet.  It's worth it!

Re: The next exercise

[Emanuel Berg]

Michael Heerdegen wrote:

> Ok - I really apologize for the little
> mathematical excursion.

On the contrary ...

-- 
underground experts united
https://dataswamp.org/~incal

Re: The next exercise

[tomas]

[-- Attachment #1: Type: text/plain, Size: 1010 bytes --]

On Fri, Dec 09, 2022 at 09:38:25PM +0100, Michael Heerdegen wrote:
> <tomas@tuxteam.de> writes:
> 
> > My choice was school maths [...]

[...]

> Or you remember how e can be introduced: with
> 
>          /    1\ n               /   1\ n+1
>   a_n := |1 + -|   and   b_n := |1 + -|  
>          \    n/                 \   n/  

FWIW, I started with the binomial formula,

  (1000 + 1)^1000 = 1000^1000 + (n-over-1) * 1000^999 + ...

Now n-over-1 is 1000, so we already have a 2 at the left
(more to come, of course :) Next (n-over-2) is 1000*999/1*2
(so roughly 1000*1000/2, that adds 0.5 to the most significant,
that makes 25...; Next 1000^3/6, so we are at 2666...

The denominator grows quickly (a tad more than an exponential),
so things are bound to converge quickly; besides, I over-estimated
things by setting 99x to 1000.

That already started looking a lot like e. Then I remembered
that limit I quoted from you above.

Then I asked Guile and Emacs.

Cheers
-- 
t

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 195 bytes --]

Re: The next exercise

[Emanuel Berg]

tomas wrote:

>> Or you remember how e can be introduced: with
>> 
>>          /    1\ n              /    1\ n+1
>>   a_n := |1 + -|   and   b_n := |1 + -|  
>>          \    n/                \    n/  
>
> FWIW, I started with the binomial formula,
>
>   (1000 + 1)^1000 = 1000^1000 + (n-over-1) * 1000^999 + ...

Is this the new exercise, to estimate e?

What does it mean to introduce something? I'm not familiar
with :=, I guess that's introduction then.

But I've seen that somewhere, Pascal?

Right, it the assignment operator so then I take it
introduction just means to say something is said to denote
something else.

I use to thing the Pascal := had a point since then you could
use = as in math (and don't double down with == for equals)
but I've never given it any more thought since I got hooked on
Lisp and now I realize why ...

-- 
underground experts united
https://dataswamp.org/~incal

Re: The next exercise

[Emanuel Berg]

tomas wrote:

> To test my conjecture (old physicist, after all), I resorted
> to guile, then to Emacs: by golly, that gmp thingy is...
> fast :)

Faster than a speeding bullet!

GMP 1991 GNU Multiple Precision Arithmetic Library

-- 
underground experts united
https://dataswamp.org/~incal

Re: The next exercise

[Gregory Heytings]

>
> Hello,
>
> my exercise for today is something I stumbled across a few days ago but 
> that is very nice: Answer with only using Emacs (or maybe your school 
> knowledge?):
>
> The first three decimal digits (from the left) of 1001^1000 - i.e. one 
> thousand and one to the one thousand's power,
>
>  1001*1001*...*1001
>  \________________/
>          ^
>     1000 factors
>
> are of course:
>
> (a) 2 7 1, the first three digits of Euler's number e
>
> (b) 3 1 4, the first three digits of the mathematical constant pi
>
> (c) 1 0 0, or
>
> (d) none of these
>
> What's your choice?  How would you solve this using Emacs (or maybe even 
> without)?
>

M-: (substring (number-to-string (expt 1001 1000)) 0 3) RET

"271"

Re: The next exercise

[Michael Heerdegen]

Gregory Heytings <gregory@heytings.org> writes:

> M-: (substring (number-to-string (expt 1001 1000)) 0 3) RET
>
> "271"

Yes - correct!

My expectation was that someone would try Emacs Calc.  Because it can
compute the number exactly - all digits.

Michael.

Re: The next exercise

[tomas]

[-- Attachment #1: Type: text/plain, Size: 690 bytes --]

On Fri, Dec 09, 2022 at 08:58:32PM +0100, Michael Heerdegen wrote:
> Gregory Heytings <gregory@heytings.org> writes:
> 
> > M-: (substring (number-to-string (expt 1001 1000)) 0 3) RET
> >
> > "271"
> 
> Yes - correct!
> 
> My expectation was that someone would try Emacs Calc.  Because it can
> compute the number exactly - all digits.

These days, Emacs Lisp can, too (that was my mulling about
the gmp thingy ;-)

So...

  (let ((n 1) (exp 1000))
    (while (> exp 0)
      (setq n (* n 1001) exp (1- exp)))
    n)

also gives the exact number (guile is a /dash/ faster, but
Emacs Lisp ain't bad, either ;-)

AFAIK, Emacs uses libgmp for that.

Cheers
-- 
t

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 195 bytes --]

Re: The next exercise

[Gregory Heytings]

>> M-: (substring (number-to-string (expt 1001 1000)) 0 3) RET
>>
>> "271"
>
> Yes - correct!
>
> My expectation was that someone would try Emacs Calc.  Because it can 
> compute the number exactly - all digits.
>

You asked for the first three digits, but of course expt also computes the 
number exactly:

M-: (expt 1001 1000) RET

But indeed:

M-x calc RET 1001 RET 1000 RET ^

Re: The next exercise

[Michael Heerdegen]

Gregory Heytings <gregory@heytings.org> writes:

> M-: (expt 1001 1000) RET

Wow, Tomas and Gregory, thanks for the hint - I had forgotten that even
"normal" Emacs Lisp can do it exactly.  Wonderful.

(substring (number-to-string (expt 10001 10000)) 0 4) is too much,
however (Arithmetic overflow error).

Michael.

Re: The next exercise

[Emanuel Berg]

Michael Heerdegen wrote:

>> M-: (expt 1001 1000) RET
>
> Wow, Tomas and Gregory, thanks for the hint - I had
> forgotten that even "normal" Emacs Lisp can do it
> exactly. Wonderful.
>
> (substring (number-to-string (expt 10001 10000)) 0 4) is too
> much, however (Arithmetic overflow error).

What is this then

(defalias '** #'expt)

(1- (** 2 (* 8 (** (** 2 10) 4))))

It's an arithmetic overflow error!

But what does it express?

Hint: Start with (** 2 10) ...

-- 
underground experts united
https://dataswamp.org/~incal

Re: The next exercise

[Michael Heerdegen]

Emanuel Berg <incal@dataswamp.org> writes:

> (1- (** 2 (* 8 (** (** 2 10) 4))))
>
> It's an arithmetic overflow error!
>
> But what does it express?
>
> Hint: Start with (** 2 10) ...

2^2^43 - 1, right?  What's it?  It's too large to be the largest known
prime number, or I calculated wrong.  I don't know.  Tell us.

Michael.

Re: The next exercise

[Emanuel Berg]

Michael Heerdegen wrote:

>> (1- (** 2 (* 8 (** (** 2 10) 4))))
>>
>> It's an arithmetic overflow error!
>>
>> But what does it express?
>>
>> Hint: Start with (** 2 10) ...
>
> 2^2^43 - 1, right? What's it? It's too large to be the
> largest known prime number, or I calculated wrong. I don't
> know. Tell us.

Oh, no!

Hint 1: Start with (** 2 10) which is 1024.
Hint 2: Think computers, not math ...

-- 
underground experts united
https://dataswamp.org/~incal

Re: The next exercise

[Michael Heerdegen]

Emanuel Berg <incal@dataswamp.org> writes:

> Hint 1: Start with (** 2 10) which is 1024.
> Hint 2: Think computers, not math ...

Hint 1 still looks like math to me.

Sorry, I'm not able to solve it.  Seems I don't know enough about
computers, or I'm too much a mathematician.

Michael.

Re: The next exercise

[Michael Heerdegen]

Emanuel Berg <incal@dataswamp.org> writes:

> > 2^2^43 - 1, right? What's it? It's too large to be the
> > largest known prime number, or I calculated wrong. I don't
> > know. Tell us.

At least I know now it's not a prime, since all integers of the form
2^2^n - 1 are divisible by 5.

> Hint 1: Start with (** 2 10) which is 1024.
> Hint 2: Think computers, not math ...

Is it some kind of Turing test?  No, I'm not a computer, I swear.

Hmm, what might I think about it as a computer?  2^2^43-1 is binary

  1 1 .....................1
  \_______________________/
   8 796 093 022 208 digits 1

so as a computer I would no doubt think, oh man, look at these
8 796 093 022 208 digits "1", I wounder what this is about - is it a
prime?  But I already answered that.  Hmm.

Still too mathematical maybe.  Wait - it's the largest number a
calculator using 8 796 093 022 208 binary digits can express.

The horizontal checksum of this binary number is 2^43 - this is not some
kind of "the answer is 42" joke?

I'm not a good computer.  I would obviously fail the inverse Turing test
(as a human pretending to be a computer).


Michael.

Re: The next exercise

[Michael Heerdegen]

Michael Heerdegen <michael_heerdegen@web.de> writes:

> At least I know now it's not a prime, since all integers of the form
> 2^2^n - 1 are divisible by 5.

I meant for n>=2 of course (n=1 is the only exception).

Michael.

Re: The next exercise

[Emanuel Berg]

Michael Heerdegen wrote:

> Still too mathematical maybe. Wait - it's the largest number
> a calculator using 8 796 093 022 208 binary digits
> can express.

That's right! \o/

It is the number you get from one terabyte of data - or
technically 1 TiB - with all the bits set, i.e.

  1111111111111 ... [just kidding]

Here is the entire list, you deserve it:

-------------------------------------------------------------------------------
  BINARY UNITS                                            incal@dataswamp.org
-------------------------------------------------------------------------------




        name               bytes   unit   max value
-------------------------------------------------------------------------------
   char/byte                   1          (1- (** 2 (* 8     (** 2  0)   )))
        word                   2          (1- (** 2 (* 8     (** 2  1)   )))
  doubleword                   4          (1- (** 2 (* 8     (** 2  2)   )))
    quadword                   8          (1- (** 2 (* 8     (** 2  3)   )))
   paragraph                  16          (1- (** 2 (* 8     (** 2  4)   )))
    kilobyte               1 024   KiB    (1- (** 2 (* 8 (** (** 2 10) 1))))
    megabyte           1 048 576   MiB    (1- (** 2 (* 8 (** (** 2 10) 2))))
    gigabyte       1 073 741 824   GiB    (1- (** 2 (* 8 (** (** 2 10) 3))))
    terabyte   1 099 511 627 776   TiB    (1- (** 2 (* 8 (** (** 2 10) 4))))
-------------------------------------------------------------------------------
                                                                 ^^^^
                                                                 1024



-------------------------------------------------------------------------------
  https://dataswamp.org/~incal/data/BINARY-UNITS                   2022-12-01
-------------------------------------------------------------------------------

-- 
underground experts united
https://dataswamp.org/~incal

Re: The next exercise

[Michael Heerdegen]

Emanuel Berg <incal@dataswamp.org> writes:

> Michael Heerdegen wrote:
>
> > Still too mathematical maybe. Wait - it's the largest number
> > a calculator using 8 796 093 022 208 binary digits
> > can express.
>
> That's right! \o/
>
> It is the number you get from one terabyte of data - or
> technically 1 TiB - with all the bits set, i.e.
>
>   1111111111111 ... [just kidding]

Ah - very nice that you made my answer count.

If I ever need to save this number to disk, I know now that it's
possible ;-)

Michael.

Re: The next exercise

[Emanuel Berg]

Michael Heerdegen wrote:

>>> Still too mathematical maybe. Wait - it's the largest number
>>> a calculator using 8 796 093 022 208 binary digits
>>> can express.
>>
>> That's right! \o/
>>
>> It is the number you get from one terabyte of data - or
>> technically 1 TiB - with all the bits set, i.e.
>>
>>   1111111111111 ... [just kidding]
>
> Ah - very nice that you made my answer count.
>
> If I ever need to save this number to disk, I know now that
> it's possible ;-)

I'm sorry you had to say that last thing because ... actually
that's the (b) question part, to implement it in practice.

Because otherwise, what signal do we send to the Emacs and Elisp
community? That only theory counts? And we can't have
that ... obviously.

:)

-- 
underground experts united
https://dataswamp.org/~incal

Re: The next exercise

[Andy Moreton]

On Fri 09 Dec 2022, Michael Heerdegen wrote:

> Gregory Heytings <gregory@heytings.org> writes:
>
>> M-: (expt 1001 1000) RET
>
> Wow, Tomas and Gregory, thanks for the hint - I had forgotten that even
> "normal" Emacs Lisp can do it exactly.  Wonderful.
>
> (substring (number-to-string (expt 10001 10000)) 0 4) is too much,
> however (Arithmetic overflow error).
>
> Michael.

Emacs can still do that:

(let ((integer-width 200000))
     (substring (number-to-string (expt 10001 10000)) 0 4))
=> "2718"

AndyM

Re: The next exercise

[Michael Heerdegen]

Andy Moreton <andrewjmoreton@gmail.com> writes:

> Emacs can still do that:
>
> (let ((integer-width 200000))
>      (substring (number-to-string (expt 10001 10000)) 0 4))
> => "2718"

Indeed:

(let ((integer-width 20000000))
     (substring (number-to-string (expt 1000001 1000000)) 0 6))
==> 271828

6 digits from e.  But there it starts to take some time.

Michael.

Re: The next exercise

[Emanuel Berg]

Michael Heerdegen wrote:

>> Emacs can still do that:
>>
>> (let ((integer-width 200000))
>>      (substring (number-to-string (expt 10001 10000)) 0 4))
>> => "2718"
>
> Indeed:
>
> (let ((integer-width 20000000))
>      (substring (number-to-string (expt 1000001 1000000)) 0 6))
> ==> 271828
>
> 6 digits from e.  But there it starts to take some time.

So how big an integer can you put into `integer-width'?

-- 
underground experts united
https://dataswamp.org/~incal

Re: The next exercise

[Emanuel Berg]

Gregory Heytings wrote:

> M-: (expt 1001 1000) RET

Make it look cooler with

  (defalias '** #'expt)

as in

  (** 1001 1000)

also

  (defalias 'ceil #'ceiling)

etc

KISS = Keep it Simple Software (or "Keep it short, stupid")

Margaret Thatcher's approach to speeches ...

-- 
underground experts united
https://dataswamp.org/~incal

Re: The next exercise

[Emanuel Berg]

Michael Heerdegen wrote:

> The first three decimal digits (from the left) of 1001^1000
> - i.e. one thousand and one to the one thousand's power,
>
>   1001*1001*...*1001
>   \________________/
>           ^
>      1000 factors
>
> are of course:
>
>  (a) 2 7 1, the first three digits of Euler's number e

I suspect some trap here but okay then, I'll bite

(substring (format "%d" (expt 1001 1000)) 0 3)

which is 271

-- 
underground experts united
https://dataswamp.org/~incal

Re: The next exercise

[Michael Heerdegen]

Emanuel Berg <incal@dataswamp.org> writes:

> I suspect some trap here but okay then

I hope I'm not that bad.

> I'll bite
>
> (substring (format "%d" (expt 1001 1000)) 0 3)
>
> which is 271

Indeed!

Seems a lot of people already know that `expt' and even `format' alone
are totally able to handle the task.

Michael.