Wikipedia:Reference desk/Archives/Mathematics/2008 June 12

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

June 12

Square Footage Conversion

How do I convert the following inches to square footage...

   4x23,  
   
   18x14,  

   18x10,  

   16x22  —Preceding unsigned comment added by 65.81.135.40 (talk) 00:31, 12 June 2008 (UTC) 

Those are rectangles, the area of a rectangle is base times height. To get the area in square feet, you need to convert the lengths of the sides into feet. There are 12 inches in a foot, so you divide by 12. You can then just multiply the numbers together to get the area. The first one, for example, will be ${\frac {4}{12}}\times {\frac {23}{12}}=0.63{\dot {8}}\,\mathrm {ft} ^{2}$. --Tango (talk) 00:44, 12 June 2008 (UTC)

Or, alternatively, you can multiply the inches and then divide the product by 144, since there are 12×12, or 144, square inches in a square foot. StuRat (talk) 13:30, 13 June 2008 (UTC)

Yes, that's clearly equivalent. I felt dividing by 12 twice was more intuitive and easier to understand. --Tango (talk) 15:06, 13 June 2008 (UTC)

Farkas' lemma

Okay, so I have a basic linear programming course this summer (not my field). I’ve understood most of it so far, but I with the most recent material, farkas' lemma, I think I missed something because I don’t see where the results are coming from.

In particular, my difficulty is when given a linear program in constructing the second linear system that farkas' lemma gives. But not by modifying the first system to be in the correct form to apply the lemma. Rather there’s some relationship between the two systems that I’m missing.

More specifically, given a linear program, at the end of phase 1 (in the two phase method), the reduced costs are significant to the problem implied by farkas' lemma for some reason (a solution even, I think but don’t know why), and for some reason have to be of a specific sign.

So for instance say I want to minimize $2x_{1}+3x_{2}$ over the region $x_{1}+x_{2}\geq 1,{\mbox{and}}-3x_{1}-3x_{2}\geq 2,x_{1}\geq 0,x_{2}\geq 0$ which by construction I made infeasible. Then applying the lemma I get the constraints $y_{1}-3y_{2}\leq 0,y_{1}-3y_{2}\leq 0,y_{1}\leq 0,y_{2}\leq 0,y_{1}+2y_{2}>0$. I don’t understand how to get that from the first problem conceptually, though.

Also, is this related to duality at all? I don’t think it is because a linear program has a solution iff it’s dual does, but here we’re finding problems which have a solution iff the other does not.

Any help or links to resources appreciated. GromXXVII (talk) 00:48, 12 June 2008 (UTC)

Try considering whether there is an improving feasible direction from the current solution or not, ie. whether there is a $d$ such that $x'=x+\alpha d$ is feasible for small enough $\alpha$ and $c^{T}x<c^{T}x'$ where $c$ is the vector of costs and $x$ is the current solution. The connection to Farkas' lemma should become obvious. 84.239.133.86 (talk) 16:35, 16 June 2008 (UTC)

Simple Divisibility Proof

Hello, this is from a Precalculus book (teaching about induction) so it must be obvious and I am just not seeing it. The problem is, show that 8 divides $9^{n}-1$ where n is a natural number. I wrote $9^{n}-1=(3^{n}+1)(3^{n}-1)$ and got that 4 divides $9^{n}-1$ but I can't get the last factor of 2 to show divisibility by 2. The next problem in the book is to show that 7 divides $3^{2n+1}+2^{n+2}$ for n=0,1,2,3,.... On this one, I don't even know how to begin. Any help will be appreciated.69.232.109.213 (talk) 01:52, 12 June 2008 (UTC)

Hint, $x^{n}-1=(x-1)(x^{n-1}+x^{n-2}+...+1)$, Dragons flight (talk) 02:07, 12 June 2008 (UTC)

Hint 2, $3^{2n+1}+2^{n+2}=3*9^{n}+4*2^{n}$ and 9 = 2 mod 7. Dragons flight (talk) 02:19, 12 June 2008 (UTC)

