Concrete Mathematics

[G-Brain]

While this isn't a book about Lisp at all, I am thoroughly enjoying it and the fact that mathematics are so easily portable to lisp. Take this problem for example:

How many slices of pizza can a person obtain by making n straight cuts with a pizza knife? or...
What is the maximum number Ln of regions defined by n lines in the plane?

I then tried some small cases on paper, and eventually came to the conclusion that

L0 = 1
Ln = Ln-1 + n for n>0

Because:
With 0 cuts, you have one big slice.
With every next cut you make, you increase the amount of slices by the number of the cut you're making.

0 cuts: 1 big slice
1 cut: 2 slices
2 cuts: 4 slices
3 cuts: 7 slices

The formula

L0 = 1
Ln = Ln-1 + n for n>0

is most easily portable to lisp code as follows:

Code: Select all

(defun L (n)                                                                                                                                                              
    (cond ((= n 0) 1)                                                                                                                                                       
              ((> n 0) (+ (L (1- n)) n))))

I've only just started reading this book, and I'm loving it already. I'll post some more examples later, like the closed form solution to this problem (that is: non-recurrent).

[amos]

The non-recursive form is fairly straightforward (think second difference of the number pattern).

The bigger problem is likely to come from how to draw a line to always generate the maximal number of slices (surely it's much easier to just buy another pizza ).

Amos

[G-Brain]

The non-recursive form is fairly straightforward (think second difference of the number pattern).

This is how I solved it:

Unfolding L3, we get:

L3 = L3
L3 = L2 + 3
L3 = L1 + 2 + 3
L3 = L0 + 1 + 2 + 3
L3 = 1 + 1 + 2 + 3

See the 1 + 2 + 3? How would we get from 3 to 1 + 2 + 3? Triangular numbers:

A 3 row triangular array:

O O O
O O
O

Okay, that's horrible ASCII, but you can see the 3 + 2 + 1. So:

Ln = Sn + 1

(The added 1 is for L0)

Where Sn returns the number of elements in an n-row triangular array, like this:

n(n+1) / 2

Code: Select all

(defun S (n)                                                                                                                                                              
    (/ (* n (1+ n)) 2))

So, the closed form formula:

Ln = 1 + n(n+1) / 2

And in lisp:

Code: Select all

(defun L (n)                                                                                                                                                              
    (1+ (/ (* n (1+ n)) 2)))

I'm liking it

The bigger problem is likely to come from how to draw a line to always generate the maximal number of slices

Ah, the how. That's a good question. I don't have any experience with graphics libraries (excluding CLX for use with stumpWM), but I'll look into it.

[alby]

While this isn't a book about Lisp at all, I am thoroughly enjoying it and the fact that mathematics are so easily portable to lisp.

"Lisp is mathematics, and mathematics is Lisp."

So that's the new propoganda we're going to hear form you Lisp people?

I'm a Ruby guy. Let me give you Lisp "mathematicians" a riddle to solve:

You have a piza. By making 3 straight cuts, divide the piza into 8 parts.

[tayssir]

I'm a Ruby guy.

Why do you identify yourself with some programming language? (Just this week, I used Lisp, Python, Perl and SQL. And regexes, if you count those. Last week you'll find PHP, Javascript and various "little languages." That said, sure, I happen to consider Lisp the only, or one of the few, ideas in computing which I have an affinity with. Otherwise I'd look at computing as a dull way to pay the rent, a glorified form of accounting, in much the same way a high-profile Ruby programmer once did.)

And what does your riddle have to do with the book _Concrete Mathematics_? If I understand correctly, your puzzle requires an operation on the slices where you move them physically. (Or is there a solution I'm missing?)

This is a Lisp forum, and people will pop in to discuss how they like Lisp's applicability to something. For example, I sauntered over here to write some big post about how I really enjoyed a game written in Emacs Lisp, because I was able to "improve" the game as I played it to one which more suited my entertainment. My companion even advised me to make some situation more dangerous and funny, and I realized it would only take 2 or 3 lines more code for that feature.

(Incidentally, given the recent controversy over sexism in the Ruby community, it'd be cool if you were biologically female and identified as a "guy." It's almost meaningless when a male speaks of his traditionally male gender identity, because it's so commonplace, don't you think?)

[alby]

I'm a Ruby guy.

Why do you identify yourself with some programming language?

Those 4 words of mine didn't carry this meaning. I was trying to antagonize the people here, for the sake of the argument, and to show that other programming langugaes aren't less "mathematic".

Otherwise I'd look at computing as a dull way to pay the rent, a glorified form of accounting, in much the same way a

I've been learning Lisp during the past month, that's why I'm here. I'm convinced Lisp has a moral, some beauty, that it can contribute me something, that's why this time I'm persisting in my efforts.

I think I understand the point you make, about "accounting", and I agree.

And what does your riddle have to do with the book _Concrete Mathematics_?

Nothing.

Just like Lisp has nothing to do with this book.

The original poster gave us some mathematical formula ("L(1- n) + n"), and used this ruse to extol Lisp. However, the real challenge is to *prove*, mathematically, this forula. Lisp can't do this. So what gives?

Since I noticed this blatant disrespect for Math, logic, and the readers' intelligence, I felt compelled to reply.

If I understand correctly, your puzzle requires an operation on the slices where you move them physically. (Or is there a solution I'm missing?)

The solution is to notice that the pizza is 3D --a cylinder-- and to cut it horizontally once.

(Incidentally, given the recent controversy over sexism in the Ruby community, it'd be cool if you were biologically female and identified as a "guy." It's almost meaningless when a male speaks of his traditionally male gender identity, because it's so commonplace, don't you think?)

I was not speaking of my "traditionally male gender identity". I was just saying that I'm a Ruby guy. I didn't mean to say "I'm a Ruby guy, guys rulz!!!11, I'm proud to be a guy!! girls should go to the kitchen". No. I was just saying I'm a Ruby guy.

It's almost meaningless when a male speaks of his traditionally male gender identity, because it's so commonplace, don't you think?)

So what's your solution? To rewrite "I'm a Ruby guy" as "I'm using Ruby"? First, it doens't carry the same meaning; Second, the fault isn't in the "guy" word but in your perceiving my innocent phrase as sexisim.

[alby]

(I hope I didn't sound rude, or belligerent. I apologize if it seemed, or seems, so.)

[tayssir]

(I don't want to accuse you of sexism; I'm personally no doubt sexist, for being raised in a culture where traditional gender identity is very important. And I hope the original poster didn't say anything that could be construed as "propoganda we're going to hear form you Lisp people.")

Historically, there's many aspects of mathematics. Proof-based mathematics isn't the only form. Davis and Hersh argued: "The mathematics of Egypt, of Babylon, and of the ancient Orient was all of the algorithmic type. Dialectical mathematics -- strictly logical, deductive mathematics -- originated with the Greeks. But it did not displace the algorithmic." And the physicist Feynman argued that, "In physics, we need the Babylonian method, and not the Euclidian or Greek method."

That said, there's some attributes of Lisp that might be of use when you're playing with math. So for example, mathematicians (and anyone else) have fluid notations. Well, Lisp's notation is handy in this respect -- it's fairly abstract and you can manipulate it with the same data-handling muscles you've already trained. Not to mention that you can play with the reader, for character-level syntax. (Other programming languages usually offer less moldable notations, for good or bad.)

Not to mention that Common Lisp has relatively nice support for numbers. So you're not too worried about integer overflow, and you have rationals and complex numbers...

There's proof systems in Lisp, though I'm not familiar with them. My vague impression is that computers are still currently more help aiding a human proof-discoverer, then discovering the proofs themselves.

About the riddle, a pizza is not a mathematical object; it is something for which a horizontal cut is usually difficult to perform, which is why it was viewed from a 2D perspective. Not to mention a geometry where there's no weird curvature or something, even though pizzas can of course be curved, leading to more (and simpler to carry out) solutions. But it's a cool riddle, if you phrase it carefully enough, which you did. (So for example, you didn't refer to a pizza "slice," but rather "parts." I assumed you were being as informal with your language as you were with spelling, which was no doubt a mistake on my part.)

(Ironically, in his essay, Feynman discussed the exasperation that physicist has when mathematicians talk of many dimensions, when the physicist just wants the special case of 3... until it turns out that maybe 4 was interesting too. Maybe I'm currently stuck in Babylon, too?)

Lest we look down on those practicing the Babylonian style, I've heard the argument (from Connes, Gowers, Smolin or someone; can't remember) that physicists have often been responsible for trailblazing mathematical fields due in part to their greater willingness to be very loose and intuitive with their mathematical reasoning, as compared to mathematicians.

[tayssir]

(I hope I didn't sound rude, or belligerent. I apologize if it seemed, or seems, so.)

Of course, I too apologize if I was rude... (I'm on a small vacation now, so I'm probably in a weird mood. )

[alby]

(Sorry for not replying earlier: I wasn't on-line.)

About the riddle, a pizza is not a mathematical object; it is something for which a horizontal cut is usually difficult to perform, which is why it was viewed from a 2D perspective.

You got me here. The original wording speaks of a cake, which is much thicker. I hoped no one will notice this glitch in my modified riddle

===

As for math: I'm not (yet?) familiar with this world, so I can't fully understand what you're saying there. Lately my interest in math has arisen (In fact, that's also why my interest in Lisp was re-kindled; because some CAS systems are written in it). I'm now reading a math history book, "Unknown Quantity".

Davis and Hersh argued: "The mathematics of Egypt, of [...]

Oh, I see that page 61 of that book says "[...] the age of twenty-five or thirty. If little has been accomplished by then, little will ever be accomplished." I hope I'm not too old to re-learn math

Tayssir, are you a math hobbiest?