{"id":"urn:lj:livejournal.com:atom1:noam_rion","title":"Noam","subtitle":"Noam","author":{"name":"Noam"},"link":[{"@attributes":{"rel":"alternate","type":"text\/html","href":"https:\/\/noam-rion.livejournal.com\/"}},{"@attributes":{"rel":"self","type":"text\/xml","href":"https:\/\/noam-rion.livejournal.com\/data\/atom"}},{"@attributes":{"rel":"service.feed","type":"application\/x.atom+xml","href":"https:\/\/noam-rion.livejournal.com\/data\/atom","title":"Noam"}}],"updated":"2011-05-31T03:02:17Z","entry":[{"id":"urn:lj:livejournal.com:atom1:noam_rion:102933","link":[{"@attributes":{"rel":"alternate","type":"text\/html","href":"https:\/\/noam-rion.livejournal.com\/102933.html"}},{"@attributes":{"rel":"self","type":"text\/xml","href":"https:\/\/noam-rion.livejournal.com\/data\/atom\/?itemid=102933"}}],"title":"noam_rion @ 2008-01-30T18:34:00","published":"2008-01-30T23:36:20Z","updated":"2011-05-31T02:41:19Z","content":"<a href=\"http:\/\/www.cbc.ca\/podcasting\/index.html?arts\" target=\"_blank\" rel=\"nofollow\">CBC arts & music podcasts.<\/a> Mmmmmm. Thanks, <span  class=\"ljuser  i-ljuser  i-ljuser-type-P     \"  data-ljuser=\"ceallaighgirl\" lj:user=\"ceallaighgirl\" ><a href=\"https:\/\/ceallaighgirl.livejournal.com\/profile\/\"  target=\"_self\"  class=\"i-ljuser-profile\" ><img  class=\"i-ljuser-userhead\"  src=\"https:\/\/l-stat.livejournal.net\/img\/userinfo_v8.png?v=17080&v=922\" \/><\/a><a href=\"https:\/\/ceallaighgirl.livejournal.com\/\" class=\"i-ljuser-username\"   target=\"_self\"   ><b>ceallaighgirl<\/b><\/a><\/span>."},{"id":"urn:lj:livejournal.com:atom1:noam_rion:95027","link":[{"@attributes":{"rel":"alternate","type":"text\/html","href":"https:\/\/noam-rion.livejournal.com\/95027.html"}},{"@attributes":{"rel":"self","type":"text\/xml","href":"https:\/\/noam-rion.livejournal.com\/data\/atom\/?itemid=95027"}}],"title":"Frost on window","published":"2006-12-08T04:34:26Z","updated":"2011-05-31T02:35:57Z","content":"The red lights are from outside.<br \/><br \/><img src=\"https:\/\/imgprx.livejournal.net\/1482bcae952d29b485e03f23f411aa0ea3cc3eba52f6bc4f65d465161396c3a4\/P2WlxyVijxKvgmFr98lTVEMdsf-ah7h03EGPSqddhsTKvRbWgdKmRkU0BwhpEEJwuw0HzG2ILCdAHh1b0j4p8FUbziWfaaeL_V0SuQ:DH1R1VsXE2oHNYWPcFE4Bg\" fetchpriority=\"high\" \/><br \/><br \/><img src=\"https:\/\/imgprx.livejournal.net\/8a4be98ca79175aa0b8522e7da5fd1612426c50b579cca200cf3d78ef285e9e8\/P2WlxyVijxKvgmFr98lTVEMdsf-ah7h03EGPSqddhsTKvRbWgdKmRkU0BwhpEEJwuw0HzG2ILCdAHh1b0j4p8FUbziWfaqeL_V0SuQ:vftrGa1WQ6zo6fjTLkA5bg\" loading=\"lazy\" \/><br \/><br \/><img src=\"https:\/\/imgprx.livejournal.net\/499a78d620c506ad3e7b19283c0a24f382d5a51178d44c338809ce7ae967f2ff\/P2WlxyVijxKvgmFr98lTVEMdsf-ah7h03EGPSqddhsTKvRbWgdKmRkU0BwhpEEJwuw0HzG2ILCdAHh1b0j4p8FUbziWfa6eL_V0SuQ:0oaCogCWjBFNoiwY5E85tg\" loading=\"lazy\" \/>"},{"id":"urn:lj:livejournal.com:atom1:noam_rion:82667","link":[{"@attributes":{"rel":"alternate","type":"text\/html","href":"https:\/\/noam-rion.livejournal.com\/82667.html"}},{"@attributes":{"rel":"self","type":"text\/xml","href":"https:\/\/noam-rion.livejournal.com\/data\/atom\/?itemid=82667"}}],"title":"Problems with representing numbers on computers, part 2","published":"2006-01-15T04:19:27Z","updated":"2011-05-31T03:02:16Z","content":"This may not make sense until you read <a href=\"http:\/\/www.livejournal.com\/users\/noam_rion\/82376.html\" target=\"_blank\">Problems with representing numbers on computers, part 1<\/a>.<br \/><br \/><br \/>Now what if you want to store numbers with fractional parts (e.g. 123.52)?<br \/><br \/>First, I want to mention something about representing fractional numbers in base 10, and explain what scientific notation is.<br \/><br \/>If you have a number with a fractional part in base 10, e.g. 123.52, that means 1 hundred, 2 tens, 3 ones... and 5 tenths, and 2 hundredths. Note that a tenth is 1 \/ 10 (1 divided by 10), a hundredth is 1 \/ 100, etc.<br \/><br \/>Some numbers don't lend themselves well to being represented in base 10. For example, 1 \/ 3 (one third) is 0.3333333.. with an infinite number of 3's. The problem is that there's no good way to write 1\/3 in terms of tenths, hundredths, etc. You have to add up 3 tenths, plus 3 hundredths, plus 3 thousandths, and so on infinitely. If you only have a finite number of places to use, you can't store 1\/3. e.g. If you had ten places to use, you could have .3333333333 -- but that's not quite equal to 1\/3. It's close, but not exact. We'll come back to this problem later, when I talk about representing fractions in binary.<br \/><br \/>Scientific notation is a method for representing numbers, widely used in scientific applications. I mention it because it's similar to floating point numbers. I'll start with an example. The number 38129.7712 would be written in scientific notation as 3.81297712 * 10^4 (or sometimes as 3.81297712E4). Essentially, I'm taking the original number and dividing it by 10^4 = 10000. Since I don't want to actually change the number, I have to write down that it's multiplied by 10^4 (note that the 4 is called an exponent). In general, the idea is to rewrite the number so that it has a single digit, then a decimal point, and then the rest of the digits. For example, 123.5 would be written as 1.235 * 10^2.<br \/><br \/>(One of the advantages in science is that you can easily compare two large numbers and get an idea if one is much larger than the other. For example, is 239283202323 larger or smaller than 2123400110203? If I write them in scientific notation, I get 2.39283202323 * 10^11 and 2.123400110203 * 10^12, so it's easy to see that the second is larger -- it's multiplied by 10 one more time than the first number is. In general, if you write the numbers in scientific notation, sometimes just checking the exponent is enough to see which is larger.)<br \/><br \/>So how does this apply to storing fractional numbers in a computer?<br \/><br \/>Remember how 123.52 means 1 hundred, 2 tens, 3 ones, 5 tenths, and 2 hundredths? For the part of a number that's larger or equal to 1, you write it in terms of ones, tens, hundreds, thousands, etc. For the fractional part that's smaller than 1, you write it in terms of tenths, hundredths, thousandths, etc. Similarly, in binary you write the part larger than or equal to 1 in terms of ones, twos, fours, eights, etc. For the fractional part, you write it in terms of halves (1 \/ 2), quarters (1 \/ 4), eighths (1 \/ 8), etc. For example, 1101.01 means 1 eight, 1 four, 0 twos, 1 one, 0 halves, and 1 quarter. 8 + 4 + 1 + 1\/4 = 13.25.<br \/><br \/>Now, a floating point number does the same sort of thing as scientific notation does. It takes 1101.01, and rewrites it as 1.10101 * 2^3 (3 is the exponent here). (The reason it's * 2^3 and not * 10^3 is that each place is a multiple of two, not a multiple of ten; I went over this in part 1.)<br \/><br \/>Again, just like in base 10, there are some numbers that can't be represented well. For example, 0.4 can't be represented well as a sum of halves, quarters, eighths, etc. It requires an infinite sum of them. So a computer, which has a limited number of bits with which to store the number, can't store 0.4 exactly. It can only store something close to it. This is the cause of some odd behaviour you sometimes see with computer arithmetic. For example, a computer might calculate 81.66 * 20 = 1633.1999999999998, when the answer should be 81.66 * 20 = 1633.2. This is getting close to the problem of why 12345678987654320 and 12345678987654321 come out the same. But, you say, those two numbers are integers, not fractional numbers -- so why the problem? Well, JavaScript stores all numbers as double precision (64 bit) floating points, even if the original numbers are integers. (That way, calculations are easier; by using floating points, it always has the ability to store a fractional part if a calculation results in a number with a fractional part. It doesn't have to go back and forth between using integers and floating points.) This is not a problem in itself -- except that a 64 bit floating point can't store as large a range of numbers as a 64 bit integer. Read on for how floating points work.<br \/><br \/>A double precision floating point is 64 bits. It uses 1 bit as the sign bit, 12 bits to store the exponent (called the \"mantissa\"), and 52 bits to store the number (called the \"significand\"). Actually, it uses a trick to squeeze out a little bit more storage space: Any non-zero binary number must have at least one bit that is set to 1. (If all the bits were 0s, then the number would be zero.) Once we write it in scientific notation style, it will be written as 1.xxxxx... -- there will always be a 1 and then a decimal point and then the rest of the number. So rather than storing the 1 before the decimal point, we can just assume it's always there and not have to store it. That gives us one more bit that we can use to store the rest of the number. (Note that you can't do this in base 10, because the digit before the decimal place could be 1, 2, 3, 4, 5, 6, 7, 8, or 9. You can't make an assumption as to what it will be.)<br \/><br \/>Remember that 1101.01 (13.25) can be written as 1.10101 * 2^3? So it would be stored as:<br \/><br \/><ul><li><strong>Sign bit:<\/strong> 0<\/li><li><strong>Exponent (mantissa):<\/strong> 3 (the exponent is also stored in binary, but in a somewhat unusual form, so I won't go into it here and will just write it in base 10)<\/li><li><strong>Number (significand):<\/strong> .10101 (note that the 1 before the decimal point is not actually stored<\/li><\/ul><br \/><br \/>(Now, I said that you can assume that 1 is always there so long as the number isn't zero. So, if you're always assuming the 1 is there, it necessitates a special way to represent zero, and in fact a zero in floating point is represented differently -- it's not as simple as having all bits set to 0. That's the price paid for squeezing out an extra bit of storage.)<br \/><br \/>Now we're at the point where I can explain the original problem.<br \/><br \/>Let's look at how 12345678987654321 is stored as a double precision floating point. In binary, 12345678987654321 is:<br \/>101011110111000101010001100010100100011111010010110001<br \/><br \/>Writing that in scientific notation style, we have:<br \/>1.01011110111000101010001100010100100011111010010110001 * 2^53<br \/><br \/>So the sign bit is 0 (signifying a positive number), and the mantissa is 53 (from 2^53). Now, since we assume there's a 1 before the decimal point, we only store<br \/>.01011110111000101010001100010100100011111010010110001<br \/>for the significand. The problem is, that's still 53 bits (count them if you like), and the double precision floating point only has space for 52 bits for the significand. So what does it do? It chops off the rightmost bit (called the \"least significant\" bit -- that's the bit representing the number of ones) and only stores:<br \/>.0101111011100010101000110001010010001111101001011000<br \/><br \/>Now, I said that 12345678987654321 is<br \/>101011110111000101010001100010100100011111010010110001<br \/>and similarly, 12345678987654320 is<br \/>101011110111000101010001100010100100011111010010110000<br \/><br \/>The only difference is the rightmost least significant bit (representing the number of ones). So, because there's not space to store the least significant bit, it's not possible to tell the difference between those two numbers once they've been stored in a double precision floating point. When the computer tries to reconstruct the number, it assumes the missing bit is a 0. (This is a reasonable assumption; it has to assume one way or the other, and it doesn't make much difference in the long run whether it assumes a 1 or a 0. Either way, you're losing some information.)<br \/><br \/>In the case that you're storing a long fractional number, e.g. 8723.23834129523172323915, if the least significant bit got cut off it might not matter so much. The least significant bit affects the smallest part of the number -- so it would change the fractional part by a small amount. But when you're storing an integer, the smallest part of the number is the ones place -- and a change there is usually quite noticeable.<br \/><br \/>(Note that if you tried to store something even larger than 12345678987654321, more than one bit might get cut off -- and so more places than just the ones place would be incorrect.)<br \/><br \/>The solution? Use a programming language (other than JavaScript) that lets you store integers as integers (which, as you recall, have 1 sign bit and 63 bits of storage -- more than enough for 12345678987654321), or use a programming language that uses floating points larger than double precision.  (Some programming languages use \"extended double precision\", which uses 80 or more bits instead of the 64 bits double precision uses.)<br \/><br \/><br \/>If you need a calculator that can handle large numbers, try the arbitrary precision calculator <a href=\"http:\/\/www.gnu.org\/software\/bc\/bc.html\" target=\"_blank\" rel=\"nofollow\">bc<\/a> (*nix version). There's also a <a href=\"http:\/\/gnuwin32.sourceforge.net\/packages\/bc.htm\" target=\"_blank\" rel=\"nofollow\">Windows version<\/a>. It doesn't have a graphical interface; you have to type commands to it. But it's very flexible -- read the documentation for more information.<br \/><br \/>To get started, try typing<br \/><strong>111111111^2<\/strong> (and press enter).<br \/>It should give you 12345678987654321.<br \/><br \/>In general, you'll want to type<br \/><strong>scale=5<\/strong><br \/>(or maybe a number larger than 5) before you start doing any other calculations in it. <strong>scale<\/strong> determines how many decimal places it uses in calculations; by default, scale is set to 0, so if you type <strong>4\/3<\/strong> you'll get 1 instead of 1.25. If you type <strong>scale=1<\/strong> and then <strong>4\/3<\/strong>, you'll get 1.3. If you type <strong>scale=2<\/strong> and then <strong>4\/3<\/strong>, you'll get 1.25. I find five decimal places is enough for most of my calculations.<br \/><br \/>Well, that was an interesting two hour diversion from homework. Comments?<br \/><a name='cutid1-end'><\/a>"},{"id":"urn:lj:livejournal.com:atom1:noam_rion:82376","link":[{"@attributes":{"rel":"alternate","type":"text\/html","href":"https:\/\/noam-rion.livejournal.com\/82376.html"}},{"@attributes":{"rel":"self","type":"text\/xml","href":"https:\/\/noam-rion.livejournal.com\/data\/atom\/?itemid=82376"}}],"title":"Problems with representing numbers on computers, part 1","published":"2006-01-15T02:17:55Z","updated":"2011-05-31T03:02:17Z","content":"<span  class=\"ljuser  i-ljuser  i-ljuser-type-P     \"  data-ljuser=\"notnotrebecca\" lj:user=\"notnotrebecca\" ><a href=\"https:\/\/notnotrebecca.livejournal.com\/profile\/\"  target=\"_self\"  class=\"i-ljuser-profile\" ><img  class=\"i-ljuser-userhead\"  src=\"https:\/\/l-stat.livejournal.net\/img\/userinfo_v8.png?v=17080&v=922\" \/><\/a><a href=\"https:\/\/notnotrebecca.livejournal.com\/\" class=\"i-ljuser-username\"   target=\"_self\"   ><b>notnotrebecca<\/b><\/a><\/span> recently pointed out to me that online calculators incorrectly calculate 111111111*111111111. It should be 12345678987654321 (any time you multiply a string of ones by itself you get a nice symmetrical answer like that), except that the online calculators she tried consistently gave 12345678987654320 instead. (Note the zero on the end.)<br \/><br \/><br \/>Here's what I found out.<br \/><br \/>Online calculators are often implemented in the JavaScript programming language. JavaScript stores all numbers as double precision floating point numbers, according to the <a href=\"http:\/\/grouper.ieee.org\/groups\/754\/\" target=\"_blank\" rel=\"nofollow\">IEEE-754 specification<\/a>. The problem is, in double precision floating point numbers, 12345678987654320 and 12345678987654321 can't be distinguished from each other. \"Say what?\", I hear you ask. Well, it's like this.<br \/><br \/>The question is, how do you represent the infinite collection of all numbers on a computer? A computer doesn't have infinite memory.<br \/><br \/>For integers (that is, numbers without a decimal point, e.g. 12742), you can simply say you'll allow numbers within a certain range, and this what computers do.<br \/><br \/>A quick primer on binary: The numbers we're most familiar with are in base 10. That means that each place represents the number of ones, the number of tens, the number of hundreds, and so on. (Note how it gets multiplied by ten with each place.) 732 means 7 hundreds, 3 tens, and 2 ones, i.e. 700 + 30 + 2 = 732. Binary on the other hand is base 2, so each place represents the number of ones, the number of twos, the number of fours, the number of eights, etc. (Note how it gets multiplied by two with each place.) So 1101 in binary means 1 eight, 1 four, 0 twos, and 1 one, i.e. 8 + 4 + 1 = 13.<br \/><br \/>Typically, an integer will be stored in a computer in 32 bits or 64 bits of memory. How large a number does that let you store? An analogy back to base 10 will help. If I'm only allowed to store numbers having five or less places in base 10, then I could store 10202 but not 110202 (because that uses six places). Essentially, I can only store numbers less than or equal to 10^6 - 1 (that means 10*10*10*10*10*10  - 1 = 99999). Similarly, if I had five bits in binary, I could store numbers less than or equal to 2^6 - 1 (meaning 2*2*2*2*2*2 - 1 = 63). 63 in binary looks like 11111, taking up all five bits.<br \/><br \/>But, we want to be able to store negative numbers as well, so what we do is use one of the bits to say whether the number is positive or negative. This one bit is called the \"sign bit\". By convention, if the sign bit is 0 the number is positive, and if it's 1 the number is negative. So if we had 32 bits to start with, we could use 1 for the sign bit and 31 of them to store the number and thus could have numbers as large as 2^32 - 1 = 4294967295 and as small as -4294967295. With 64 bits, we can store numbers as large as 2^64 - 1 = 18446744073709551615 and as small as -18446744073709551615. For most purposes, this is enough.<br \/><br \/>(Actually, this isn't exactly how integers are stored. One problem is that we have two representations of the number zero, positive zero and negative zero. Because you could set all the bits except the sign bit to 0, and then have the sign bit set to either  1 or 0, we get two different ways of representing the number zero. For this and other reasons, numbers are usually stored in a form called two's complement -- but that's another topic.)<br \/><br \/>See <a href=\"http:\/\/www.livejournal.com\/users\/noam_rion\/82667.html\" target=\"_blank\">part two<\/a> for the continuation of this, and the explanation of why 12345678987654320 and 12345678987654321 can't be distinguished from each other.<br \/><a name='cutid1-end'><\/a>"},{"id":"urn:lj:livejournal.com:atom1:noam_rion:80875","link":[{"@attributes":{"rel":"alternate","type":"text\/html","href":"https:\/\/noam-rion.livejournal.com\/80875.html"}},{"@attributes":{"rel":"self","type":"text\/xml","href":"https:\/\/noam-rion.livejournal.com\/data\/atom\/?itemid=80875"}}],"title":"IKEA Digital Calculator","published":"2005-12-25T08:59:21Z","updated":"2011-05-31T02:59:53Z","content":"<img src=\"https:\/\/imgprx.livejournal.net\/a13f3d960fedc05be2a8694ae488c32b2ffa3c93d28f5161fef1928089885da6\/P2WlxyVijxKvgmFr98lTVEMdsf-ah7h03EGPSqddhsTKvRbWgdKmRkU0BwhpEEJwuw0HzG2LLCdAHh1eyFcS1GMuziWfHOCG5E5RqFQzejHtH-CMusBahn8V7EI_JDlJqBD5pDNGKcZkG3lkDDfZog:Ptf_Ows3muUmx0-MVDK0MA\" title=\"88 cents\" alt=\"88 cents\" fetchpriority=\"high\" \/><br \/>\"Early Digital Calculator, Price 88\u00a2\"<br \/><br \/><img src=\"https:\/\/imgprx.livejournal.net\/49eed337873dd3e644d3aedd3fe8f44e47ea8591253e188535ea77af8f23ca74\/P2WlxyVijxKvgmFr98lTVEMdsf-ah7h03EGPSqddhsTKvRbWgdKmRkU0BwhpEEJwuw0HzG2LLCdAHh1eyFcS1GMuziWfHOCG5E5RqFQzejHtH-CMusBahn8elCJVI3Y:pU9ECLZwkop904SFUchP4g\" title=\"Mini-calculator\" alt=\"Mini-calculator\" loading=\"lazy\" \/><br \/>\"IKEA MINI-CALCULATOR\"<br \/>Tag reads, \"Digital Memory\"<br \/><br \/> <img src=\"https:\/\/imgprx.livejournal.net\/8db5b66127b56073527e48aa1c3e658d41b44aa4205d2a79cd3218f38b4a6615\/P2WlxyVijxKvgmFr98lTVEMdsf-ah7h03EGPSqddhsTKvRbWgdKmRkU0BwhpEEJwuw0HzG2LLCdAHh1eyFcS1GMuziWfHOCG5E5RqFQzejHtH-CMusBahn8V7EJ7b3gN4l2_4mpKIts-Igdpfg0:X7C3Ovk5p01LLBpjoXEszQ\" title=\"Instructions\" alt=\"Instructions\" loading=\"lazy\" \/><br \/>Instructions read:<br \/><br \/><strong>IKEA MINI* CALCULATOR OWNERS MANUAL<\/strong><br \/><br \/>* Also available in EENIE, MINEY & MO models.<br \/><br \/><strong>UNIQUE FEATURES<\/strong><br \/><ul><li>No batteries to replace. Uses energy-conserving digital circuitry.<\/li><li>All calculations guaranteed to \u00b1 five digits.<\/li><li>Not subject to rust or corrosion<\/li><li>Termite insurance available at slight extra charge<\/li><li>Solid state construction. It floats.<\/li><\/ul><br \/><br \/><strong>WARNING<\/strong><br \/><ul><li>Any attempt to play 12-string banjo while using the IKEA MINI Calculator can result in permanent erasure of digital circuitry, voiding of warranty and really bad music.<\/li><\/ul><br \/><br \/><strong>WARRANTY<\/strong><br \/>Your IKEA MINI Calculator is guaranteed to be free from defects in materials and workmanship for as long as you own it. Warranty covers <u>all<\/u> moving parts and electronic circuitry. It does not cover wooden components, which are for appearance only and in no way affect performance of the unit.<a name='cutid1-end'><\/a>"},{"id":"urn:lj:livejournal.com:atom1:noam_rion:77883","link":[{"@attributes":{"rel":"alternate","type":"text\/html","href":"https:\/\/noam-rion.livejournal.com\/77883.html"}},{"@attributes":{"rel":"self","type":"text\/xml","href":"https:\/\/noam-rion.livejournal.com\/data\/atom\/?itemid=77883"}}],"title":"Vector space decompositions","published":"2005-12-11T05:05:43Z","updated":"2011-05-31T02:51:23Z","content":"I think I'm beginning to understand the Primary Decomposition Theorem in Linear Algebra. Yay!<br \/><br \/>First, the Basic Decomposition Theorem says that <strong>if<\/strong> there exist orthogonal projection operators that partition identity, <strong>then<\/strong> the vector space can be written as the direct sum of the subspaces yielded by the projection operators (by their actions on the vector space, that is).<br \/><br \/>The Primary Decomposition Theorem says that, given a linear transformation T on the (finite) vector space (an <a href=\"http:\/\/en.wikipedia.org\/wiki\/Endomorphism\" target=\"_blank\" rel=\"nofollow\">endomorphism<\/a>), then using the minimum polynomial of the transformation, we can construct a direct sum decomposition of the vector space. We do this by constructing orthogonal projection operations that partition identity. Specifically, the subspace yielded by a projection operator's action on the vector space ends up being the kernel of an irreducible distinct factor of the minimal polynomial (well, the factor with T substituted in for the variable). Now, the projection operators consists of the minimal polynomial, less one distinct factor (which is divided out), times some other stuff obtained using the GCD of .. things I don't feel like trying to describe in words. Anyway, the projection operator's subspace is the kernel of the missing factor.<br \/><br \/>Right?"},{"id":"urn:lj:livejournal.com:atom1:noam_rion:77284","link":[{"@attributes":{"rel":"alternate","type":"text\/html","href":"https:\/\/noam-rion.livejournal.com\/77284.html"}},{"@attributes":{"rel":"self","type":"text\/xml","href":"https:\/\/noam-rion.livejournal.com\/data\/atom\/?itemid=77284"}}],"title":"3-d graphing on paper","published":"2005-12-09T04:48:51Z","updated":"2011-05-31T02:51:27Z","content":"<a href=\"http:\/\/www.livejournal.com\/community\/mathart\/16896.html?#cutid1\" target=\"_blank\">A beautiful hand-drawn graph of for the volume of an object.<\/a>"},{"id":"urn:lj:livejournal.com:atom1:noam_rion:76260","link":[{"@attributes":{"rel":"alternate","type":"text\/html","href":"https:\/\/noam-rion.livejournal.com\/76260.html"}},{"@attributes":{"rel":"self","type":"text\/xml","href":"https:\/\/noam-rion.livejournal.com\/data\/atom\/?itemid=76260"}}],"title":"noam_rion @ 2005-12-02T01:01:00","published":"2005-12-02T06:01:43Z","updated":"2011-05-31T02:51:27Z","content":"<a href=\"http:\/\/antwrp.gsfc.nasa.gov\/apod\/ap051130.html\" target=\"_blank\" rel=\"nofollow\">A gorgeous picture of the Horsehead Nebula.<\/a>"},{"id":"urn:lj:livejournal.com:atom1:noam_rion:47853","link":[{"@attributes":{"rel":"alternate","type":"text\/html","href":"https:\/\/noam-rion.livejournal.com\/47853.html"}},{"@attributes":{"rel":"self","type":"text\/xml","href":"https:\/\/noam-rion.livejournal.com\/data\/atom\/?itemid=47853"}}],"title":"Math problem","published":"2005-05-17T08:42:06Z","updated":"2011-05-31T02:08:47Z","content":"I came across an intriguing (if not overly complex) little <a href=\"http:\/\/www.livejournal.com\/community\/mathematics\/611853.html\" target=\"_blank\">math problem<\/a>.<br \/><br \/>In essence, the idea is to determine the number of <i>permutations<\/i> of a <i>set<\/i> of <i>integers<\/i>, where the even numbers are not in their natural places.<br \/><br \/>Vocabulary:<br \/><ul><br \/><li>Integer: A number without a fractional or decimal part. (e.g. 2, 3, -7, 109, etc., but not 57.2 or 3.3333333...)<\/li><br \/><li>Set: A collection of things, in this case integers. (e.g. {1, 2, 3} is a set containing the numbers 1, 2, and 3.) Think of taking some numbers and throwing them in a bag. That's all that a set is.<\/li><br \/><li>Permutation: A way of ordering a set of things. (e.g. {1, 2, 3} and {2, 1, 3} are two different permutations of the above set.)<\/li><br \/><li>Factorial: Means you multiply things. \"4 factorial\" is written 4! and means 4*3*2*1 = 24 (4 times 3 times 2 times 1). 6! = 6*5*4*3*2*1 = 720, etc. 1! of course is just equal to 1, and 0! is <b>defined<\/b> to be equal to 1 (because it makes sense in many many calculations to do so).<\/li><br \/><\/ul><br \/><br \/>So the specific question (simplified slightly, to make possible the drawing of a diagram) is:<br \/><br \/>Given the set of integers {1, 2, 3, 4, 5, 6}, find the number of permutations (i.e. how many ways you can arrange it) in which the even numbers (2, 4, and 6) are NOT in their natural places.<br \/><br \/>e.g. {1, 3, 2, 6, 5, 4} has 2, 4, and 6 all in different places from where they started. {1, 3, 2, 5, 4, 6} on the other hand has 6 still in it's natural place where it started.<br \/><br \/>So here's how you do it.<br \/><br \/>Using a <a href=\"http:\/\/lib.colostate.edu\/howto\/others\/venn.html\" target=\"_blank\" rel=\"nofollow\">Venn diagram<\/a> for illustration.<br \/><br \/><img src=\"https:\/\/imgprx.livejournal.net\/09ddcdfa151e48a29442bdae3b207994f28d80913f060b6f8d26cf0415ef8900\/P2WlxyVijxKvgmFr98lTVEMdsf-ah7h03EGPSqddhsTKvRbWgdKmRkU0BwhpEEJwuw0HzG2LLC5EBB1dylcv7U8MhHvAKtaX6FRe5gw:7hEZJv_7LdNZnQajJ3hMSg\" alt=\"Venn diagram with three overlapping circles\" fetchpriority=\"high\"><br \/><br \/>The problem is \"Determine the number of permutations of {1, 2, 3, 4, 5, 6} in which no even number integer is in it's natural position.\" We can represent this on the above diagram. Let the entire region inside the box be the total number of permutations of the set. There are 6! of these. So we start with 6! permutations.<br \/><br \/>Now we want to exclude the permutations where \"2\" is in it's natural position. Let the red circle (the WHOLE circle, not just the section that is pure red) represent these permutations. If we fix \"2\" in it's natural position and permute the remaining five integers, we get 5! permutations. Because we started with 6! permutations (the entire region inside the box, including the red circle), we want to subtract from that the 5! permutations where \"2\" is in its natural position (the region of the red circle). So we get 6! - 5!.<br \/><br \/>Now, we can do the same with \"4\" (the green circle) and with \"6\" (the blue circle), and we end up with 6! - 5! - 5! - 5! = 8! - 3x5!. (Note that there are 3C1 = 3 ways to pick one even integer from the set of three even integers, and for each even integer there are 5! permutations; this is why we get 3x5!).<br \/><br \/>But note that the circles overlap, so we subtracted some regions more than once. When we subtracted the 5! permutations where \"2\" is fixed, and the 5! permutations where \"4\" is fixed, we subtracted the yellow region twice. This region represents the number of permutations where both \"2\" and \"4\" are fixed in their natural positions. Since we subtracted this region twice, we have to add it back once (so that the net result is subtracting it once). If we fix \"2\" and \"4\" in their natural positions, there are 4! ways to permute the rest of the integers. So we get 6! - 3x5! + 4!<br \/><br \/>We do similarly for \"2\" and \"6\", and \"4\" and \"6\" (the magenta and cyan regions), and end up with 6! - 3x5! + 4! + 4! + 4! = 8! - 3x5! + 3x4!. (Note that there are 3C2 = 3 ways to pick two even integers at a time from the set of three even integers. Thus, we get 3x4!.)<br \/><br \/>Now we look at the white middle region. We subtracted it three times (when we subtracted each of the circles individually), then added it back three times (when we added the regions where two circles overlap). The net result is that it didn't get subtracted, so we want to subtract it. This region represents all three even integers being fixed in their natural positions at the same time. Then there are 3! ways to permute the remaining integers. We end up with 6! - 3x5! + 3x4! - 3!.<br \/><br \/>Note that this final number represents the grey region OUTSIDE of the three circles. Quick recap: The red circle represents the permutations where \"2\" is in it's natural position; the green and blue circles similarly represent \"4\" and \"6\". The overlapping regions represent permutations where two of the even integers are in their natural positions (e.g. yellow represents \"2\" and \"4\" both in their natural positions.) The center region represents all three even integers being in their natural positions. So the grey region OUTSIDE the circles represents the permutations where none of the even integers is in its natural position. This is what we want, and we calculated the number of permutations represented by this region to be 6! - 3x5! + 3x4! - 3!.<br \/><br \/>The original problem used integers from 1 to 8, so it had even integers 2, 4, 6, and 8. Because of this, we'd need to have four overlapping circles for a diagram -- but you can't draw that in two dimensions. We'd have to have four overlapping spheres in three dimensions, which I can't very easily do on a web page! Better to stick with the simpler example. The procedure is the same if you have more integers; you just have to add and subtract more because there are more overlapping regions. Try it!"},{"id":"urn:lj:livejournal.com:atom1:noam_rion:43584","link":[{"@attributes":{"rel":"alternate","type":"text\/html","href":"https:\/\/noam-rion.livejournal.com\/43584.html"}},{"@attributes":{"rel":"self","type":"text\/xml","href":"https:\/\/noam-rion.livejournal.com\/data\/atom\/?itemid=43584"}}],"title":"Mathematical art","published":"2005-04-19T21:01:43Z","updated":"2011-05-31T02:24:26Z","content":"<a href=\"http:\/\/math.ucsd.edu\/~dwildstr\/photos\/1335-larry-frazier.jpg\" target=\"_blank\" rel=\"nofollow\">Carved<\/a> <a href=\"http:\/\/math.ucsd.edu\/~dwildstr\/photos\/1336-wood-moebius.jpg\" target=\"_blank\" rel=\"nofollow\">wooden<\/a> <a href=\"http:\/\/mathforum.org\/sum95\/math_and\/moebius\/moebius.html\" target=\"_blank\" rel=\"nofollow\">m\u00f6bius strips<\/a>, courtesy of <a href=\"http:\/\/www.livejournal.com\/community\/mathart\/7266.html\" target=\"_blank\">this post<\/a> on <span  class=\"ljuser  i-ljuser  i-ljuser-type-C     \"  data-ljuser=\"mathart\" lj:user=\"mathart\" ><a href=\"https:\/\/mathart.livejournal.com\/profile\/\"  target=\"_self\"  class=\"i-ljuser-profile\" ><img  class=\"i-ljuser-userhead\"  src=\"https:\/\/l-stat.livejournal.net\/img\/community.png?v=556&v=922\" \/><\/a><a href=\"https:\/\/mathart.livejournal.com\/\" class=\"i-ljuser-username\"   target=\"_self\"   ><b>mathart<\/b><\/a><\/span>.<br \/><br \/>Also, beautiful mathematical <a href=\"http:\/\/www.bathsheba.com\/sculpt2\/\" target=\"_blank\" rel=\"nofollow\">metal sculptures<\/a>.<br \/><br \/>I love seeing the tangible beauty in math, especially when I'm studying not very interesting math for exams. (Introductory differential equations, right now. None of the theory, no overarching elegant concepts that fit together and make sense, just a bunch of rules to learn. Introductory applied math courses aren't much fun.)"},{"id":"urn:lj:livejournal.com:atom1:noam_rion:40593","link":[{"@attributes":{"rel":"alternate","type":"text\/html","href":"https:\/\/noam-rion.livejournal.com\/40593.html"}},{"@attributes":{"rel":"self","type":"text\/xml","href":"https:\/\/noam-rion.livejournal.com\/data\/atom\/?itemid=40593"}}],"title":"noam_rion @ 2005-03-16T20:37:00","published":"2005-03-17T04:37:40Z","updated":"2011-05-31T01:47:16Z","content":"A fantastic <a href=\"http:\/\/astronomy.swin.edu.au\/~pbourke\/fractals\/\" target=\"_blank\" rel=\"nofollow\">site<\/a> about fractals. Speaking of beauty in math."},{"id":"urn:lj:livejournal.com:atom1:noam_rion:39808","link":[{"@attributes":{"rel":"alternate","type":"text\/html","href":"https:\/\/noam-rion.livejournal.com\/39808.html"}},{"@attributes":{"rel":"self","type":"text\/xml","href":"https:\/\/noam-rion.livejournal.com\/data\/atom\/?itemid=39808"}}],"title":"Math poetry","published":"2005-03-10T09:02:23Z","updated":"2011-05-31T01:47:17Z","content":"<span  class=\"ljuser  i-ljuser  i-ljuser-type-P     \"  data-ljuser=\"ghareth_3\" lj:user=\"ghareth_3\" ><a href=\"https:\/\/ghareth-3.livejournal.com\/profile\/\"  target=\"_self\"  class=\"i-ljuser-profile\" ><img  class=\"i-ljuser-userhead\"  src=\"https:\/\/l-stat.livejournal.net\/img\/userinfo_v8.png?v=17080&v=922\" \/><\/a><a href=\"https:\/\/ghareth-3.livejournal.com\/\" class=\"i-ljuser-username\"   target=\"_self\"   ><b>ghareth_3<\/b><\/a><\/span> asked about <a href=\"http:\/\/www.livejournal.com\/users\/ghareth_3\/184031.html\" target=\"_blank\">math poetry<\/a>.<br \/><br \/>I've never heard it called math poetry, but there are certainly beautiful equations and proofs. \"Beautiful\" tends to convey elegant, simple, yet non-trivial. A beautiful expression of math is one which states something that matters in a very elegant way.<br \/><br \/><br \/>Probably the expression most widely considered beautiful is the <b><a href=\"http:\/\/mathworld.wolfram.com\/EulerFormula.html\" target=\"_blank\" rel=\"nofollow\">Euler Identity<\/a><\/b>: e<sup>i&pi;<\/sup> + 1 = 0. It relates five of the most important constants in mathematics: e, i (the square root of negative 1, which gives the so-called imaginary or complex numbers), &pi;, 1, and 0. It's very simple, yet the reason these constants are related is complex... and amazing.<br \/><br \/><br \/>I would submit that the <b><a href=\"http:\/\/mathworld.wolfram.com\/PythagoreanTheorem.html\" target=\"_blank\" rel=\"nofollow\">Pythagorean Theorem<\/a><\/b> a<sup>2<\/sup> + b<sup>2<\/sup> = c<sup>2<\/sup> for the lengths of sides of a right triangle is beautiful.<br \/><br \/><br \/>And then there's the golden ratio. If you make a rectangle with one side of length 1 and the other side of length Phi (&Phi; = 1.61803...), the ratio of the longer side to the shorter side is phi (&phi; = 0.61803...). (This is just under two thirds.) This is called the golden rectangle, and &phi; is called the golden ratio or golden section. The golden ratio shows up everywhere, from <a href=\"http:\/\/students.bath.ac.uk\/ma1caab\/phi.html\" target=\"_blank\" rel=\"nofollow\">art<\/a> to <a href=\"http:\/\/goldennumber.net\/face.htm\" target=\"_blank\" rel=\"nofollow\">faces<\/a> to the spirals formed by <a href=\"http:\/\/www.mcs.surrey.ac.uk\/Personal\/R.Knott\/Fibonacci\/fibnat.html#seeds\" target=\"_blank\" rel=\"nofollow\">sunflower seeds<\/a>. The golden ratio is intimately connected to the <a href=\"http:\/\/www.mscs.dal.ca\/Fibonacci\/\" target=\"_blank\" rel=\"nofollow\">Fibonacci Numbers<\/a>: 1, 1, 2, 3, 5, 8, 13, 21, ... where each successive number is the sum of the previous two (8 = 3 + 5; 13 = 5 + 8; 21 = 8 + 13). If you divide each number by its predecessor:<br \/><br \/>13 \/ 8 = 1.625<br \/>21 \/ 13 = 1.615...<br \/>34 \/ 21 = 1.619...<br \/><br \/>You'll find that the result gets closer and closer to the golden ratio.<br \/><br \/><br \/>Mathematical equations and algorithms can also generate beautiful objects, as in <a href=\"http:\/\/sprott.physics.wisc.edu\/fractals\/bookfigs\/FIG5-01.GIF\" target=\"_blank\" rel=\"nofollow\">these<\/a> <a href=\"http:\/\/sprott.physics.wisc.edu\/fractals\/bookfigs\/FIG3-21.GIF\" target=\"_blank\" rel=\"nofollow\">two<\/a> <b><a href=\"http:\/\/sprott.physics.wisc.edu\/sa.htm\" target=\"_blank\" rel=\"nofollow\">strange attractors<\/a><\/b>. (Lots more <a href=\"http:\/\/sprott.physics.wisc.edu\/fractals\/bookfigs\/\" target=\"_blank\" rel=\"nofollow\">here<\/a>.)<br \/><br \/>Or try Scott Draves' exquisite <b><a href=\"http:\/\/draves.org\/pix\/flames\/\" target=\"_blank\" rel=\"nofollow\">fractal flames<\/a><\/b>.<br \/><br \/><br \/><b>Proof by contradiction<\/b> sometimes gives very elegant proofs, as in the case of Euclid's proof that there are infinitely many prime numbers.<br \/><br \/>Prime numbers are numbers that can't be divided by other whole numbers. 7 is prime. 11 is prime. 13 is prime. 101 is prime. And so forth. 63 is not prime because 63 can be divided by 3 to give 31. Stated another way, 61 = 3 times 31. In general terms, a prime number is a number which can't be written as two other numbers multiplied together (ignoring a few details, this is essentially correct).<br \/><br \/>Proof by contradiction works by supposing that the opposite of what you want to prove is actually true. (For example, if I wanted to prove that 2 + 2 = 4, I'd assume that 2 + 2 does not equal 4 (please ignore the fact that this is obviously false -- in a real proof, it would be something more complex that wasn't obviously false). Then I'd start with the assumption that 2 + 2 is not 4, and logically deduce something that obviously doesn't make sense, for example, that 2 = 1. And then I say, if I started with 2 + 2 not equalling 4, and got a wrong answer, then I must have been wrong to say 2 + 2 isn't 4. So 2 + 2 must be 4.)<br \/><br \/>Euclid's proof: Suppose there are only a finite number of prime numbers. Then we could list them in order: first, second, etc. up until the nth and final one. Now, take all n of those, multiply them together, and add 1. I'll call this new number (the one I got by multiplying them and adding 1) m. But then I note that m isn't divisible by the first prime number (it would have a remainder of 1). Similarly, it's not divisible by the second... or any of the other n prime numbers. So it must be a prime number. But I supposed that I had listed all of them, yet I just found one that wasn't on the list! So I was incorrect in supposing that I could list all of them, and therefore there are infinitely many.<br \/><br \/>In more mathematical notation: Suppose there are only a finite number of primes, p<sub>1<\/sub>, p<sub>2<\/sub>, ..., p<sub>n<\/sub>. Let m = p<sub>1<\/sub>p<sub>2<\/sub>...p<sub>n<\/sub> + 1. m is not divisible by p<sub>1<\/sub> since it leaves a remainder of 1. m is not divisible by p<sub>2<\/sub> since it leaves a remainder of 1. ... m is not divisible by any p<sub>i<\/sub>, for 1 &lt;= i &lt;= n. So m must also be prime. But this contradicts the assumption that p<sub>1<\/sub>, p<sub>2<\/sub>, ..., p<sub>n<\/sub> was a complete list of primes. Therefore there are infinitely many primes.<br \/><br \/><br \/>Some other interesting <b><a href=\"http:\/\/www.cut-the-knot.org\/proofs\/index.shtml\" target=\"_blank\" rel=\"nofollow\">proofs<\/a><\/b>."},{"id":"urn:lj:livejournal.com:atom1:noam_rion:39000","link":[{"@attributes":{"rel":"alternate","type":"text\/html","href":"https:\/\/noam-rion.livejournal.com\/39000.html"}},{"@attributes":{"rel":"self","type":"text\/xml","href":"https:\/\/noam-rion.livejournal.com\/data\/atom\/?itemid=39000"}}],"title":"noam_rion @ 2005-02-23T17:09:00","published":"2005-02-24T01:09:38Z","updated":"2011-05-31T01:43:26Z","content":"\"f(x) takes on the value 1 at all the chairs\" -- my professor, regarding functions defined on things other than numbers"},{"id":"urn:lj:livejournal.com:atom1:noam_rion:35067","link":[{"@attributes":{"rel":"alternate","type":"text\/html","href":"https:\/\/noam-rion.livejournal.com\/35067.html"}},{"@attributes":{"rel":"self","type":"text\/xml","href":"https:\/\/noam-rion.livejournal.com\/data\/atom\/?itemid=35067"}}],"title":"Further results on finite differences","published":"2005-01-05T23:06:48Z","updated":"2011-05-31T01:39:02Z","content":"Further to my post <a href=\"http:\/\/www.livejournal.com\/users\/noam_rion\/34795.html\" target=\"_blank\">\"Sequences and differences\"<\/a>, I realized that finite differences are indeed very much like differentiation.<br \/><br \/>First, what is differentiation? It's the study of the slope of a continuous function (a curve on a graph). More specifically, it gives you the slope at a <em>single point<\/em> on the curve. That may not sound like it makes sense, yet, but hold on.<br \/><br \/>Suppose you have a graph that looks like:<br \/><br \/><img src=\"https:\/\/imgprx.livejournal.net\/153ce455ab4e0eec5dca515a035e98a01025af6d7fad6df18839e827f2ebce65\/P2WlxyVijxKvgmFr98lTVEMdsf-ah7h03EGPSqddhsTKvRbWgdKmRkU0BwhpEEJwuw1Zli3XYBAKTwJcyFcR_khA3jjXa6eL_V0SuQ:8GWO2MexPhHXYH25A9gTGQ\" alt=\"x^3 courtesy of gnuplot\" fetchpriority=\"high\"><br \/><br \/>If we pick two points on the graph and draw a (green) line between them,<br \/><br \/><img src=\"https:\/\/imgprx.livejournal.net\/2436f6c7318611fdf9ad539552a2e49aba2b474913d756e8c0f20f7185b5a9a8\/P2WlxyVijxKvgmFr98lTVEMdsf-ah7h03EGPSqddhsTKvRbWgdKmRkU0BwhpEEJwuw1Zli3XYBAKTwJcyFcR_khA3jjXa9aS6FlRqgUvIALrUf4:BAFK8umJxFGyKatSvH4eOQ\" alt=\"secant line\" loading=\"lazy\"><br \/><br \/>we get what is called a secant line. It's easy enough to calculate the slope of the line -- it goes through the points (2, 8) and (4, 64) so from the old formula, slope = rise divided by run, we get slope = (64 - 8) \/ (4 - 2) = 56 \/ 2 = 28.<br \/><br \/>Now, what happens as the second point gets closer to the first point?<br \/><br \/><img src=\"https:\/\/imgprx.livejournal.net\/804bae7d23f707629322b6feaf022300ab6479022f79d0471dc491e2c02244df\/P2WlxyVijxKvgmFr98lTVEMdsf-ah7h03EGPSqddhsTKvRbWgdKmRkU0BwhpEEJwuw1Zli3XYBAKTwJcyFcR_khA3jjXa9aS6FlRqgUzZBj8FKGE:nWiMbVPsbam19JcI6n6QcA\" alt=\"secant line #2\" loading=\"lazy\"><br \/><br \/>See how the slope of the line changes? Now the points are (2, 8) and (3, 27), so the slope is (27 - 8) \/ (3 - 2) = 19.<br \/><br \/>What happens as you keep moving the second point closer and closer to the first? Well, you never have to stop moving it closer. Suppose the second point was at x = 2.1. Then you could pick x = 2.05, which is closer. In other words, there's no end to how close you can make the two points. In fact, you can make them so close you might as well think of them as a single point.<br \/><br \/>Now, as you moved them closer together, the slope of the line changes. So when we talk about the slope at a single point, we're talking about the slope of that line when the two points are arbitrarily close, so close you can think of them as a single point. (This isn't entirely accurate, but conveys the idea.)<br \/><br \/>When you have the two points arbitrarily close, it looks like this:<br \/><br \/><img src=\"https:\/\/imgprx.livejournal.net\/112da34149007541d8234452911a2bd80cba314c76feb5690a4ccae5bd480b93\/P2WlxyVijxKvgmFr98lTVEMdsf-ah7h03EGPSqddhsTKvRbWgdKmRkU0BwhpEEJwuw1Zli3XYBAKTwJcyFcR_khA3jjXa9aV7FRXoR91ZBj8FKGE:3U4VFrbdTx75h7XE5J0LaA\" alt=\"tangent line\" loading=\"lazy\"><br \/><br \/>That's called a tangent line. See how it just touches the curve? And when we talk about the slope of the curve at x = 2 (a single point), we're talking about the slope of the tangent line.<br \/><br \/>Now, why would you want to calculate the slope of a curve? Because the slope is the rate of change of the curve. Say you're driving your car down the highway, and you have a graph of your position (in kilometers, on the vertical) against time (in minutes, on the horizontal):<br \/><br \/><img src=\"https:\/\/imgprx.livejournal.net\/b2e88ca281af51e17fe7c7ccc0672f7129795a986dbd35d3da4dde64b5b82d12\/P2WlxyVijxKvgmFr98lTVEMdsf-ah7h03EGPSqddhsTKvRbWgdKmRkU0BwhpEEJwuw1Zli3XYBAKTwJcyFcR_khA3jjcKOyE6RRatBYjNw:Agp2mn-K4wMq81gX5O_njQ\" alt=\"position-time graph\" loading=\"lazy\"><br \/><br \/>The green tangent line would give you the slope of the graph at a particular time -- that is, it would give you your speed in kilometers per minute at a given instant.<br \/><br \/>Now, what of finite differences? Looking back at our discrete sequence x<sup>2<\/sup>:<br \/><br \/><table rows=\"9\" border=\"0\" cellpadding=\"1\" cellspacing=\"3\">\n<tr><td>1<\/td><td><\/td><td>4<\/td><td><\/td><td>9<\/td><td><\/td><td>16<\/td><td><\/td><td>25<\/td><td><\/td><td>...<\/td><\/tr>\n<tr><td><\/td><td>3<\/td><td><\/td><td>5<\/td><td><\/td><td>7<\/td><td><\/td><td>9<\/td><td><\/td><td>...<\/td><\/tr>\n<\/table><br \/><br \/>The second row is the differences between the numbers in the sequence (the sequence is the first row), i.e.<br \/>4 - 1 = 3<br \/>9 - 4 = 5<br \/>etc.<br \/><br \/>But, consider that each successive number in the sequence is a \"run\" of length 1: x = 1, x = 2, x = 3, ... And the \"rise\" is the difference between successive numbers. So the \"slope\" between x = 2 and x = 3 is<br \/><br \/>(3<sup>2<\/sup> - 2<sup>2<\/sup>) \/ (3 - 2) = (9 - 4) \/ (1) = 5<br \/><br \/>On a graph:<br \/><br \/><img src=\"https:\/\/imgprx.livejournal.net\/5f4273a4c06023cbb7241c7cadde8c5e954fcf73d6f8a3fca7318094cc6547a9\/P2WlxyVijxKvgmFr98lTVEMdsf-ah7h03EGPSqddhsTKvRbWgdKmRkU0BwhpEEJwuw1Zli3XYBAKTwJcyFcR_khA3jjXataF5ElTthR1LwHgHPOc-Mteji9N:x-9Vwl7KnXF8Eot-A84wuA\" alt=\"position-time graph\" loading=\"lazy\"><br \/><br \/>It's not a smooth curve when you connect the discrete points with lines (see how it has corners at the points?), but the finite difference (i.e. the difference of one number from the next) does indeed give you the slope of the lines between points.<br \/><br \/>(Note that there isn't anything comparable to talking about the slope AT a single point in this case, since we're not dealing with a continuous function.)"},{"id":"urn:lj:livejournal.com:atom1:noam_rion:34795","link":[{"@attributes":{"rel":"alternate","type":"text\/html","href":"https:\/\/noam-rion.livejournal.com\/34795.html"}},{"@attributes":{"rel":"self","type":"text\/xml","href":"https:\/\/noam-rion.livejournal.com\/data\/atom\/?itemid=34795"}}],"title":"Sequences and differences","published":"2005-01-05T06:26:55Z","updated":"2011-05-31T01:39:03Z","content":"While I was in Portland, <span  class=\"ljuser  i-ljuser  i-ljuser-type-P     \"  data-ljuser=\"vruba\" lj:user=\"vruba\" ><a href=\"https:\/\/vruba.livejournal.com\/profile\/\"  target=\"_self\"  class=\"i-ljuser-profile\" ><img  class=\"i-ljuser-userhead\"  src=\"https:\/\/l-stat.livejournal.net\/img\/userinfo_v8.png?v=17080&v=922\" \/><\/a><a href=\"https:\/\/vruba.livejournal.com\/\" class=\"i-ljuser-username\"   target=\"_self\"   ><b>vruba<\/b><\/a><\/span> introduced me to a curiosity: Take the sequence x<sup>2<\/sup>:<br \/><br \/>1, 4, 9, 16, 25, ... (i.e. 1 squared, 2 squared, 3 squared, ...)<br \/><br \/>Now, subtract each number from the next one:<br \/><br \/>4 - 1 = 3<br \/>9 - 4 = 5<br \/>16 - 9 = 7<br \/>...<br \/><br \/>to get this sequence:<br \/><br \/>3, 5, 7, 9, ...<br \/><br \/>Repeat this, and you end up with:<br \/><br \/>2, 2, 2, 2, ...<br \/><br \/>Put together in a table, this looks like:<br \/><br \/><table rows=\"9\" border=\"0\" cellpadding=\"1\" cellspacing=\"3\">\n<tr><td>1<\/td><td><\/td><td>4<\/td><td><\/td><td>9<\/td><td><\/td><td>16<\/td><td><\/td><td>25<\/td><td><\/td><td>...<\/td><\/tr>\n<tr><td><\/td><td>3<\/td><td><\/td><td>5<\/td><td><\/td><td>7<\/td><td><\/td><td>9<\/td><td><\/td><td>...<\/td><\/tr>\n<tr><td><\/td><td><\/td><td>2<\/td><td><\/td><td>2<\/td><td><\/td><td>2<\/td><td><\/td><td>...<\/td><\/tr>\n<\/table><br \/><br \/>Now, <span  class=\"ljuser  i-ljuser  i-ljuser-type-P     \"  data-ljuser=\"vruba\" lj:user=\"vruba\" ><a href=\"https:\/\/vruba.livejournal.com\/profile\/\"  target=\"_self\"  class=\"i-ljuser-profile\" ><img  class=\"i-ljuser-userhead\"  src=\"https:\/\/l-stat.livejournal.net\/img\/userinfo_v8.png?v=17080&v=922\" \/><\/a><a href=\"https:\/\/vruba.livejournal.com\/\" class=\"i-ljuser-username\"   target=\"_self\"   ><b>vruba<\/b><\/a><\/span> pointed out that by assuming the bottom row is always going to consist of 2s (which it looks like it will), we can then calculate the next number in the original sequence. The 2s in the bottom row tell us that the difference between the numbers in the middle row is always 2... so the next number in the middle row should be 9 + 2, or 11:<br \/><br \/><table border=\"0\" cellpadding=\"1\" cellspacing=\"3\">\n<tr><td>1<\/td><td><\/td><td>4<\/td><td><\/td><td>9<\/td><td><\/td><td>16<\/td><td><\/td><td>25<\/td><td><\/td><td>...<\/td><\/tr>\n<tr><td><\/td><td>3<\/td><td><\/td><td>5<\/td><td><\/td><td>7<\/td><td><\/td><td>9<\/td><td><\/td><td>11<\/td><td><\/td><td>...<\/td><\/tr>\n<tr><td><\/td><td><\/td><td>2<\/td><td><\/td><td>2<\/td><td><\/td><td>2<\/td><td><\/td><td>2<\/td><td><\/td><td>...<\/td><\/tr>\n<\/table><br \/><br \/>But then that tells us that the difference between 25 and the next number in the first row is 11... so the next number in the first row shoule be 25 + 11, or 36:<br \/><br \/><table border=\"0\" cellpadding=\"1\" cellspacing=\"3\">\n<tr><td>1<\/td><td><\/td><td>4<\/td><td><\/td><td>9<\/td><td><\/td><td>16<\/td><td><\/td><td>25<\/td><td><\/td><td>36<\/td><td><\/td><td>...<\/td><\/tr>\n<tr><td><\/td><td>3<\/td><td><\/td><td>5<\/td><td><\/td><td>7<\/td><td><\/td><td>9<\/td><td><\/td><td>11<\/td><td><\/td><td>...<\/td><\/tr>\n<tr><td><\/td><td><\/td><td>2<\/td><td><\/td><td>2<\/td><td><\/td><td>2<\/td><td><\/td><td>2<\/td><td><\/td><td>...<\/td><\/tr>\n<\/table><br \/><br \/>And indeed, 36 is 6 squared, the next number in the sequence. Now, this way of figuring out the sequence might seem a little convoluted, but consider this. <em>You<\/em> might immediately recognize the first row as being squares of numbers, but a computer wouldn't. But, if you gave a computer the first row, and it used this method, it could figure out the rest of the sequence without knowing anything about the sequence other than the few numbers you gave it.<br \/><br \/>I decided to play around with this technique some more, and found some very interesting things.<br \/><br \/>First, it works for more than x<sup>2<\/sup>. Here's x<sup>3<\/sup>:<br \/><br \/><table border=\"0\" cellpadding=\"1\" cellspacing=\"3\">\n<tr><td>1<\/td><td><\/td><td>8<\/td><td><\/td><td>27<\/td><td><\/td><td>64<\/td><td><\/td><td>125<\/td><td><\/td><td>216<\/td><td><\/td><td>...<\/td><\/tr>\n<tr><td><\/td><td>7<\/td><td><\/td><td>19<\/td><td><\/td><td>37<\/td><td><\/td><td>61<\/td><td><\/td><td>91<\/td><td><\/td><td>...<\/td><\/tr>\n<tr><td><\/td><td><\/td><td>12<\/td><td><\/td><td>18<\/td><td><\/td><td>24<\/td><td><\/td><td>30<\/td><td><\/td><td>...<\/td><\/tr>\n<tr><td><\/td><td><\/td><td><\/td><td>6<\/td><td><\/td><td>6<\/td><td><\/td><td>6<\/td><td><\/td><td>...<\/td><\/tr>\n<\/table><br \/><br \/>Again, we could figure out what the next number in the first row is by working up from the bottom row (this is called \"extrapolation\").<br \/><br \/>I started trying this for other things, such as x<sup>4<\/sup> and x<sup>5<\/sup>, and noticed two patterns.<br \/><br \/>The number of rows needed before the numbers become the same (\"constant\") seems to the be the power of x plus 1. So for x<sup>2<\/sup> it takes three rows. For x<sup>3<\/sup> it takes four rows. And so on.<br \/><br \/>Also, the constant number that you end up with appears to be the factorial of the power. (The best way to explain a factorial is by example. 5 factorial, written 5!, means 5*4*3*2*1. 6! = 6*5*4*3*2*1. It's just multiplication.) If you have x<sup>3<\/sup>, you end up with 3*2*1, or 6. If you have x<sup>5<\/sup> you get 5!, which is 120.<br \/><br \/>Curious, no?<br \/><br \/>So I started looking for the underlying pattern. I tried looking at three consecutive, arbitrary numbers -- x, (x+1), and (x+2) -- and the sequence x<sup>2<\/sup>. Then I looked at x<sup>3<\/sup>, where it gets more interesting:<br \/><br \/><table border=\"0\" cellpadding=\"1\" cellspacing=\"3\">\n<tr><td>x<sup>3<\/sup><\/td><td><\/td><td>(x+1)<sup>3<\/sup><\/td><td><\/td><td>(x+2)<sup>3<\/sup><\/td><td><\/td><td>(x+3)<sup>3<\/sup><\/td><td><\/td><td>...<\/td><\/tr>\n<\/table><br \/><br \/>I expanded these out and subtracted:<br \/><br \/>(x+1)<sup>3<\/sup> - x<sup>3<\/sup> = (x<sup>3<\/sup> + 3x<sup>2<\/sup> + 3x + 1) - x<sup>3<\/sup> = 3x<sup>2<\/sup> + 3x + 1<br \/><br \/>and obtained:<br \/><br \/><table border=\"0\" cellpadding=\"1\" cellspacing=\"3\">\n<tr><td align=\"center\">x<sup>3<\/sup><\/td><td align=\"center\"><\/td><td align=\"center\">(x+1)<sup>3<\/sup><\/td><td align=\"center\"><\/td><td align=\"center\">(x+2)<sup>3<\/sup><\/td><td align=\"center\"><\/td><td align=\"center\">(x+3)<sup>3<\/sup><\/td><td align=\"center\"><\/td><td align=\"center\">...<\/td><\/tr>\n<tr><td align=\"center\"><\/td><td align=\"center\">3x<sup>2<\/sup> + 3x + 1<\/td><td align=\"center\"><\/td><td align=\"center\">3x<sup>2<\/sup> + 9x + 7<\/td><td align=\"center\"><\/td><td align=\"center\">3x<sup>2<\/sup> + 15x + 19<\/td><td align=\"center\"><\/td><td align=\"center\">...<\/td><\/tr>\n<tr><td align=\"center\"><\/td><td align=\"center\"><\/td><td align=\"center\">6x + 6<\/td><td align=\"center\"><\/td><td align=\"center\">6x + 12<\/td><td align=\"center\"><\/td><td align=\"center\">...<\/td><\/tr>\n<tr><td align=\"center\"><\/td><td align=\"center\"><\/td><td align=\"center\"><\/td><td align=\"center\">6<\/td><td align=\"center\"><\/td><td align=\"center\">...<\/td><\/tr>\n<\/table><br \/><br \/>See how the power goes down by one in each row, and how the coefficient on the first term (starting in the second row) is 3, then 3*2, then 3*2*1? At this point, I started wondering if it has anything to do with differentiation, since you see a similar pattern there. But I couldn't figure out how this would have anything to do with calculus. We pulled out a calculus textbook and I was going to play around with it, but I got sidetracked explaining limits and differentiation to Rebecca.<br \/><br \/>I wrote a little <a href=\"http:\/\/community.nbtsc.org\/~noam\/code\/difference.pl\" target=\"_blank\" rel=\"nofollow\">perl script<\/a> to create these sort of tables for me, and by playing around found out that this behaviour happens for any polynomial, and that it's only the highest power that affects what the final constant will be. (Note that if there's a coefficient on the highest-power term, it carries through and the eventual constant is multiplied by the coefficient.)<br \/><br \/>I played around some more, and tried to research it on the net, but didn't turn up anything until today.<br \/><br \/>Turns out that this sort of method is called a <a href=\"http:\/\/mathworld.wolfram.com\/FiniteDifference.html\" target=\"_blank\" rel=\"nofollow\">Finite Difference<\/a> and it is the discrete analogue of differentiation.<br \/><br \/>(Discrete means talking about something at specific points. e.g. the sequence of x<sup>2<\/sup> I was using above is what you get when you take x=1, x=2, x=3, ... and square them. If you plot x<sup>2<\/sup> on a graph discretely (x on the horizontal, x<sup>2<\/sup> on the vertical) you get:<br \/><br \/><img src=\"https:\/\/imgprx.livejournal.net\/d325d4be52a7ffeca1324accddf3efac720f0232626d30ea239812d40f9ae2f2\/P2WlxyVijxKvgmFr98lTVEMdsf-ah7h03EGPSqddhsTKvRbWgdKmRkU0BwhpEEJwuw1Zli3XYBAKTwJcyFcR_khA3zjXataF5ElTthR1L1zmA-Tbqw:LNZS3CFrMMCGIpXrP7zXSw\" alt=\"x^2 discrete courtesy of gnuplot\" fetchpriority=\"high\"><br \/><br \/>Whereas if you treat x<sup>2<\/sup> continously, and you draw the graph, you get:<br \/><br \/><img src=\"https:\/\/imgprx.livejournal.net\/d5a5dd54bac3f566b616d1d50c1ea851d982334513ff2c0c5ad889cf6987a07f\/P2WlxyVijxKvgmFr98lTVEMdsf-ah7h03EGPSqddhsTKvRbWgdKmRkU0BwhpEEJwuw1Zli3XYBAKTwJcyFcR_khA3zjXataC4lRErR90JQf_XemJsYNT:-VyJMe0bDoXZW7my4odx3g\" alt=\"x^2 continous courtesy of gnuplot\" loading=\"lazy\"><br \/><br \/>See how it's all points, not just certain points?)<br \/><br \/>Well, finite differences are what you do on discrete functions, whereas differentiation is what you do on continuous functions. So I was right, there is a connection.<br \/><br \/>I found several other useful pages: <br \/><a href=\"http:\/\/www.jimloy.com\/algebra\/finite.htm\" target=\"_blank\" rel=\"nofollow\">Figuring out functions using finite differences<\/a><br \/><a href=\"http:\/\/www.math.ilstu.edu\/day\/courses\/old\/305\/contentfinitedifferences.html\" target=\"_blank\" rel=\"nofollow\">Another explanation<\/a><br \/><br \/>None of those directly explain why you get the factorial of the highest power, but I think it could be explained fairly easily (let me know if you figure it out). I haven't tried playing with it as a difference of polynomials in general form (a<sub>k<\/sub>x<sup>k<\/sup> + a<sub>k-1<\/sub>x<sup>k-1<\/sup> + ... + a<sub>2<\/sub>x<sup>2<\/sup> + a<sub>1<\/sub>x + a<sub>0<\/sub> where a<sub>j<\/sub> is the coefficient of the j<sup>th<\/sup> term) yet; I suspect this would yield the result. Similar to proving the power rule in calculus. Actually, I'm sure that it could be shown that addition isn't affected across finite differences, so you could look at the polynomial term by term, and prove that a<sub>k<\/sub>x<sup>k<\/sup> becomes k*a<sub>k<\/sub>x<sup>k-1<\/sup>.<br \/><br \/>Sorry, that got a bit technical at the end... ask me if you want a simpler breakdown or explanation of anything in here."}]}