The Tower of Hanoi And two (three?) clever solutions

 

Back awhile, in a blog about Fibonacci, I mentioned that Edouard Lucas had created the "Tower of Hanoi" game and received comments and mail from people who thought I must be mistaken because the game was "really old". Turns out, it really isn't, but just the creation of a master mathematical story teller. Here are some notes about the man, and the history of the Towers of Hanoi from my Math Words Etymology page.

Also, you can find a java applet to play the game at this site... and if you've never done it (where HAVE you been?) don't start with all 12 discs, that takes 4095 moves to solve (see below).

The Lucas sequence is similar to the Fibonacci sequence. The Lucas sequence is given by {1, 3, 4, 7, 11, 18, ...} . Each term is the sum of the two previous numbers, as in the Fibonacci sequence. Just as in the Fibonacci sequence, the limit of the ratio of consecutive terms is the Golden Ratio. The Lucas numbers can also be constructed from the Fibonacci numbers by the function Ln = Fn-1 + Fn+1, thus the fifth Lucas number, 11, is the sum of the fourth and sixth fibonacci numbers (3+8).

The sequence is named for Edouard Lucas, a French mathematician of the later half of the nineteenth century. He used his sequence and the Fibonacci sequence to develop techniques for testing for prime numbers. Lucas is also remembered for his unusual death, caused by a waiter dropping a plate which shattered sending a piece of plate into his neck. Lucas died several days later from a deadly inflamation of the skin and subcutaneous tissue caused by streptococcus. The disease, officially listed as erysipelas (from the Greek for "red skin") was more commonly known as "Saint Anthony's Fire".


Lucas was also the creator of a popular puzzle called The Tower of Hanoi in 1883. You can see the original box cover above. Note that the author on the box cover is Professor N. Claus de Siam, an anagram of Lucas d' Amiens (his home). The professors college, Li-Sou-Stian, is also an anagram for "Lycee Saint-Louis" where Lucas worked.

France was building an Empire in Indochina (the peninsula stretching from Burma to Viet Nam and Malaysia) and the "mysterious East" was a very fashionable topic. Lucas created a legend (some say he embellished an existing one, but I can find no earlier record of one) of monks working to move 64 gold disks from one of three diamond points to another after which the world would end. The solution for a tower of n disks taks 2n -1 moves, so the game often had less than the 64 disks of the legend. Solving the 64 disks at one move a second would require 18,446,744,073,709,551,615 seconds, which at 31,536,000 seconds a year would take 584 Billion years. (and you thought Monopoly took a long time to finish).  The reference in his instructions to Buddhist monks in a temple in Bernares(Varanasi),  India seems, even now, to make people believe there was such an activity taking place.  Varanasi is considered the holiest of the seven sacred cities (Sapta Puri) in Hinduism, and Jainism, and is important to Buddhism because it was in nearby Sarnath that Buddha gave his first teaching after attaining enlightenment, in which he taught the four noble truths and the teachings associated with it. There is a Buddhist temple there with many relics of the Buddha, but so far as I can find, no monks moving golden disks on needles.

Students/teachers interested in further explorations of the history and math of the famous game should visit the work of Paul K Stockmeyer who maintains the page with the cover illustration mentioned above, and his Papers and bibliography on the Tower of Hanoi problem.

Lucas developed several other mathematical games of his on, including the well known children's pastime of dots and boxes (which he called  La Pipopipette), which on large boards is still essentially unsolved, I believe.  He also (probably) invented a Mancala type game called Tchuka Ruma.

Lucas is also remembered for suffering an unusual death.  At a banquet in 1891  a waiter dropped a dining plate and one of the pieces cut Lucas on the neck and cheek. Within a week he was dead from what was called the "Holy Fire" or St Anthony's Fire, a form of septicemia.

A while after I wrote the above, I learned a little more, and so:

Just browsing through Wikipedia, and they show a solution to the Towers of Hanoi puzzle that I had never seen using a ruler as a solution key.

If you have been off planet for the last 130 years and don't know the Towers problem, you can play online here. You might try that first, and set the number of discs to 6 so that it matches the solution shown below.

And for those who know the game but just want to see how a ruler is used, here is the graphic.



For any move, just move the disc whose size compares to the marks on the ruler. For instance the first five marks on a ruler marked in 32^nds would be 1/32, 1/16/ 3/32, 1/8, 5/32.... The denominators tell you which disk to move. The largest denominator (smallest scale) goes with the smallest disc, etc. If you then apply two fundamentals of any solution, always move the smallest disc From rod A, to B to C and back to A in a cycle, and never put a bigger disc on a smaller one, then you have a solution... That's easier than Gray codes isn't it.

Why have I never encountered this before? The connection was made in 1956 by Donald W. Crow, in relation to traversing the vertices of a cube in n-dimensions[ D. W. Crowe, The n-dimensional cube and the tower of Hanoi, Amer. Math. Monthly, 63 (1956), 29-30.]


POSTSCRIPT:::: For another really insightful solution (maybe the best of them all) See the comment by Jeffo....Thanks guy, why don't I see ideas like that?

Jeffo said...

If the rods are placed in a circular arrangement instead of linear, then a correct solution will involve always moving the smallest disk one rod clockwise every other move. The alternate moves are forced.    

Things I Learned on the Road-II

Things I Learned on the Road (and long afterward, at home)

Some notes from a trip a few years ago with some updates from recent readings.... enjoy (or if this is your second time, re-enjoy)
Newsflash!! Spanish Moss is NOT Spanish...AND (wait for it.....) it is NOT moss... talk about bad names... The French gave it the "Spanish" name as an insult???? 