Since you are trying to create a proof by induction, could you explain what goes wrong when you assume that 8 divides 9ⁿ – 1 and try to use that fact to prove that 8 divides 9^{n + 1} – 1? You should also make sure to check your basis step, namely, that 8 divides 9⁰ – 1. Michael Slone (talk) 02:52, 12 June 2008 (UTC)

Use the fact that $x-y$ divides $x^{n}-y^{n}$ for positive $n$. I think this is a bit more straightforward. Someletters<Talk> 15:05, 12 June 2008 (UTC)

Thanks everyone for the quick reply. I got them. For the first one, forming the difference works.69.232.109.213 (talk) 03:18, 12 June 2008 (UTC)

I'd like to note that the first approach using $9^{n}-1=(3^{n}+1)(3^{n}-1)$ should also work.

$3^{n}\equiv 1{\pmod {2}}$

$3^{n}\equiv {\begin{cases}1,&{\mbox{if }}n{\mbox{ is even}}\\3,&{\mbox{if }}n{\mbox{ is odd}}\end{cases}}{\pmod {4}}$

so one of $3^{n}+1$ or $3^{n}-1$ divides 4 and the other divides 2. --Prestidigitator (talk) 05:44, 12 June 2008 (UTC)

A excellent offshoot of all the above is to simply express the number concerned in base 9. You'll see it immediately then. 203.221.127.19 (talk) 15:16, 13 June 2008 (UTC)

1020

Which numbers are divisible to 1020? —Preceding unsigned comment added by 76.64.52.208 (talk) 02:15, 12 June 2008 (UTC)

After calculating with a little program, here are the results: 1,2,3,4,5,6,10,12,15,17,20,30,34,51,60,68,85,102,170,204,255,340,510 After knowing the answer, may you kindly explain what is it for?--Lowerlowerhk (talk) 03:41, 12 June 2008 (UTC)

If you include 1 in your answer, you should probably also mention 1020 itself. --CiaPan (talk) 08:57, 12 June 2008 (UTC)

I'd normally show you the technique without giving away the answer, but, since the answer has already be given, I can show you both:

Start by finding the prime factors. First, is it divisible by 2 ? Yes, so that gives us factors of 2 and 510. Is 510 divisible by 2 ? Yes, so that gives us factors of 2 and 255. Since 255 isn't divisible by 2, but is obviously divisible by 5, let's do that next, to get 5 and 51. 51 isn't divisible by 2, but is by 3, to give us factors of 3 and 17. 17 is prime. So, we have the following prime factors:

2×2×3×5×17

Now, you can combine them in every possible way to get all the factors:

Factor 1    Factor 2
---------   --------------
        2   2×3×5×17 = 510
        3   2×2×5×17 = 340
        5   2×2×3×17 = 204
       17   2×2×3×5  =  60
2×2  =  4   3×5×17   = 255
2×3  =  6   2×5×17   = 170
2×5  = 10   2×3×17   = 102
2×17 = 34   2×3×5    =  30
3×5  = 15   2×2×17   =  68
3×17 = 51   2×2×5    =  20
5×17 = 85   2×2×3    =  12

So, not only can you solve this without a computer, you don't even need a calculator. StuRat (talk) 13:22, 13 June 2008 (UTC)

Some Algebra Simplification

Thanks for the quick help on the last one guys. Here is another problem. The book says to find a simplifying expression for the product

$\left(1-{\frac {1}{2}}\right)\left(1-{\frac {1}{3}}\right)\cdots \left(1-{\frac {1}{n}}\right)$

$\left(1-{\frac {1}{2^{2}}}\right)\left(1-{\frac {1}{3^{2}}}\right)\cdots \left(1-{\frac {1}{n^{2}}}\right).$

Both are indeed finite products. And then the book says to verify its validity for all integers n greater than or equal to 2. Now, I already know the answers for both of them. The first one simplifies to 1/n and the second one simplifies to (n+1)/(2n) and once you know this, it is a piece of cake to prove their validity by induction. My question is, if I didn't already know the answers, how would an algebra student go about finding these simple expressions in the first place for both of them? Is there a quick simple derivation that I can't see?69.232.109.213 (talk) 03:33, 12 June 2008 (UTC)

