[math-fun] Short programs for e, etc. (was Re: Factorial base)
rcs@xmission.com wrote:
The only theorem I know of is that a rational number always has a finite representation in factorial base; therefore e is irrational.
How does that follow? The existence of an infinite representation for e in factorial base doesn't prove there isn't also a finite representation.
Back in the day, I was looking through the file of paper tapes in the PDP1 room (this served as the software library), and I came across one labeled simply "e". The handwriting might have been either Eric Jensen or Bill Ackerman. It was only a couple of folds, a few hundred characters.
A few years ago I wrote the following obfuscated c program, which prints a thousand digits of e: void main(){int j,k,l[1002];for(j=1776;j;j--){for(k=0;k<1001;k++){l[k+1]+= 10*(l[k]%j);l[k]/=j;}l[0]++;}for(j=0;j<1001;j++){printf("%d",l[j]);if(!j) printf("%c",46);}printf("\n");} I'm especially proud of operating on an uninitialized array, just to drive readers insane. "It *can't* work, but it does." Can anyone write an equally short c program to print the first thousand decimal digits of any other interesting irrational number, such as pi, phi, zeta(3), cos(x)=x, ln(2), gamma, or sqrt(2)? (An irrational number contrived to have its first thousand digits have some simple pattern (e.g. all 0) is not interesting.) (Okay, nobody knows if gamma is irrational, but it's close enough for me.)
Good point. I left out some important nits: Irrationals have a unique representation in factorial base. Any rational has exactly two representations: one that's finite, and one analogous to the xxx99999... glitch with finite decimal representations. In factorial base, 1 can be represented as 1.000000... or as 0.123456... . (Zero is an exception here, although I suppose you could argue that 0 and -0 are two different representations.) Then you need to check that e-2 = .11111... isn't finite, and also doesn't fit the ....n(n+1)(n+2)... pattern. After adding the proofs for these nits, this proof that e is irrational doesn't look particularly nicer than the standard proof. In fact, the two proof themes look pretty similar. Rich ------- Quoting "Keith F. Lynch" <kfl@KeithLynch.net>:
rcs@xmission.com wrote:
The only theorem I know of is that a rational number always has a finite representation in factorial base; therefore e is irrational.
How does that follow? The existence of an infinite representation for e in factorial base doesn't prove there isn't also a finite representation.
<clip>
On Feb 11, 2015, at 5:14 PM, Keith F. Lynch <kfl@KeithLynch.net> wrote:
rcs@xmission.com wrote:
The only theorem I know of is that a rational number always has a finite representation in factorial base; therefore e is irrational.
How does that follow? The existence of an infinite representation for e in factorial base doesn't prove there isn't also a finite representation.
It follows from the (easy) theorem that for all fractions f in [0,1] the factorial fraction representation is unique. --Dan
That is, using the greedy representation.
On Feb 11, 2015, at 7:47 PM, Daniel Asimov <asimov@msri.org> wrote:
On Feb 11, 2015, at 5:14 PM, Keith F. Lynch <kfl@KeithLynch.net> wrote:
rcs@xmission.com wrote:
The only theorem I know of is that a rational number always has a finite representation in factorial base; therefore e is irrational.
How does that follow? The existence of an infinite representation for e in factorial base doesn't prove there isn't also a finite representation.
It follows from the (easy) theorem that for all fractions f in [0,1] the factorial fraction representation is unique.
* Keith F. Lynch <kfl@KeithLynch.net> [Feb 12. 2015 08:19]:
[...]
Can anyone write an equally short c program to print the first thousand decimal digits of any other interesting irrational number, such as pi, phi, zeta(3), cos(x)=x, ln(2), gamma, or sqrt(2)?
Stanley Rabinowitz, Stan Wagon, A Spigot Algorithm for the Digits of $\pi$, The American Mathematical Monthly, vol.102, no.3, pp.195-203, (March-1995). http://www.mathpropress.com/stan/bibliography/ Best regards, jj
[...]
The following update is also really interesting: Unbounded Spigot Algorithms for the Digits of Pi http://www.cs.ox.ac.uk/jeremy.gibbons/publications/spigot.pdf On Thu, Feb 12, 2015 at 2:35 AM, Joerg Arndt <arndt@jjj.de> wrote:
* Keith F. Lynch <kfl@KeithLynch.net> [Feb 12. 2015 08:19]:
[...]
Can anyone write an equally short c program to print the first thousand decimal digits of any other interesting irrational number, such as pi, phi, zeta(3), cos(x)=x, ln(2), gamma, or sqrt(2)?
Stanley Rabinowitz, Stan Wagon, A Spigot Algorithm for the Digits of $\pi$, The American Mathematical Monthly, vol.102, no.3, pp.195-203, (March-1995).
http://www.mathpropress.com/stan/bibliography/
Best regards, jj
[...]
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Intriguing conjecture therein ... RWG ? I have to confess to finding the Haskell programming language hopelessly slippery, despite having some familiarity with LISP and PROLOG, and notwithstanding the best efforts of the amiably hyper Simon Peyton-Jones' videos on YouTube. Anybody else have this problem? WFL On 2/12/15, Victor Miller <victorsmiller@gmail.com> wrote:
The following update is also really interesting:
Unbounded Spigot Algorithms for the Digits of Pi
http://www.cs.ox.ac.uk/jeremy.gibbons/publications/spigot.pdf
On Thu, Feb 12, 2015 at 2:35 AM, Joerg Arndt <arndt@jjj.de> wrote:
* Keith F. Lynch <kfl@KeithLynch.net> [Feb 12. 2015 08:19]:
[...]
Can anyone write an equally short c program to print the first thousand decimal digits of any other interesting irrational number, such as pi, phi, zeta(3), cos(x)=x, ln(2), gamma, or sqrt(2)?
Stanley Rabinowitz, Stan Wagon, A Spigot Algorithm for the Digits of $\pi$, The American Mathematical Monthly, vol.102, no.3, pp.195-203, (March-1995).
http://www.mathpropress.com/stan/bibliography/
Best regards, jj
[...]
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
I have actually written some working code in Haskell, mostly for solving Project Euler problems and providing programs for OEIS sequences. There *is* something slippery about it. But I can mostly read the code in that paper -- though I couldn't begin to tell you why it works. I'm tempted to write that e algorithm in Haskell; I think it's a one-liner. On Thu, Feb 12, 2015 at 10:17 AM, Fred Lunnon <fred.lunnon@gmail.com> wrote:
Intriguing conjecture therein ... RWG ?
I have to confess to finding the Haskell programming language hopelessly slippery, despite having some familiarity with LISP and PROLOG, and notwithstanding the best efforts of the amiably hyper Simon Peyton-Jones' videos on YouTube.
Anybody else have this problem?
WFL
On 2/12/15, Victor Miller <victorsmiller@gmail.com> wrote:
The following update is also really interesting:
Unbounded Spigot Algorithms for the Digits of Pi
http://www.cs.ox.ac.uk/jeremy.gibbons/publications/spigot.pdf
On Thu, Feb 12, 2015 at 2:35 AM, Joerg Arndt <arndt@jjj.de> wrote:
* Keith F. Lynch <kfl@KeithLynch.net> [Feb 12. 2015 08:19]:
[...]
Can anyone write an equally short c program to print the first thousand decimal digits of any other interesting irrational number, such as pi, phi, zeta(3), cos(x)=x, ln(2), gamma, or sqrt(2)?
Stanley Rabinowitz, Stan Wagon, A Spigot Algorithm for the Digits of $\pi$, The American Mathematical Monthly, vol.102, no.3, pp.195-203, (March-1995).
http://www.mathpropress.com/stan/bibliography/
Best regards, jj
[...]
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
participants (7)
-
Allan Wechsler -
Daniel Asimov -
Fred Lunnon -
Joerg Arndt -
Keith F. Lynch -
rcs＠xmission.com -
Victor Miller