Guess you had to be there. Probably an old Monty Python skit about that, "Your Moss is Spanish and your Mother smells of Elderberries!!!". Ok, and the moss part, NOPE... its an epiphitic (gets its food from the air) bromeliad (cousin of the pineapple). Now you know

I also was reminded that people do things that seem really strange. In the middle of the road in Enterprise Alabama, there is a statue to the Boll Weevil. Now if you are really a city child and know nothing of the agricultural history of the south, the weevil wiped out many cotton farmers in the south around the beginning of the 20th century. The idea of a monument to the weevil in Alabama would seem like a giant grasshopper in Salt Lake City, Utah.  (Just a few weeks ago in 2023 a lot of folks in Salt Lake area may have been hoping for another seagull miracle when the National Weather Service reported a swarm of grasshoppers on their radar screen.  After a day of investigation, the culprit turned out to be the chaff from the flyboys out of Nellis AFB) 

Ok, So a few years later I came across a reason for this at the Futility Closet blog by Greg Ross.  It seems that, after the weevil's wiped out all the cotton crops for several years in a row, "local businessman H.M. Sessions convinced indebted farmer C.W. Bastion to try planting peanuts instead of cotton. When Bastion produced 8,000 bushels that year, neighboring farmers followed suit, and in 1917 Coffee County brought forth the largest peanut harvest in the nation.
Because the new, diversified crops proved more profitable than cotton, in 1919 local businessman Roscoe Fleming proposed dedicating a statue to the pest that had proven a “herald of prosperity,” and an $1,800 classical statue was commissioned from an Italian sculptor. Thirty years later, one Luther Baker fashioned a large weevil to place atop her outstretched arms. Might as well be explicit."  --And now you know, as Paul Harvey would say, ....

I also continued my road heroics on Jekyll Island (which used to be called Jeykl Island, but someone thought the extra L would be better ). I saved a Loggerhead Turtle and set him free. Ok, I didn't do it all by myself. The Georgia Sea Turtle association was releasing a ten year old (about 150 pounds) that had been kept in the Georgia Aquarium since its egg-ship. I did happen to be in the crowd watching as Dylan, that was his name, went free. He seemed to need a little encouragement as he turned back to shore several times. Eventually prompted by the workers in the waters urging he swam out to sea. Perhaps he was also encouraged by the shouting on shore as the crowd yelled "DIll - Enn.. Dill Enn... repeatedly, especially if he was as confused as I was at first. I thought I had fallen in with gourmets of the turtle soup variety yelling "Kill him, kill him..' eventually I got it straight, and hope Dylan also knew we were NOT trying to have him for supper.

More stuff I learned, don't explain palindromes while driving through Elba, Alabama. As I came into town the name of the town reminded me of one of the first palindromes I ever leaned (OK, second, the first was Madam I'm Adam.. read it backwards if you don't know what a palindrome is); Able was I ere I saw Elba. In math, we call numbers like 121 or 1331 or 14641 (surely you recognize the powers of 11) palindromic numbers. We even refer to a polynomial like 1x²+2x+1 as palindromic (look at the coefficients). As I was making sure my wife understood, I saw flashing lights in the rear view mirror... apparently the speed through town was only 25 mph and I was, as the kind officer explained holding thumb and finger an inch apart, "A little over." It was Sunday Morning, and in the spirit of Christian charity, he let me off with a warning.... Thank goodness I was not in Georgia.. I might still be rotting in Macon County Correctional Institute for Out of state drivers.

A Mandelbrot-like Set for Quadratics

 The Mandelbrot set can be thought of as a catalog of closed Julia Sets over the complex plane. Each point on the plane representing a complex number, and the coloring representing whether the Julia set for that point had a closed or open orbit.

The equation y= ¹/₄ x² on the coordinate plane can, in similar fashion, serve as a catalog of all possible quadratic equations. The method was discovered by a high school age British student by the name of Anthony Bayes around 1955 as reported in the Mathematical Gazette in September of that year by H. Gebert, the young man's teacher.

If every point (b,c) on the coordinate plane is representative of a quadratic equation x²+bx+c=0, then the set of all points in the cup of the parabola have only complex solutions [for example, the point (2,5) would represent the equation x²+2x+5=0 which has only complex roots]. Those points beneath the curve have two real distinct solutions, and the points on the curve specify equations which have a double root[ again, (2,1) would represent the perfect square trinomial x²+2x+1=0]. For any point on the curve, the solutions are -1/2 the x-coordinate. In the case of (2,1) the double root of x²+2x+1=0 is at -1/2 of 2 = -1.

Any line tangent to the curve passes only through points representing equations which share at least one solution. The line y=x-1 which is tangent to the curve at the point (2,1). Since the solutions for x²+2x+1=0 are both -1; all the points on this tangent represent quadratic equations which have x=-1 as one solution. As a case in point, (or a point in this case), (5,4) is on the tangent line, and the solutions of the quadratic equation x²+5x+4=0 are x=-1 and x=-4. If you drew the other tangent to the parabola passing through the point (5,4) it would contain the point (8,16) on the parabola representing the quadratic with a double root at x=-4, that is, the quadratic x²+8x+16=0.
 

Desmos 

The reflection of this tangent in the y-axis gives the tangent through the point representing the equation x^2-2x+1, with the double root at x=+1.  At this point your students should know the point of intersection of the tangent at (8,16) and the tangent at (-2,1).