Probably by writing out the first few terms and then guessing the pattern. This is easy for the first one, probably less so for the second. Dragons flight (talk) 03:48, 12 June 2008 (UTC)

Well, taking the first expression:

$\left(1-{\frac {1}{2}}\right)\left(1-{\frac {1}{3}}\right)\cdots \left(1-{\frac {1}{n}}\right)$

$={\tfrac {1}{2}}\left[2\cdot \left(1-{\frac {1}{2}}\right)\right]\left(1-{\frac {1}{3}}\right)\cdots \left(1-{\frac {1}{n}}\right)$

$={\tfrac {1}{2}}\left(2-1\right)\left(1-{\frac {1}{3}}\right)\cdots \left(1-{\frac {1}{n}}\right)$

$={\tfrac {1}{2}}1\left(1-{\frac {1}{3}}\right)\cdots \left(1-{\frac {1}{n}}\right)$

Continuing with 3, 4, you should be able to see a pattern. Then you can use mathematical induction to prove what you can already see intuitively (if really necessary; this seems trivial enough not to need such a proof, but then you never know with mathematicians). I believe that should also give you enough to get started on the second example. --Prestidigitator (talk) 04:11, 12 June 2008 (UTC)

For the first product note that each term is $\left(1-{\tfrac {1}{k}}\right)={\tfrac {k-1}{k}}$ so the every term's denominator cancels the next term's numerator. Conlcusion: the whole product internally cancels except the first term's numerator and the last term's denominator, which makes the result of ${\tfrac {2-1}{n}}={\tfrac {1}{n}}.$

For the second product use the well known identity: $a^{2}-b^{2}=(a-b)(a+b)$ to rewrite each term as $\left(1-{\tfrac {1}{k^{2}}}\right)={\tfrac {k^{2}-1}{k^{2}}}={\tfrac {(k-1)\times (k+1)}{k\times k}}$ and similary note how terms cancel between consecutive fractions. All that remains is ${\tfrac {k-1}{k}}$ from the first fraction (k=2) and ${\tfrac {k+1}{k}}$ from the last one (k=n), which makes the result of ${\tfrac {(2-1)}{2}}\times {\tfrac {(n+1)}{n}}={\tfrac {n+1}{2n}}$. --CiaPan (talk) 08:48, 12 June 2008 (UTC)

fuzzy hyperplanes

How can I write fuzzy heperplanes? —Preceding unsigned comment added by 80.191.210.252 (talk) 10:50, 12 June 2008 (UTC)

Matrix notation

Is there a convenient standard shorthand for sticking several vectors together into a matrix (e.g., the points (1, 0) and (0, 1) into the identity matrix)? Right now I'm using square braces, except that they're on the top and bottom, not on the sides; this works well, but I've had to explain it to everyone who's seen it, which I'd not have to with a standard notation. —Preceding unsigned comment added by 79.78.47.229 (talk) 13:35, 12 June 2008 (UTC)

$\left(\mathbf {v_{1}} |\mathbf {v_{2}} |\mathbf {v_{3}} \right)$ is a fairly standard notation, I believe. --Tango (talk) 14:14, 12 June 2008 (UTC)

Square of squares

Suppose a₁ ... a_n are n square numbers, each with n digits. We write a₁ ... a_n into an nxn square, one number per row, one digit per cell. Then we read down the columns. If each column is also an n digit square number then call this a "square of squares". For example (121, 256, 169) is a square of squares, because the columns also read (121, 256, 169).

I have (I think) found all 2x2, 3x3 and 4x4 squares of squares - mainly by brute force search. Thing is, every one I have found so far is symmetric, like (121, 256, 169) above. But nothing in the problem statement forces symmetry, and I can see no obvious reason why an asymmetric square of squares should be impossible. I did a Google search, which turned up a lot of references to magic squares of squares, which are interesting, but not what I am looking for.

Does anyone know whether an asymmetric square of squares exists for some n > 4 ? Or is there a proof that an asymmetric square of squares is impossible ? Gandalf61 (talk) 13:39, 12 June 2008 (UTC)

