These fields are all optional and need only be supplied if you would like a direct reply. Subject Your email address Your real name

You must answer this! If you don't, my spam filtering will ensure that I never see your email. What's 8 plus five (in digits only)?

Please make your changes here and then
Editing tips and layout rules.
File: SquareRootByLongDivision ''' <link rel="alternate" type="application/rss+xml" ''' href="/rss.xml" title="RSS Feed"> ********> width="25%" |>> ''' <a title="Subscribe to my feed" ''' rel="alternate" ''' href="https://www.solipsys.co.uk/rss.xml"> ''' <img style="border-width: 0px;" ''' src="https://www.feedburner.com/fb/images/pub/feed-icon32x32.png" ''' align="middle" ''' alt="" />Subscribe!</a> _ ''' <a href="https://twitter.com/ColinTheMathmo"> ''' <img src="https://www.solipsys.co.uk/new/images/TwitterButton.png" ''' title="By: TwitterButtons.net" ''' width="212" height="69" ''' alt="@ColinTheMathmo" ''' /></a> <<| ---- My latest posts can be found here: * ColinsBlog ---- Previous blog posts: * BeyondTheBoundary * FillInTheGaps * SoftwareChecklist * NASASpaceCrews * TheBirthdayParadox * TheTrapeziumConundrum * RevisitingTheAnt * TheAntAndTheRubberBand * IrrationalsExist * MultipleChoiceProbabilityPuzzle * RandomEratosthenes * WrappingUpSquareDissection * DissectingASquarePart2 * DissectingACircle * DissectingASquare * AnOddityInTennis * DecisionTreeForTennis * DecisionTreesInGames * AMatterOfConvention * DoYouNourishOrTarnish * BinarySearchReconsidered * TwoEqualsFour * TheLostPropertyOffice * TheForgivingUserInterface * SettingUpRSS * WithdrawingFromHackerNews ---- Additionally, some earlier writings: * RandomWritings. * ColinsBlog2010 * ColinsBlog2009 * ColinsBlog2008 * ColinsBlog2007 * ColinsBlogBefore2007 ''' <img src="/cgi-bin/CountHits.py?SquareRootByLongDivision" alt="" /> ******** !!! SquareRootByLongDivision - 2014/08/11 [[[>40 Just as one can often solve a quadratic "by inspection" rather than turning to the full generality of the usual formula, so in this case there are easier ways to solve this problem than using the full power of square roots by long division. But on this occasion this is how I did it, and it serves as a nice example, so I thought I'd share it. ]]] The other day on Twitter, Paul Salomon ''' (<a href="https://twitter.com/lostinrecursion">@lostinrecursion</a>) asked: ''' <ul><li><a href="https://twitter.com/lostinrecursion/status/498204696016715777"> ''' Is the product of 4 consecutive <br> ''' positive integers always one <br> ''' less than a square?</a></li></ul> Good question. The answer is yes, and I solved it using a technique Paul didn't know: * Yes. _ If /n/ is the second integer, the square root _ is EQN:n^2+n-1. Interestingly, I used the algebraic _ version of square root by long division. * Show me your work will you? I don't think _ I know this algebraic square root business. OK. If you're interested in the actual algorithm then simply skip to the end. However, I'm going to derive the algorithm, starting with long division. !!! Long Division So let's start with the division problem, computing 999999 divided by 7. Apparently modern teaching doesn't use long division any more. Instead they use a thing called "chunking". In fact, "chunking" is nothing more than long division done with more guesses and less formality. [[[< {{{ 1 +------------- 7 | 9 9 9 9 9 9 7 --- 2 9 9 9 9 9 }}} ]]] So we start by ignoring everything except the most significant part. We ask how many 7s we can take out from the first digit. The answer is just one. So we have |>> {{{ 999999 = 700000 + 299999 }}} <<| We can see that laid out formally at right. That table then says that |>> {{{ 9999999 / 7 = 100000 + 299999/7 }}} <<| We now iterate. We can remove 4 chunks of 7 from 29, so that's removing 40000 lots of 7 from 299999. Again, we lay that out in the tabular fashion: |>> [[[ {{{ 1 4 +------------- 7 | 9 9 9 9 9 9 7 --- 2 9 9 9 9 9 2 8 ----- 1 9 9 9 9 }}} ]]] <<| So we are, at each stage, deciding what the next digit should be, multiply by 7, subtract from the remaining amount, and then repeat. This is laid out in a formal, tabular fashion. At each stage we have an intermediate sum that makes sense. |>> [[[ {{{ 1 4 2 8 . . +------------- 7 | 9 9 9 9 9 9 7 --- 2 9 9 9 9 9 2 8 ----- 1 9 9 9 9 1 4 ----- 5 9 9 9 5 6 ----- 3 9 9 }}} ]]] <<| Here we can see that 999999 = 7 * 142800 + 399. At each stage we reduce the remainder, subtracting a chunk of 7s from it. !!! Polynomial division This can be used for polynomials too. So, for example, here we start: |>> [[[ {{{ +--------------------------- x^2 + x - 3 | x^4 - x^3 - 3x^2 + 8x - 5 }}} ]]] <<| The first term has to be multiplied by EQN:x^2 so we end up cancelling the EQN:x^4, so the first term has to be EQN:x^2. Multiply and subtract - the first term cancels: |>> [[[ {{{ x^2 +--------------------------- x^2 + x - 3 | x^4 - x^3 - 3x^2 + 8x - 5 x^4 + x^3 - 3x^2 ------------------ -2x^3 + 0x^2 }}} ]]] <<| We've magically vanished the EQN:x^2 term as well, although that will come back in a moment. We bring down the "8x" and ask what we need that will cancel the EQN:2x^3 term. Clearly that will have to be "2x", and so we continue ... |>> [[[ {{{ x^2 - 2x + 2 +--------------------------- x^2 + x - 3 | x^4 - x^3 - 3x^2 + 8x - 5 x^4 + x^3 - 3x^2 ------------------ -2x^3 + 8x -2x^3 - 2x^2 + 6x ------------------- + 2x^2 + 2x - 5 2x^2 + 2x - 6 ------------------- 1 }}} ]]] <<| As you can see, we can divide EQN:x^4-x^3-3x^2+8x-5 by EQN:x^2+x-3 and we get EQN:x^2-2x+2 with a remainder of 1. So we can perform long division with polynomials in exactly the same way as we can perform long division with numbers, and in effect, it's just a formalised way of doing "chunking." !!! Square roots by Long Division So, on to Square Roots By Long Division ... We do the same thing. We remove as much as we can from the leading portion, hang on to the remainder, and then carry on. At each stage we have an equation giving the current status. Let's compute the square root of 677329. We start by thinking of it as EQN:67*10^4+7329. That means the square root will be 800 and a bit (because the square root of 67 is 8 and a bit, and the square root of EQN:10^4 is 100.) So EQN:\sqrt{677329} is (800 and a bit). Let's put that in a table: |>> [[[ {{{ 8 . . ,--------------- v 6 7 7 3 2 9 6 4 ----- 3 7 3 2 9 }}} ]]] <<| So, specifically, EQN:677329=800^2+37329. Now let's go for the next phase. Drop the last two digits of 37329 to get 373. We computed the square root of 6773 as 80 and a bit, so we have EQN:(80+x)^2=6400+2\times80\times{x}+x^2. We've already removed the 6400 to be left with 373, so we think of that 373 as the EQN:(2\times80+x)\times{x}. We need to find a digit "d" such that "16d" (that's one hundred and sixty-d) times "d" is as big as possible, but no bigger than 373. In other words, find the maximum value of "d" such that EQN:(160+d)\times{d}\leq{373}. |>> [[[ {{{ 8 d . ,--------------- v 6 7 7 3 2 9 6 4 ----- 16d 3 7 3 }}} ]]] <<| The "16" at left in that table is twice 8. So we want a "d" such that "16d" times "d" is as close as possible to, but no bigger than, 373. Clearly the best value is "2". We insert the value "2", multiply, and subtract: |>> [[[ {{{ 8 2 . ,--------------- v 6 7 7 3 2 9 6 4 ----- 3 7 3 162 3 2 4 -------- 4 9 2 9 }}} ]]] <<| Now again, we double the answer so far (giving 164) and find a digit that we can put on the end, then multiply by, to get something as close as possible but no bigger than 4929. |>> [[[ {{{ 8 2 d ,--------------- v 6 7 7 3 2 9 6 4 ----- 162 3 7 3 3 2 4 -------- 4 9 2 9 164d ? ? ? ? }}} ]]] <<| So we need to the largest "d" such that EQN:(1640+d)\times{d}\leq{4929}. Just looking at the first two digits gives us a first approximation. 16 goes into 49 three and a bit times, so let's try 3: |>> [[[ {{{ 8 2 3 ,--------------- v 6 7 7 3 2 9 6 4 ----- 162 3 7 3 3 2 4 -------- 4 9 2 9 1643 4 9 2 9 ---------- 0 }}} ]]] <<| It goes exactly, the remainder is zero, and so we've computed our square root. Now let's do that with 2: |>> [[[ {{{ 1 . 4 1 4 2 ,------------------------------- v 2 . 0 0 0 0 0 0 0 0 0 0 1 --- 1 . 0 0 2 4 . 9 6 --------- 4 0 0 2 8 1 2 8 1 -------- 1 1 9 0 0 2 8 2 4 1 1 2 9 6 ------------- 6 0 4 0 0 2 8 2 8 2 5 6 5 6 4 ------------- 3 8 3 6 0 0 }}} ]]] <<| Here we are looking for the next digit. Our equation so far is that EQN:\sqrt{2}=(1.4142+x)^2. We are part way, and we can see that EQN:2=(1.4142)^2+0.00003836. We double the bit we have so far, multiply by 10, then find the digit to put on the end, multiply by, and get close to 0.00383600. So "28284x" times "x" has to be close to, but not exceed, 383600. The value for "x" has to be 1, and so we continue. !!! Polynomial Square Roots by Long Division And so, back to the original question. * Is the product of 4 consecutive _ positive integers always one _ less than a square? Let's take the product of 4 consecutive positive integers: * EQN:(n-1)n(n+1)(n+2)=n^4+2n^3-n^2-2n Add one: * EQN:(n-1)n(n+1)(n+2)+1=n^4+2n^3-n^2-2n+1 And now we take the square root: |>> [[[ {{{ n^2 ,--------------------------- v n^4 + 2n^3 - n^2 - 2n + 1 n^2 n^4 ----- 0 + 2n^3 - n^2 }}} ]]] <<| Remember, we double what we have so far, and then work out what the next term will be: |>> [[[ {{{ n^2 + X ,--------------------------- v n^4 + 2n^3 - n^2 - 2n + 1 n^2 n^4 ----- 2n^2 + X 0 + 2n^3 - n^2 }}} ]]] <<| Whatever X is going to be, we have to get rid of the EQN:2n^3 term when we multiply by EQN:2n^2, so there's only one option - X has to be /n./ |>> [[[ {{{ n^2 + n ,--------------------------- v n^4 + 2n^3 - n^2 - 2n + 1 n^2 n^4 ----- 2n^2 + n 0 + 2n^3 - n^2 2n^3 + n^2 ------------ -2n^2 - 2n + 1 }}} ]]] <<| Double the answer so far, and work out what to extend by: |>> [[[ {{{ n^2 + n + X ,--------------------------- v n^4 + 2n^3 - n^2 - 2n + 1 n^2 n^4 ----- 2n^2 + n 0 + 2n^3 - n^2 2n^3 + n^2 ------------ 2n^2 + 2n + X -2n^2 - 2n + 1 }}} ]]] <<| We can see that X has to be -1 and we get this: |>> [[[ {{{ n^2 + n - 1 ,--------------------------- v n^4 + 2n^3 - n^2 - 2n + 1 n^2 n^4 ----- 2n^2 + n 0 + 2n^3 - n^2 2n^3 + n^2 ------------ 2n^2 + 2n - 1 -2n^2 - 2n + 1 -2n^2 - 2n + 1 ---------------- 0 }}} ]]] <<| .... and there's no remainder. Therefore |>> [[[ EQN:\sqrt{n^4+2n^3-n^2-2n+1}\quad={\quad}n^2+n-1 ]]] <<| And we're done. So, a final example. Let's take the square root of this: |>> [[[ {{{ ,--------------------------------- v 4n^4 - 12n^3 - 11n^2 + 30n + 24 }}} ]]] <<| Here it is ... |>> [[[ {{{ 2n^2 - 3n - 5 ,--------------------------------- v 4n^4 - 12n^3 - 11n^2 + 30n + 24 2n^2 4n^4 ------ 0 - 12n^3 - 11n^2 4n^2 - 3n - 12n^3 + 9n^2 ------------------- - 20n^2 + 30n + 24 4n^2 - 6n - 5 - 20n^2 + 30n + 25 -------------------- - 1 }}} ]]] <<| So: |>> EQN:4n^4-12n^3-11n^2+30n+24{\quad}={\quad}(2n^2-3n-5)^2-1 <<| and hence it's the difference of two squares. That means we have the factorisation: |>> EQN:4n^4-12n^3-11n^2+30n+24{\quad}={\quad}(2n^2-3n-5+1)\times(2n^2-3n-5-1) <<| or |>> EQN:4n^4-12n^3-11n^2+30n+24{\quad}={\quad}(2n^2-3n-4)\times(2n^2-3n-6) <<| ---- !!! Credits ... Hat tips to both Colin Beveridge ''' (<a href="https://twitter.com/icecolbeveridge">@icecolbeveridge</a>) and James Tauber ''' (<a href="https://twitter.com/jtauber">@jtauber</a>) for useful feedback and helpful suggestions while writing this. ---- |>> | |>> <<<< Prev <<<< ---- BeyondTheBoundary <<| | : | |>> >>>> Next >>>> ---- OnTheRack ... <<| | ---- ********> ''' <a href="https://twitter.com/ColinTheMathmo">You should follow me on twitter</a> ******** ''' <a href="https://twitter.com/ColinTheMathmo"> ''' <img src="https://www.solipsys.co.uk/new/images/TwitterButton.png" ''' title="By: TwitterButtons.net" ''' width="212" height="69" ''' alt="@ColinTheMathmo" ''' /></a> ********< <<| ---- !! Comments I've decided no longer to include comments directly via the Disqus (or any other) system. Instead, I'd be more than delighted to get emails from people who wish to make comments or engage in discussion. Comments will then be integrated into the page as and when they are appropriate. If the number of emails/comments gets too large to handle then I might return to a semi-automated system. That's looking increasingly unlikely. ********<