This would also allow a simple approximation method to find the solutions of any quadratic with reasonably small values using only a straightedge and a printed graph of the curve y=1/4 x². Simply pick the point (b,c) corresponding to the values of the equation, and then lay a straight edge through the point and tangent to the parabola. The solutions would be -1/2 the x values of the points of tangency, as given above.

Chen, Goldbach, and the Search for an Unsolved Proof

3-5,     5-7,     11-13,     17-19...                        29-31 

            7-9...........13-15........19-21..... 23-25, 

 A few days before I set out to write this, scrolling through my twitter feed I found, @AlgebraFact · " Chen’s theorem: There are infinitely many primes p such that p+2 is either prime or the product of two primes." This read a little differently than how I remembered it so I set about milking the net to refresh myself. I concluded that Chen's Theorem is a lot like the parallel postulate, it is written lots of different ways. 

 Here's another, Theorem(Chen): For any even integer h∈2Z, there exist infinitely many primes p such that p+h is either a prime or a semiprime. Ok, make h=2 and it's the same thing. 

 But then Wikipedia has " Chen's theorem states that every sufficiently large even number can be written as the sum of either two primes, or a prime and a semiprime (the product of two primes)." Now these are really very different statements, at least to young students. It is a link that number theorists recognize in some of math's long unproven conjectures. 

 So let's go back a bit, to the early twentieth century, and a German Mathematician named Edmund Landau. "At the 1912 International Congress of Mathematicians, Edmund Landau listed four basic problems about prime numbers. These problems were characterized in his speech as "unattackable at the present state of mathematics" and are now known as Landau's problems. 

They are as follows: 

 Goldbach's conjecture: Can every even integer greater than 2 be written as the sum of two primes? 

Twin prime conjecture: Are there infinitely many primes p such that p + 2 is prime? 

 Legendre's conjecture: Does there always exist at least one prime between consecutive perfect squares? 

 Are there infinitely many primes p such that p − 1 is a perfect square? In other words: Are there infinitely many primes of the form n^2 + 1? 

 As of June 2022, all four problems are unresolved." *Wikipedia. 

 Wow, so number 2 says almost the same as the twitter post, with a slight opening for "nearly prime", one of the terms sometimes used for semi-primes, or composite numbers that are the product of two primes. (As a teacher I hope that the students reading this would know the the two primes need not be distinct, so 9 and 25 are still semi-primes.) 

 Number one sounds more like the Wikipedia definition of the term. Obviously these two conjectures are interrelated. A little before Chinese mathematician Chen Jingrun, first wrote about this idea in 1966 , and expanded on his proof in 1973, in 1947, Alfréd Rényi had showed there exists a finite K such that any even number can be written as the sum of a prime number and the product of at most K primes. So Chen had reduced the number of factors of the non-prime from some unspecified K, to 2, and showed that and included that there are an infinite number of "nearly prime pairs" with any even separation.  So there are infinitely many primes p such that p + 4 is prime, or a semi-prime; and  there are infinitely many primes p such that p + 6 is prime, or a semi-prime; and p+8, p+10,.....

Number Theory folks have names for some of these pairings, Cousin primes differ by four, (7 and 11 for example), and sexy primes differ by six, and if one of two sexy primes has a twin that falls between the sexy pair, they are called a prime triplet, 7, 11, 13 for example, or 17, 19, 23. Chen's theorem says that there must be infinite examples of cousin and sexy pairs with a prime followed by a prime or a semi-prime. 

 Then in 2015, Tomohiro Yamada took away the "every sufficiently large even  another number " of Chen's theorem and gave a definite limit. Every even number greater than \(e^{e^{36}}\) , which is big. But in time someone will find a way to knock that "sufficiently large number" down a little, maybe a lot. But  that is with "nearly twin primes", it seems like Goldbach's conjecture and the twin prime conjecture still rest heavily in the "unattackable at the present state of mathematics" stage. 

 But then, in my youth most folks said we could never prove Fermat's Last Theorem, and then we did... well, not me, but it was the same type of whittling away at it through the ages until Andrew Wiles, inspired by a book he found in the library at age ten, completed a thirty year search for the "impossible" proof. Maybe one of your students will learn about this pair of "impossibles", and surprise us all.

Why not expose them to Goldbach's conjecture; what even numbers are the sum of two primes? It seems like all of them, at least every one we try.  It has been tested up to 4*10^18 though, and so far, so good. But there are still great things to explore, how many ways can even n be written as the sum of two primes, and by what rules.  10 = 5+5 = 3+7 = 7+3  are the last two different?  What if we don"t allow doubles like 5+5?  If we want each sums primes to be distinct, 24 is the smallest even number expressible as the sum of two primes in three ways... and no, I'm not telling you, find them. 

Just as I was writing this, one of the Fields Medalist winners in 2022 was presented to Oxford Professor James Maynard for his work on primes.  One of his recent works about distributions of primes was toward a proof that there are an infinite number of prime numbers that do not have a 7 among their digits.  He also cited the twin prime conjecture as one of his favorites.  

Now what's the smallest number that is expressible in four ways, five...

Some History Notes on Casting Out Nines, and request for information

I'm Re-posting some old blogs to try and preserve some notes,  and do some editing

In my youth, back in the dark ages before calculators, one of the common mathematical tools we were taught was called casting out nines. It seems it is not common anymore, perhaps the errors students make with calculators no longer submit to the simple check of this ancient method. If you happen to be of the generation who have been kissed on the forehead by the Gods of Electronics and actually don't know the method, you can find some notes on my page, and also here is a brief video from YouTube.