Here's a counterexample which uses leading zeros. Rows: 00 and 49; columns: 04 and 09. I will speculate wildly, and guess that there will also be counterexamples without leading zeros. Eric. 144.32.89.104 (talk) 14:51, 12 June 2008 (UTC)

I think saying a number has "n digits" implicitly assumes there are no leading zeros, otherwise it's pretty meaningless. I can write a computer program to search for them, but for n>4, it's going to be rather slow by pure brute force (n=4 will be bad enough, n<4 is easily doable, though). I might be able to optimise it a little, but I'm not sure... --Tango (talk) 16:18, 12 June 2008 (UTC)

Yes, true, that wasn't the sort of counterexample Gandalf61 was looking for. But I imagine that if there were any good mathematical reason for asymmetric squares to be impossible without leading zeros, then it would probably also apply to asymmetric squares with leading zeros; so, to me, the existence of a counterexample with leading zeros suggests that ones could be found without leading zeros. Of course, I could just as easily be wrong, which is why I wrote "speculate wildly". Eric. 144.32.89.104 (talk) 16:53, 12 June 2008 (UTC)

All of the counterexamples given so far with leading zeros also have at least one column or row consisting of all zeros. Maybe that, and not leading zeros, is the real exception? Or can someone find a counterexample to that? —Ilmari Karonen (talk) 19:27, 12 June 2008 (UTC)

(400,441,196), transposed (441,049,016). -- Meni Rosenfeld (talk) 20:52, 12 June 2008 (UTC)

My program found a 3x3 that isn't symmetric: (100,400,400) transposes to (144,0,0). It has leading zeros on the columns, but not the rows, which is an improvement, but still not ideal. It's the best you can get with 3x3's though. All the ones without leading 0's are symmetric. There must be a general theorem here somewhere, can anyone find and prove it? --Tango (talk) 16:54, 12 June 2008 (UTC)

Gandalf did specify that every column must be an n-digit number. What he didn't specify is that the original numbers must be distinct - without this, (144,400,400) there is a counterexample for $n=3$. -- Meni Rosenfeld (talk) 17:12, 12 June 2008 (UTC)

But that's symmetric... --Tango (talk) 17:32, 12 June 2008 (UTC)

Oh, of course, sorry. I had a counterexample, but the margins of the page were too narrow to write it down. -- Meni Rosenfeld (talk) 17:45, 12 June 2008 (UTC)

Or maybe I'm just imagining things. -- Meni Rosenfeld (talk) 17:55, 12 June 2008 (UTC)

(outdent) One could exploit the fact that square numbers need end in 0, 1, 4, 5, 6 or 9. Further, that the last two digits have only 22 possibilities (e.g., 01, 04, 09, 16, 25, 36, 49, 64, 81, 00, 21, 44, 69, 96, 56, 89, 24, 61, 41, 84, 29, 76). etc. Baccyak4H (Yak!) 18:59, 12 June 2008 (UTC)

This proof is not going well... I can prove that, in the 3x3 case, the middle digits of the last column and last row much have the same parity. That's as far as I've got... Can anyone do any better, or at least give me some ideas to try? --Tango (talk) 18:56, 12 June 2008 (UTC)

I wonder if there might not be an inductive proof? A 1×1 square is obviously symmetric; can we prove that every n×n square of squares being symmetric implies the same for n+1? —Ilmari Karonen (talk) 19:27, 12 June 2008 (UTC)

Here's a lemma that may help: if k is a square number and n even, then k mod 10ⁿ must also be a square number. Thus, the lower right n×n corner of any square of squares, for even n, is itself a square of squares. —Ilmari Karonen (talk) 19:35, 12 June 2008 (UTC)

...or is it? I thought it was obvious when I wrote the above, but now I'm not so sure anymore... :-/ —Ilmari Karonen (talk) 19:47, 12 June 2008 (UTC)

(edit conflict) That lemma doesn't seem to the true. 144 is square, and 2 is even, but 144 mod 100 is 44, which is not square. Or have I misunderstood you? --Tango (talk) 19:48, 12 June 2008 (UTC)

