20170325, 09:53  #1 
Nov 2016
29 Posts 
Understanding Lucas' chess board algorithm
I'm trying to understand the chess board algorithm that Lucas used compute the residues of Mersenne numbers.
For example, the calculation of residues for 2^71: Form the sequence of numbers S_n = 3, 7, 47, ... via squaring, subtracting 2, and reduction modulo the Mersenne number. If we perform this on S_3 to obtain S_4 using binary multiplication, we can lay out the calculation on a 7 x 7 chess board (noting how 0101111 is left shifted through the rows cyclically), then obtain the result of the reduction. 0 1 0 1 1 1 1 = S_3 = 47 7 6 5 4 3 2 1 0 1 0 1 1 1 1 1 0 1 1 1 1 0 0 1 1 1 1 0 1 1 1 1 1 0 1 0 1 1 1 0 1 0 1 0 0 0 0 0 0 0 1 1 0 1 0 1 1 Once he had this array, Lucas would perform these operations: 1: Subtract 2 from the result via removing one pawn from column 2. 2: For each pair of pawns in any column, remove one from the board and move the other into the column to the left. Via successive removal of lines, continue these operations until the only pawns remaining are in the first row. In our case we are supposed to get a top row of: 7 6 5 4 3 2 1 0 1 1 0 0 0 0 = S_4 = 48 = 2207 mod 127 I would be grateful for a more detailed description of the second instruction or additional procedures. I can't seem to get the right result. How does one remove and shift the pawns to obtain the top row? I've attached a clipping of an explanation from "Mathematics of Computation 19431993" and the 127 bit array from Lucas' paper in Recreations Mathematiques  https://primes.utm.edu/mersenne/Luke...t/lit_068s.htm Lucas shows an additional set of four rows giving the addition of the units of each column, with the carries, but I'm not clear if/how these are accumulated using pawns. 
20170325, 19:22  #2 
Nov 2016
1D_{16} Posts 
Sorry, the array from Lucas' paper is 31 bits, not 127 (but he did prove 2^127 1 is prime using this method).
Last fiddled with by a nicol on 20170325 at 19:23 
20170325, 19:28  #3 
"Rashid Naimi"
Oct 2015
Remote to Here/There
2^{6}·31 Posts 
Thank you for posting this thread.
I have subscribed to it for further study. BTW, Welcome to the board. 
20170325, 21:31  #4 
"Forget I exist"
Jul 2009
Dumbassville
2^{6}×131 Posts 
the closest method I know of is that you can square a number using shifts and carries in binary:
11111 > 31 in binary but as for what's actually being done I'm at a loss right now. Last fiddled with by science_man_88 on 20170325 at 21:51 
20170326, 00:12  #5 
"Forget I exist"
Jul 2009
Dumbassville
8384_{10} Posts 
sorry double posting it seems to be missing one of the shifts and replaced it with 0 or messed it up but one formula is y mod 2^n1 is equivalent to y mod 2^n + y\(2^n) where \ is the integer division sign. You get the addition of the two parts, if you shift the binary value correctly.

20170326, 17:26  #6  
(loop (#_fork))
Feb 2006
Cambridge, England
13·491 Posts 
Quote:
You're trying to compute 0101111^2 mod 127. That is, (32+8+4+2+1)*47 mod 127. Which is 47 + 2*47 + 4*47 + 8*47 + 32*47 So I would start out on the board with Code:
0101111 = 47 1011110 = 2*47 0111101 = (4*47)%127 where the modulo comes from the cyclic shift 1111010 = (8*47)%127 0000000 because not 16*47 1101011 = (32*47)%127 0000000 because not 64*47 And the rules need to be (these are 'adding zero or 2^p1 does nothing', 'addition is commutative', and 'twice a power of two is the next power of two') * If a row is allempty or allfull, you can remove it and move all the other rows up * You can move a pawn up and down its column at will * If there are ever two 1s in a column, you can remove them both and change a 0 to a 1 in the next column (they don't have to be adjacent or anything). This includes wrapping round from the leftmost to the rightmost column I set this up in Excel with some extra calculations to check that I wasn't changing the answer, and did manage correctly to square 47 mod 127. I think the original article doesn't make it clear that the pawns you remove don't have to be adjacent in their column and that the increment can be anywhere in the appropriate column, and I really don't think they've illustrated the starting board correctly. Last fiddled with by fivemack on 20170326 at 17:27 

20170327, 16:30  #7 
Romulan Interpreter
Jun 2011
Thailand
5^{2}×7×53 Posts 
To make it chesslike, imagine a game of suicidal lemmings, where the chessboard is on the side of a cliff and all pawns/lemmings advance towards the cliff. So, better rules could be:
 if a pawn has an empty square in front of him, he advances into it.  if a pawn can not advance because other pawn is in front of him, he will "capture" (kill) the one in front of him by moving himself to the left, if the left square is free (this cycles as mentioned, from the first column to the last) (alternative, you can say that when a pawn can not advance because other pawn is in front of him, he will push that one to the left, if the space is empty, but doing so, he will die because of the effort, hehe).  if the first row is full, all pawns hold their hands and jump from the clif, crying "hooraay" hehehe. Of course, a prime is the most criminal situation, where all pawns comit suicide. Note that "subtracting 2" may not be possible initially, therefore it has to be done first time when it becomes possible (i.e. remove a pawn from the second column from the right). It is very easy to implement an animation of it... (maybe we will do one in excel or so, but not now, when it is midnight here). Last fiddled with by LaurV on 20170327 at 16:32 
20170328, 11:08  #8 
Nov 2016
1D_{16} Posts 
Thank you for your responses all. I can get the right answer now.
Thank you for the correction to the table fivemack: Mathematics of Computation, 19431993: A Halfcentury of Computational Mathematics has a mistake in it, I think. Being able to move the pawns up and down and clear out a whole full row at once makes this much easier. Last fiddled with by a nicol on 20170328 at 12:07 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Vote chess game 4: To be decided? Some chess variant will be interesting to consider with!  Raman  Chess  6  20161206 06:50 
Understanding assignment rules  Fred  PrimeNet  3  20160519 13:40 
Understanding NFS  Demonslay335  YAFU  11  20160108 17:52 
understanding the group G in an explanation of the LucasLehmer test  wildrabbitt  Math  1  20150517 12:34 
LL Test: Understanding the math  zacariaz  Homework Help  32  20070516 15:18 