I have a note on my MathWords page on the subject from a respected math historian (Albrecht Heefer) that tells me, "Casting out nines is believed to be of Indian origin, but it does not occur before 950. Maximus Planudes called it 'Arithmetic after the Indian method". Along the way I seem to have a note from him telling me that I can find more confirmation on the web site of David Singmaster, the famous historian of mathematical recreation; but while searching there, I seem to have a note that claims the first mention of casting out nines was by the Latin writer Iamblichus in 325 AD... But he was talking about Nichomachus, a Pythagorean who lived around 100 AD.

"325 Iamblichus: On Nicomachus's Introduction to Arithmetic - first mention of Casting Out Nines; first description of the Bloom of Thymarides; first Amicable Numbers."

Now the common thought, or at least as I thought I understood it, was that the inventors of the hindu-arabic numerals had developed casting out nines and it sort of made its way into the west with the introduction of the Arabic numbers. Leonardo of Pisa, the famous Fibonacci whose bunny sequence you remember from school (of course you do, 1, 1, 2, 3, 5, 8, 13, 21...... That sequence) was a major influence in bringing both to the west with his famous book, the Liber Abaci, (the book of calculating) around 1202.

But the fact is that the general public held on to their Roman numerals for several centuries, and legal documents had to have them in some areas up into the 15th century.. Now the problem, at least for me, is that it seemed much less likely that someone would develop casting out nines using Roman numerals.. see if you are using Arabic numerals, you take a number and add up the digits... 2534 would give 2+5+3+4 = 14 and then adding 1+4 = 5 so we know that if you divide 2534 by nine, you get a remainder of 5. Now in Roman numerals we write 2534 as MMDXXXIIII ... So I set about trying to figure out casting out nines with Roman numerals, and it hit me.   

Numbers that are powers of ten always have a remainder of one when divided by nine, so any X, C, or M is crossed out and an I is added at the end for it.  So MMDXXXIIII is replaced with DXXXIIII+II.  Maybe they would shorten that to DXXXVI.  Now replace the three tens with Is also to get DVI+III.  Now five, fifty, or five hundred would have a remainder of five when divided by 9, so D becomes a second V, and the two Vs become an X which becomes an I  (I can visualize all this as a mental operation to experienced "casters") leaving him with five I's, or just a V = 5  for the remainder. In fact without writing anything down you can just read across MMDXXXIIII, counting 1,2,7,8,9,10,11,12,13,14...and any time with a sand tray they would know that subtracting is taking one from the X column and put it in the I column.  

If they converted all the Ds and Ls and V's to five of the powers of ten, and avoided any IV orXC type subtractors,  I can see it becoming obvious, so maybe that is how it came about. If you write the Roman numbers with only unit (that's how math types say ONE) multipliers, like M for 1000 or X for 10 or C for 100, then all you would have to do is count the number of digits (not add them up). For example MMCCXII has seven digits, so the number 2212 should have a digit root of 7, which it does. And for really long numbers, you could throw away groups of nine in the same way we do with casting out nines..... MAYBE... but I wonder..  So do any of you scholars out there know of an example of casting out nines from something using other than Arabic numerals?  Please share if you do.

Anyway, I'm still looking for that Rogue Scholar out there who happens to have the original of Nicomachus' "Introduction to Arithmetic" laying around on his bookshelf and would like to translate for me to explain where he says it came from (if indeed he did).

I have played around with other divisibility rules, and even made up some of my own. If you want to read these early blogs first, you might try this one.