No, just a brain fart on my part. :-( —Ilmari Karonen (talk) 19:50, 12 June 2008 (UTC)

I made a few computer searches for a counter-example, and got a near miss with 9 digits. Columns: (249166225, 351562500, 913611076, 156625225, 661209796, 62159?245, 250272400, 207994084, 506565049). Rows are the same except that 249166225 becomes 239166225, and 351562500 becomes 451562500. There's no way to fill in the missing digit to make 62159?245 into a perfect square. I've been looking for counterexamples (like this one) which have a single asymmetry, where the difference between the two asymmetric digits is exactly 1: I've checked all such potential counter examples up through 9 digits. There were a few other near misses, the smallest being: (15129, 67600, 16641, 20449, 9019?), and the other 1 or 2 near misses being 9 digits. I'm not going to look any further, so good luck hunting/proving. Eric. 144.32.89.104 (talk) 19:46, 12 June 2008 (UTC)

Thanks to all for the ideas. To clarify - yes, I was excluding leading zeros, although the asymmetric examples with 0 rows/colums are interesting; no, the squares don't have to be distinct. The "near miss" approach sounds promising. Gandalf61 (talk) 20:28, 12 June 2008 (UTC)

A few more thoughts. I've brute-force checked everything through 5 digits and found no asymmetric solutions (although, don't trust the accuracy of my programs too much). The search is greatly aided by using the fact that the two square numbers with the same first half are equal (provided they have the same number of digits), so if a matrix has any asymmetries, some of them must necessarily be present in the upper-left quadrant.