The reason I am reminded of all this is that I just read an interesting article by the almost unknown English mathematician, Henry Wilbraham (July 25, 1825 – February 13, 1883), in an old Cambridge and Dublin Mathematical Journal. He points out that you can construct a similar division technique for any number. The idea is to use the period of the smaller numbers repeating fraction to break apart the second number. As an example, if you wanted to test to see if some large number was divisible by 37, you would first find the digital period length of the decimal 1/37. It turns out that 1/37 = 0.02702702702702703 so its period is three.
Now we take the really big number we want to test, say 7,424,883,933,621. We want to know if that number is evenly divisible by 37, and if it isn't, what the remainder will be.
The variation in Wilbraham's approach, and as I point out later it's not really an a variation at all, is to break the larger number up into sections of three digits (the period of our divisor's reciprocal), so we would add the 621+933+883+424+7= 2868. Now just as we can continue to compute digital roots when casting out nines, because there are more than three digits here, we can recombine those to get 2+868 = 870. Now all we have to do is divide 37 into 870 and if it goes evenly, it's a factor of the larger 13 digit number. If not, the remainder we get will be the same as the remainder when dividing the original number.
Turns out 37 is not a factor of 870 but leaves a remainder of 19. The good news is that we know that when we divide 7,424,883,933,621 by 37, we will get the same remainder.

It turns out that the reason this works is the same as the reason that casting out nines works. The period of 1/9 is one,.11111....., so we add every digit.

The math behind this is simple enough that I think any bright high school kid could understand it. If the period of a numbers reciprocal 1/n is some number p, then it must be true that 10^p-1 is divisible by n. In my example, 10³-1 must be divisible by 37, and is.
So if we break our larger number, N, up into periods of p, and express the sets of digits as individual numbers, A,B,C,D... so that N= A+10^pB + 10^2p...etc.
So we know that N= A+ (kn+1)B+ (kn+1)² C.... and if we distribute all these kn+1 terms all the kn powers can be collected (and are thus a multiple of our smaller divisor, n) and the rest will be A+B+C... which is the sum of the periods, and thus the remainder. If this number is longer than the period of 1/n, we can apply it again by using the same reasoning.

I should point out, because Wilbraham is so unknown, he did not spend his entire mathematical life doing arithmetic novelties. He is known for discovering and explaining the Gibbs phenomenon, the peculiar manner in which the Fourier series of a piecewise continuously differentiable periodic function behaves at a jump discontinuity, nearly fifty years before J. Willard Gibbs did. Gibbs and Maxime Bôcher, as well as nearly everyone else, were unaware of Wilbraham's work on the Gibbs phenomenon.

Most students know a rule for testing divisibility by 11 that goes sort of like this usually:  add up every other digit, then add up the remaining digits, if their difference is o or a multiple of 11, then it's divisible by 11. For  42351 we add 4, 3, and 1 to get eight, and 2  + 5 =7 , so 42351 is not divisible by 11.  But let's explore Wilbraham's  method,  The period of 1/11 is two digits, .0909....  Breaking the trial number into 4 + 23 + 51 we get 78, which we can see immediately is one more than a multiple of eleven.  

There are many divisibility shortcuts that are quicker for some numbers.  Thirteen has a period of six digits, and seventeen hasw a period of 16 digits, so unless you are working with very large numbers, the reduction of labor may not be great.  Stll for numbers with shorter periods it's just "casting out."

A Problem About Elevens, and Some Methods of Casting Out Sevens, and Other Primes.

Expanding an Archive blog from 2008 with some new insights:


Sometimes I enter the math contest they host at the Wild About Math blog site, and usually am among the people who get a correct answer, but haven't been the lucky name pulled from the hat yet. A recent problem about divisibility got me thinking about testing divisibility by seven again.
The problem was actually about divisibility by eleven, and asked
Consider all of the 6-digit numbers that one can construct using each of the digits between 1 and 6 inclusively exactly one time each. 123456 is such a number as is 346125. 112345 is not such a number since 1 is repeated and 6 is not used.

So.... How many of these 6-digit numbers are divisible by 11?

The answer, of course, is none.
Of course, is a danger word, like obviously, or trivially, in which we dismiss the idea that there is thinking involved.  If I were presenting this question to a class, and I have, I would say it differently. 

"None of these numbers are divisible by eleven, can you figure out why without test dividing any of them? "
 If you don't see it, don't worry, I'll spill the beans on how I would prove it down the page.  Just take a moment and try it yourself.

K
I
L
L
I
N
G

T
I
M
E

T
O

LET

YOU

THINK


The divisibility rule for eleven most commonly known is to take the digits abcdef and add every other one from the back, and then subtract the alternate ones.  So f-e+d-c+b-a  For example, 123456 would be  6-5+4-3+2-1=3.  Now they can only be divisible by eleven if the result is 0, or a multiple of 11.

So if we think about the numbers involved in all these numbers, they all have three odd numbers, and three even, so no matter how you split them, you'll have one group is odd, the other is even, so the difference is an odd number.  You can't get zero.  But can we get eleven?  Ummm, NO, because if we put all the big ones in one clump (6+5+4), and all the small ones in another (3+2+1), the difference is less than eleven.... so NONE of them are divisible by 11.  There is another pretty easy test of divisibility by 11 that is similar to a general method usable by any prime.  Unlike casting out nines, it doesn't give the exact remainder.

 My interest was piqued by a response by Jonathan, of the jd2718 blog made these observations about the 6! or 720 possible numbers formed with the six digits as described:

As a consolation, all 720 of them are multiples of 3.

Half of them (360) are even (multiples of 2)

One in 6 (120) are multiples of 5.

Eight in thirty (192) are multiples of 4.

None are multiples of 9.

Fourteen of 120 (84) are multiples of 8.

Multiples of 7? New puzzle, good place to stop.


It is Not surprising that Jonathon covered all the other one digit divisors but did NOT test seven. Seven is the one that books on mental math simply say "divide by seven"; but thinking about it, it shouldn’t be too hard
I wrote recently about a mental test for divisibility by seven but it did have one flaw. It worked fine to tell you a number was divisible by seven, but if the number was not divisible by seven it did not give the correct modulus. Casting out nines will always give you the correct modulus. The sum of the digits of 2134 is 10 which has a digit root of 1, so if you divide 2134 by 9 you get a remainder of one. My rule for seven didn't give the true remainder.

The remainder when you divide a number by seven (or any other number) is frequently called the modulus. I've mentioned this before, it is just a way to divide integers into sets. Odd numbers are all equivalent to 1 mod 2 (they all leave a remainder of one when you divide by 2) and even numbers are all equivalent to zero. If a number is equivalent to zero mod (something) that means it is divisible by that (something). One of the things that makes them effective is the simple rule that if a+b=c then for any modular index n(the number you are dividing by) c mod n = a mod n + b mod n. For example 25 mod 7 = 4.  We could have found that by breaking it into parts.  Since 25 = 20 + 5 we find 20 mod 7 = 6, and 5 mod 7 = 5... and the  6+5 = 11 which is equivalent to 4 mod 7. So now we have the basics.

Every increase of one in the units increases the modulus 1, and every increase in the tens increases the modulus three, (for example 21 mod 7 = 0; 31 mod 7 = 3,and 41 mod 7 = 6). I figured out that the rest would be an increase of two in the hundreds, six in the thousands (think minus one) four in the ten-thousands (minus three?) and five in the hundred-thousands (minus two….) so the sequence applied to our test number, 546231… and what a coincidence, if you multiply 5(-2)+4(-3)+6(-1)+2(2) +3(3) + 1(1) …YOU GET -14, which is zero mod 7, the sequence of modulii used in each place makes it a multiple of seven…(546231 = 0 [mod 7]…

 but wait, if you used the A-2B method in the blog  above, we would notice that 231 by itself is a multiple of seven, since 23 - 2(1) =21… and 546 is also. [54 - 2(6)=42]..   You could also apply that approach step by step, 54623-2*1=54621; and 5462-2(1) = 5460.  The zero we can throw away because 546 tens is not divisible by 7 if 546 is not, so we proceed to 54-2(6) = 42 and hey, we have a divisor by 7.  In each case we just combined two moduli to reduce the size of the number.

Note: the A - 2B method briefly says take call the last digit B, and the previous digit string A, then if 10 A + b is divisible by seven, then A - 2B is divisible by 7.  224 is divisible by 7; in fact, it's 7 x 32.  If we write it as 10x 22 + 4, then the method says 22 - 2x4 is divisible by 7 also.  since 22 - 8 is 14.   I'll come back to why it tests numbers not divisible by seven, but gives the wrong remainder sometimes later, but first.

 
There is even a neat graphic approach that works very much the same way as the 2A - B approach, but proceeding from front to back, and it gives the correct remainder. I recently came across a nice video of that at a site by Presh Talwalker called Mind Your Decisions. 

  

The secret to this starts with finding the multiple of each digit, and then multiplying by ten.  Checking 312 for example, the modulus of 3 is,,,, 3.  but the modulus if we make it 30 is 2.  (notice that the green arrow from 3 points back to two.  Now we know that 31 must add one more to the modulus, so now we are up to 3 for our modulus.  When we multiply by ten, 31 x 10 = 310 the green arrow says back to 2 again.   Now we need to add the 2 in the units digit to get the final remainder of 2+2 = 4.  

OK, so can we use the graph from the video to correct the remainder on the 2A-B method?  And maybe a little explanation about Why it works.  Most kids realze that on way to divide is to repeatedly subtract the divisor until you get a number too small to subtract again.  24 -7 = 17, 17-7 = 10 , 10 - 7 = 3 so 24 is three sevens and three more or 3 R 3.  

But subtracting one at a time is pretty slow with big numbers, so we could subtract bunches of sevens all at once.  We learned above that 224 was divisible by 7.  So what if we subtracted ten sevens, 70, in a bunch, or we could subtract 140, or 210 (and this is a really good way to test divisibility by seven and it preserves the remainder.  And that's how the A - 2B method works, with a gimmick.  To keep the calculations simple, we use a rule that shortens thew length of the number on each operation.  (Just as the video showed using one digit at a time).   

If we are going to make the number shorter, we need to subtract something that will get rid of the last digit.  It works because of a fact about multiples of seven you may never have noticed.  For every ending digit, there is a multiple of 7 that has twice that digit in the ten's column; 21,, 42, 63, 84, 105, 126, ....

So when test 224, we begin by subtracting 84 to get 140.  You know that 140 is only divisible by 7 if 14 is, so we can throw away the zero and continue with 14.  For really really long numbers, not having to keep all thos zeros on the end reduces the writing, especially if you only care if it is divisible by 7 or not, and don't need the remainder because that gets messed up in the zeros...but it is recoverable using the graph on the video.

So let's walk through a slightly bigger number, doing it with and without dropping the zeros.

5162 sounds like a winner.  

Longer ----------------------------------------A-2B

5162 - 42 ====>    (5120)                  516 - 4 = 512

5120 -420=====>  (4700)                   51 - 4 = 47

4700-14700 ===== (-10000)               4 - 14  = -10

Ok, -10, or 10 is not divisible by 7, and neither is -10000.  Perhaps you could see the fact at 47 without going negative.  Ok, two questions.  What about that negative remainder. and is that the right remainder?  If you not familiar with modulus, just add back sevens (or multiples there-of) and get a small positive.  -10 + 14 =4, but wait, 47 - 42  = 5.  It seems like the remainder is jumping around on us.  Wait, remember the Green arrows used in the video for multiplying by ten?  Well we are dividing by ten.  To get our -10 or 4, we had divided three times.So lets ride the Green arrows, rebuilding from the bottom this time since we are anti-multiplying.   Our final 4 remainder maps to a remainder for the previous 2 digit number, 47.  The 5 maps to 1, and guess what the remainder of 512 divided by 7 is.  Now we have to go back one more The 1 maps to 3, and that is the correct remainder....front to back, or back to front.  

Another divisibility check is a little more work, but has a neat tie to vectors, so I'm adding it.  check is make a function for the first n digit modulii you can just write them out multiplied times the correct modulus for that place value and probably check it in your head, but you would have to check each one… so making up a sequence, 234561(this covers everything up to six digits, but if you have a super memory, figure out another period), we would think 2×5=10 (the first digit times the first modulus) drops to 3, plus 3(second digit)x4(second modulus) is 15 which drops to modulus of one, now add 4(6) to get 25 and drop to mod 4, then add 2×5 to get 14, and we are at mod 0 [so 234500 is divisible by seven] and we know that 61 is NOT divisible by seven, so we can be assured that 234561 == 61 == 5 mod 7… ok, not EASY, but certainly could be done sans calculator…. [footnote, for those of you who have just gone through a pre-calc class and somewhere along the way they taught you about vectors, you probably imagined that you would never run across another dot product in your life, but you just did. IF you think of the sequence of modular values as one vector (5,4,6,2,3,1) and the six-digits of the number as a second vector, then the dot product is an integer that has the same modulus as the original six digit number....come on... that's pretty cool use of vectors!!!]  

It is easy enough to write/remember the modulus up to ten-thousands (6231) to make this pretty useful as a factoring tool if you really needed the correct modulus. If the number is 4723 we just think 4(6)=24--==; 3 + 7x2---==; still 3, + 2(3)=9 --==;2 and then + 3(1)= 5 so 6231 divided by seven leaves a remainder of five.

Now 11 has a very similar method to the A - 2B method, But it's A- B.  Is 43726 divisible by 11?  4372-6 = 4366, 436-6 = 430, and zeros are freebies , so we have 4-3 = 1.  Nope not divisible by 7.  In this case, the one is the true remainder, but not always.  Consider 21, which obviously has a remainder of 10, but the A - B method gives 2-1 = 1.  

If you continue methods for all the primes less than 20, they follow similar approaches.  The approach for 19 would be A + 2B .  An easy way to show it works is to apply it to any multiple of 19.  If we use 95 = 5 x 19, 9 + 2 x 5 =19 (divisible by 19),  19 x 13 = 247, let's try it.  24 + 2 x 7 = 38, and 3 + 2 x 8 = 19. 

Let's make up a longer number we won't know for sure 198273456.  Step by step, 1982734 5 + 2 x 6 = 19827357; and 1982735 + 2 x 7 = 1982749; 198274 + 2 x 9 = 198292;  19829 + 2 x 2= 19833; 1983 + 2 x 3 = 1989; 198 + 2 x 9 =  216; and 21 + 2 x 6 = 12.  Not divisible by 19.  

A moment to clarify,  What determines A + 2B from A - 2B or other to come.  Suppose we have a number that is a multiple of seven  and we break it up as 10 x 7k + 21 N.  the last digit must be the same as N.  try 10 x 2x7 + 21 x 3.  that's 140 + 63 = 203.  The 3 has to come from the multiples of 21, and since that last digit is 3, there must be three of them, or 13 or 33 or... but if we subtract 3 of them, we will still preserve divisibility by seven.  The three ones came with six tens, so each time we cross off the ones, we are reducing the tens by twice as much.  When we adjust 161 with 16-2 to get 14, it's a short cut for 161 - 21 = 140, but a number n times ten is only divisible by 7,  if n is divisible by 7, because 10 isn't.  

With 19, once more we are at almost two tens, so we use addition to make the ones go to zero.  Think of  133 If we add 60 ( three twentys) to 133, we get 193, but now it is not divisible by 19, it has three extra in the units digit, so we get rid of the 3 by subtraction to get a multiple of 19, 190.  And for our quick algorithm, we drop the last digit of zero because dividing by ten does not change divisibility by nineteen if the last digit was zero.  Is 19 divisible by 19, then so is 133.  

We do a similar thing with 13.  3 x 13 = 39, almost four tens. Our rule is A + 4B.   We need to use the add on method like 19.  Let's look at some multiples of 13.  13  becomes 1 + 4 x 3 = 13; divisibility retained.  26 is transformed into 2 + 4x6 = 26, check.  Maybe something bigger.  15 x 13 = 195.  195 morphs into 19 + 4 x 5 = 39 which is three thirteens.  

For 17, we get close to a multiple of ten with 3 x 17 = 51, so we expect our divisibility to be preserved by an algorithm of A - 5B.  Let's try a few.  17 becomes 1 - 5 x 7 = -34, which is divisible by 17.  

17 x 346 = 363.  Trying the rule on that we begin, 36 - 5 x 3 = 17, and  success.  17 x 1345 = 22865.  We begin with 2286 - 5x5 =  2261.  Then 226 - 5 x 1 = 221.  Finally 22- 5 x 1 = 17.  

Once you see the method, you could create shortcuts for any prime.  3 x 23 = 69; nearly 7 tens.  I would try A + 7 B.  29 seems quick, almost three tens.  Try A + 3B.  1044 is 36 x 29.  We use 104 + 3 x 4 = 116.  Then 11 + 3 x 6 = 29....seems to work.   -37.  see

31 seems easy, but 37?  What do you think, and remember, there can be more than one way for lots (all?) of these. Do you think A - 11B?  Let's check, and if that works,  think you are on your way.  37 x 17 = 629.  We begin with 62 - 11 x 9=  -37.  Seems to work.  

Have Fun!

The Rule(s) of Three and the Probability of Nothing

A Re-edit and Posting of a 2008 Blog

From 1827 Pike's Arithmetic

In my youth, back when dinosaurs roamed the earth, there was “the rule of three”… singular, one, and even then the name was often described as “archaic”. More modern books tended to develop “properties of proportions” or similar terms for the problems of proportionalities. Now there seem to be an abundance of them; including one for witches, and one about businesses. There is not space enough to talk about all of them so I will mention three, of course.
The first rule of three is as old as math, and shows up at least as early as the Hindu mathematician Brahmagupta, and in Fibonacci’s famous Liber Abaci(1202). It was once so common that it was introduced into common language. Abraham Lincoln is quoted in his biography as stating that he learned to "read, write, and cipher to the rule of 3."   So common that student's often wrote verse like the following, in their copy (practice) books.

Multiplication is vexation;

Division is as bad;

The Rule of Three doth puzzle me,

And Practice drives me mad

The most common and longest living form was the direct rule (although there was an inverse rule as well), in which case three numbers would be given and a fourth sought so that the ratio between the third and fourth would match the ratio between the first and second; a:b = c:d. Today students use the ideas in elementary school to complete fraction equivalences, “2/3 is the same as 10/?” Some of the ancient examples grew incredibly complicated.

I suppose the reason I chose to address three of the many “rules of three” is because of the rule of three from language and literature. Three just seems to be the right number for lots of things, there were Three Musketeers, Three Stooges, and Three Coins in the Fountain. It was Goldilocks and the Three Bears, and “bah bah black sheep” had “three bags full.” Comics in the newspaper usually have three panels and many jokes involve a three part ritual where the punch line is the third element, such as the t-shirt with “Great Cities of the World” on the top, and below, one after another, “Paris, Rome, Fargo”. The first two make the last funnier. In language the examples range from “Blood, sweat, and tears, to veni, vidi, vici. If you don’t think there really is a mental tendency to have three terms, consider that in Churchill’s speech, he actually used four; “I say to the House as I said to ministers who have joined this government, I have nothing to offer but blood, toil, tears, and sweat. “  But who cares what he said, you will hear the phrase almost always as "Blood, sweat, and tears, and it was common usage before and (however long they last) after the band.

The final rule of three I would mention is from statistics, and is of more recent origin. It is also, I think, a really clever solution to what is a really difficult problem. Suppose something never happens; how can you assign a probability to it? It is not that it might not happen some day, just not so far. It is just such a problem the statistical rule of there was created to handle. Suppose you stopped at the same gum ball machine every day, but unlike the normal gumball machine, this one did not have a glass you could see into the gumballs inside. You buy a gum ball every day and get red ones, and green ones, but never a blue one. After a while you begin to wonder if they even put a blue one in the machine. So one day, after 20 days of getting all the other colors, over lunch you ask your local statistician (doesn’t everyone have lunch with a statistician?) how to figure out if there really is a blue one in there. He pauses, fork poised in mid-air, and informs you that you can be 95% sure (a common statistical benchmark) that the proportion of blue gum balls is no greater than 14.3%. He had mentally taken three, and divided by one more than the number of failed efforts, to get 3/21 or 1/7 as the upper limit of the possible fraction.
The idea is base on a simple extension of the binomial probability. If you knew that P % of the gum balls were blue, then you could calculate the probability that None showed up in 20 days. The probability would be (1-p)²⁰. Working back through this calculation many times you might notice that the number followed a pattern, a rule of thumb to calculate without tables and calculators, and that turns out to be 3/(n+1), the statistical rule of three, giving a probability for the Blue gum balls as 0< P < .143.  If you wanted greater certainty, you can use the rule of seven, which says that 7/(n+1) will give the 99% interval boundary. So in the case of your gumballs, you can be 99% sure the percentage of blue gumballs is less than 1/3. (Of course this problem assumes a population that constantly replaces the gum ball removed so that the probabilities remain constant.

But what if after a long string of failures, you have a success.  How does this change your confidence interval?   Thanks to a recent post from John D Cook I now can tell you that as well.  

So suppose you had worked your way as before with twenty failures to get the blue gumball, and then after the aforementioned lunch with a statistician,  you get a blue gumball on the 21st try.  Now what can you say about the expected percentage of blue gumballs.  

After the first success according to the Beta distribution would give a 95% confidence interval of appx. [.1/n, 4.7/n]  .  For our imagined 21 tries, this would be about [.0047, .224]  So our confidence interval has opened up considerably.  

It appears, if I understand correctly, that the blue gumball could have occurred anytime among the first 21 tries and thus would still be the CI.  So if we went another nine tries without success, we would adjust our CI to {.1/30, 4.7/30] ... [ .00333, .157], back much closer to our expectations before we ever had a success.

Comparing this interval to the binomial confidence interval you learned in high school math, p +/- 2 sqrt(p*(1-p)/n).  The customary warning on the normal expectation is beware of p being too high or too low.  Using one success in 30 tries we get a 95% CI of [-.03, .099]... perhaps the negative lower bound is a sign that we have strayed to close to zero with our p-hat.  A nice topic to spring on your AP stats teacher when you get to confidence intervals, but please be kind. 

 

Primes Generated by Alternating Factorials?

 Found this one in an article by Richard Guy on the Strong Law of Small Numbers... *K. Guy, The strong law of small numbers. Amer. Math. Monthly 95 (1988), no. 8, 697-712.

Is it always true?  Is even the next one true?

Just a quick note on the notation a(n) for alternating factorial.  I would think something like +/- n! is much more intuitive.

Spoiler (of sorts)

x
x
x
xx

xx
x
xx
x
x
x
Neil Calkin ‏@neil_calkin offers:
solutions for 3,4,5,6,7,8,10,15,19,41,59,61,105,160 no more small values.  

It continues 661, 2653, 3069, and probables (3943, 4053, 4998, 8275, 9158, 11164, 43592, 59961) ...  but the sequence is finite, and all prime terms in alternating factorials must be less than p = 3612701,

If you love factor challenges  f(9) = 36614981, and f(11)=36614981  (maybe easier)

 

The prime values of the prime terms are 

3- 5

4 19

5 101

6- 619

7- 4421
8- 35899
10- 3301819
15- 1226280710981
19 115578717622022981
41- 32656499591185747972776747396512425885838364422981
59-136372385605079432248118270297843987319730859689490659519593045108637838364422981

61-499395599150088488088828589263699706832570087241364247806476254829684637838364422981
105-1071195818389184106041377222623114315174404652995290026861977169467051355218307761044337430404771512503239158647256903838408052353602736923780521178553460637838364422981
160-468544077492065936712052044718939948687543330546977719976017418129955876663406131164377030450551575840099843957105136480237871017419158043635450756712088769133544426722033165168878328322819566779381528981882285541609256481166622331374702000809600061055686236758821446539362161635577019