I thought it was time to do a few heuristics. Suppose we are trying to fill a 2n by 2n square-of-squares with digits. First, let us permit leading zeros. There are $10^{4n^{2}}$ ways to fill with digits. Any given 2n digit number has a $10^{-n}$ chance of being a perfect square (keep in mind I'm permitting leading zeros). For a randomly filled square, the "chance" of every row and column being a perfect square is $10^{-4n^{2}}$; so we have an expectation of precisely 1 way to make a square-of-squares with 2n digits (we can assume that this solution is asymmetric). However, we can do better using a symmetric square-of-squares. We fill the diagonal and the upper-right triangle, a total of $2n^{2}+n$ digits, and copy the digits from the upper-right triangle into the lower-left triangle. Since it is symmetric, we only need to verify that the columns are perfect squares: this has a chance of succeeding of $10^{-2n^{2}}$, for an overall expectation of $10^{n}$ symmetric square-of-squares with 2n digits.

But let us restrict our attention to those square-of-squares with no leading zeros (we neglect the fact that if we no longer permit leading zeros, the chance of a randomly selected 2n digit number being a perfect square drops beneath $10^{-n}$). For asymmetric square-of-squares, this is $(9/10)^{4n-1}$ of them, and there was only 1 to being with, so we have an expectation of $(9/10)^{4n-1}$ asymmetric square-of-squares (summing over n > 1, these yields a total of 1.390802). For symmetric square-of-squares, this is $(9/10)^{2n}$ of them, so we have an expectation of $8.1^{n}$. So, we should expect to find a rapidly growing number of symmetric square-of-squares, and a rapidly diminishing number of asymmetric square-of-squares. Ok, I think I really will stop here. Eric. 144.32.89.104 (talk) 21:24, 12 June 2008 (UTC)

Where did that thing about the first halves being equal meaning the whole things are equal come from? Unless I've misunderstood you, I have a counter example. 32²=1024 and 33²=1089, both have a first half of "10", both are square, but they aren't equal. --Tango (talk) 21:47, 12 June 2008 (UTC)

I was speaking loosely; your example is right, so the rule I used was, for a n digit number, the first (n + 1) / 2 digits (rounded up) suffice. Eric. 81.132.23.106 (talk) 21:29, 13 June 2008 (UTC)

Outside of base 10, there are plenty of examples. Generally there are more of them in higher bases, but I've found several in bases less than 10. For example, in base 5 there's this neat one:

11114
40000
10000
10000
10000

made up of the numbers 10000, 11114, 14111, and 40000 which in decimal are 25^2=625, 28^2=784, 34^2=1156, and 50^2=2500. It also demonstrates the typical appearance of most of the answers in any base: lots of 4's and 1's, and especially lots of 0's.

There are some without 0's though, like this little one in base 24, which oddly enough is symmetric around the other diagonal (does that count?):

1C
11

(I'm using A=10, B=11, ... Z=35 for the higher digits)

In base 23 there's a rarity: a 3x3 with no 0's no 1's, and no 4's:

2DC
7MG
6D8

There's another one of those in base 33 at 3x3, and one in base 23 at 5x5. Also there's a nice 5x5 in base 15 composed entirely of 1's, 4's, and 9's. (Exercise for the reader.)

Here's how many I've found with various bases and sizes.

	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	26	27	28	29	30	31	32	33	34	35	36
2x2	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	2	0	0	0	0	0	0	0	0	8	0	0	2
3x3	0	0	0	0	0	0	0	0	0	0	4	4	0	4	16	10	4	4	12	4	6	8	34	14	4	12	32	6	4	10	58	18	6	14	66
4x4	0	0	0	0	0	0	2	2	0	0	2	0	0	10	44	4	0	0	30	6	2	0	62	16	0	10	10	2	12	6	20	6	6	14	386
5x5	0	0	0	4	0	2	20	4	0	0	106	2	2	14	252	0	12	10	170	26	8	10	450	48	8	50	266	?	?	?	?	?	?	?	?
6x6	0	0	0	0	0	0	6	12	0	0	50	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?
7x7	0	0	0	0	0	4	52	20	8	4	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?
8x8	0	0	0	0	2	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?

The missing entries correspond to searches I haven't done yet. (The big ones are pretty slow. 5x5 base 25 is running now.) --tcsetattr (talk / contribs) 00:00, 13 June 2008 (UTC)

Fascinating table, thank you! Anyone want to hazard a guess at what's so special about bases 10 and 11? The lack of any in the smaller bases isn't surprising - there just aren't many squares with 6 or less digits, so there aren't as many possibilities to try, but there are plenty in bases 7, 8 and 9, but then suddenly none in 10 or 11, and then plenty again. Strange... --Tango (talk) 00:19, 13 June 2008 (UTC)

Hmm... a quick eyeballing of the table suggests a pretty clear series of peaks at bases that are multiples of 4, so it's not surprising in that light that the bases 8 and 12 should have more solutions than 10 and 11. Not so sure about why bases 7 and 9 (or base 5, for that matter) should have more than 10 and 11, though. If I squint at it just right I could almost suspect a bias against squarefree non-prime bases, but it's all fuzzy enough that I might as likely just be seeing patterns in random noise. (And besides, 11 is prime.) —Ilmari Karonen (talk) 00:48, 13 June 2008 (UTC)

Excellent table ! Looks as if asymmetric squares of squares should emerge for base 10 if we look at large enough squares, but a brute force search of course becomes less and less feasible. Maybe need some clever way of reducing the size of the search space ... Gandalf61 (talk) 13:56, 13 June 2008 (UTC)

Actually all I needed was a few more hours of CPU time.

1313316  1542564  6441444  6441444
6497401  5645376  4000000  4000000
1562500  8410000  4840000  4840000
5904900  2505889  1004004  1000000
4609609  5308416  4410000  4410000
4000000  6708100  4000000  4000000
1000000  4609609  4004001  4000000

The table above has been updated with a few new entries. --tcsetattr (talk / contribs) 19:18, 13 June 2008 (UTC)

Congratulations! --Tango (talk) 19:44, 13 June 2008 (UTC)

Wow, very exciting. Can you give some insights in how your program worked? Was it a clever brute-force, or were you only looking for counterexamples of a carefully chosen form? And, thanks to Gandalf for an interesting problem. Eric. 81.132.23.106 (talk) 21:29, 13 June 2008 (UTC)

Started out brutish, added a little bit of cleverness later. This problem is a lot like crossword puzzle construction. First generate a list of all square numbers with the correct number of digits. That's like the list of words you are allowed to put in the puzzle. The grid is a simple crossword grid with no black squares. The basic method was to define a recursive procedure like this: you have a grid in which the first n rows are filled with square numbers already. Go through your list of words (square numbers), trying each one of them in the (n+1)st row. After you put a word in, check the columns. Each column now has n+1 digits followed by some blanks. If all the columns contain prefixes of valid words (square numbers), recurse. Otherwise, you've got a bad column so you remove the word you just put in and move on to the next one. Brutish so far, right? The clever part was reversing all the words so the prefixes are actually reversed suffixes, which takes advantage of the limited repertoire of square suffixes of all lengths, then building those prefixes into a tree before the main loop for quick searching. Then I added a second grid full of pointers to tree nodes. Each cell in that grid points to the tree node corresponding to the column prefix that ends directly above that cell. That eliminated a lot of memory references by chaning prefix checks from a "trace down from the root of the tree" to a "look at this one tree node". Elimination of the unwanted symmetric solutions was done as a post-process. There is always an even number of results, since each solution reflected across the diagonal is also a solution, which indicates that I should still be able to cut the search time in half, but instead I went to sleep and let it run. Run times vary greatly depending on how many near-solutions there are. The 7x7 base 9 search took 8 hours, then moving on to base 10, it finished that one in 8 minutes! 7x7 base 11 is still running after 9 hours. The 11 column will not remain dry though. It's found 3 solutions so far, so there will be at least 4. I also implemented a second strategy, where instead of filling in the rows in order, I searched all the rows and columns and picked the one with the fewest candidates matching the digits already in the grid. That turned out to be slower but not by much, and I didn't spend as much time working on it so I don't really know which strategy would be better if they were both perfectly optimized. --tcsetattr (talk / contribs) 22:37, 13 June 2008 (UTC)

I think you can get rid of the binary column. To avoid leading zeros, the whole first column and first row would need to be 1's, that means you need to find an n such that 2ⁿ-1 is a square, but:

2ⁿ-1 = m^2

2ⁿ-2 = m^2-1

2(2^n-1-1) = (m+1)(m-1)

The LHS is even, so at least one of m+1 and m-1 must be even, which means both are. This means the RHS, and therefore the LHS, is divisible by 4. This means 2^n-1-1 must be even, but that can only be true for n=1, which would be a 0x0 matrix, which isn't very meaningful. Therefore, there can be no binary squares of squares, even symmetric ones, without leading zeros. --Tango (talk) 20:06, 13 June 2008 (UTC)

Wow ! Great work everyone - thank you very much for taking an interest in my problem. Gandalf61 (talk) 06:56, 14 June 2008 (UTC)

A fascinating discussion. Should we make an article Square of squares about this? The article wouldn't be original research as that has been done here - presumably we would reference the archival version of this page. -- SGBailey (talk) 08:27, 14 June 2008 (UTC)

I don't think the Wikipedia Mathematics Reference Desk is a reliable source. Anyone feel like writing up a short paper on the subject and trying to get it published? That would be great publicity for the ref desk, having a peer reviewed paper written collaboratively on it! --Tango (talk) 15:24, 14 June 2008 (UTC)

Wow, all this is fascinating ! All the information about this should be kept somewhere (and not just in the reference desk archives). I love the table ! --Xedi^Talk 04:05, 15 June 2008 (UTC)

Are all the numbers in the table 'even' because of reflective symmetry? -- SGBailey (talk) 16:32, 16 June 2008 (UTC)

Yes, if you're looking for really distinct solutions you should divide all the table entries by 2. The base 11 7x7 search finally finished so I'm updating the table again. base 6 finally yielded results at 8x8. I'm quitting there. --tcsetattr (talk / contribs) 22:15, 16 June 2008 (UTC)

A formula for the cube of a complex number

$(a+bi)(a+bi)(a+bi)$

$(a^{2}+2abi-b^{2})(a+bi)$

$(a^{2}-b^{2}+2abi)(a+bi)$

I hope the last step, the rearrangement is valid - i.e. you can "group" the real and imaginary parts. But I think something is wrong because if you multiply the two numbers the result is a real number. What's the correct form? 81.187.252.174 (talk) 13:40, 12 June 2008 (UTC)

Looks fine to me. Multiply out the last expression and you have

$(a^{2}-b^{2}+2abi)(a+bi)$

$=(a^{3}-ab^{2}+2a^{2}bi)+(a^{2}bi-b^{3}i-2ab^{2})$

$=a^{3}-3ab^{2}+(3a^{2}b-b^{3})i$

which is not real unless b=0 or 3a²=b². Gandalf61 (talk) 13:49, 12 June 2008 (UTC)

Question about product rule-calculus

Can the product rule be derived (using limits) from the following:

(X + deltaX)(Y + deltaY)

Why or why not?

Anne teak (talk) 13:45, 12 June 2008 (UTC)

This question was asked yesterday, I replied and then the section was deleted by an anonymous user, I guess by mistake. This is what I said last time:

That doesn't make sense. That's just an expression, not a statement, so you can't derive anything from it. See product rule for some proofs of the rule. --Tango (talk) 20:36, 11 June 2008 (UTC)

--Tango (talk) 14:05, 12 June 2008 (UTC)

In any case, can you provide a little more context for the question? -- Meni Rosenfeld (talk) 14:07, 12 June 2008 (UTC)

Sounds like homework to me. Presumably he wants to know whether the product rule of differentiation can be derived as a limit of the finite difference equation XY + Δ(XY) = (X + ΔX)(Y + ΔY), where Δf denotes the change of f over some short but finite interval. Presumably he's looking for something similar to Product rule#Discovery by Leibniz, only using limits of finite forward differences in place of differentials (which is mostly just a cosmetic change at this level of rigor). The proof can be made more rigorous, but that requires defining the meaning of Δ more carefully, e.g. by substituting X = X(t), Y = Y(t), Δf = f(t + Δt) - f(t) and taking the limit Δt → 0 while making use of the fact that X and Y are assume to be continuous and differentiable. —Ilmari Karonen (talk) 16:28, 12 June 2008 (UTC)

Π (film)

What do mathematicians think about the film Π (film)? GoingOnTracks (talk) 13:50, 12 June 2008 (UTC)

I study maths, and think it may be the worst maths film ever.--Fangz (talk) 16:48, 12 June 2008 (UTC)

There was hardly any mathematics in it, and the protagonist wasn't portrayed as an average workaday mathematician, so I don't think there's much to find fault with. The most serious mistake—not mentioned in the WP article, oddly—was Max's suggestion that the Kabbalists had already tried every possible 216-digit number. Max should have realized that this is impossible (10²¹⁶ is about 10¹⁵⁵ times the age of the universe measured in units of the Planck time), and I can't imagine a mathematician watching the movie without noticing this mistake either, so I'm surprised it survived into the finished product. -- BenRG (talk) 17:04, 12 June 2008 (UTC)

Our article on the film lists a whole load of mathematical errors, which suggests they never actually involved a mathematician at any point during production. --Tango (talk) 17:31, 12 June 2008 (UTC)

I don't think that can be taken for granted. The filmmakers may have been informed about some of the errors, and decided that to correct them would have in some way interfered with their artistic vision. That's a perfectly reasonable attitude for them to take, in my humble opinion -- as the saying goes "it's just a movie, not a cure for cancer", or in this case not a math course. Whether I get upset about factual errors depends on the genre, and in the genre of surreal art films I'll let pretty much anything slide, if I judge the movie to be worthwhile on its own terms. (These are generalities -- I haven't actually seen π, and I seem to recall hearing that it's dull as dirt.) --Trovatore (talk) 00:47, 14 June 2008 (UTC)

That's very true in general, but if you look at the errors listed in the article, most of them are clearly just a complete lack of any attempt to get things right. The article is called π, but gets the digits of it wrong in the opening sequence! That's not artistic license, it's just plain wrong. --Tango (talk) 01:24, 14 June 2008 (UTC)

Maybe they were trying to make some statement. "Mathematics is useless, so you may as well get it wrong." -- Meni Rosenfeld (talk) 13:33, 16 June 2008 (UTC)