Prime numbers and primality testing is a Restricted Group with 1137 members. New puzzle? King moves for primes Zak Seidov Message 1 of 28 , Jul 13, 2003 View Source Dare suggest (new?) puzzle: Take, say, 3x3 board with digits arranged e.g. in order: 1 2 3 4 5 6 7 8 9 Starting from any cell, King (Chess King!) moves for primes. How many primes can he (or you) find by rules: King moves for any neighbor cell, (* e.g. from cell with 5, he can move to any of 8 other cells, from cell with 1, he can go to cell with 2, 5, or 4 etc*) then again for any neighbor cell (even returning back). Each time digits contacenate to form (finally - maximum after say 10 moves) a prime. Then you may start from any other cell. Ok, let me show examples a) for 1-move version (two-digit primes) we have : starting from 5, two primes: 53 and 59, starting from 4, two primes: 41 and 41, starting from 2, one prime : 23, total 5 two-digit primes. b) for 2-move version (three-digit primes) we have: starting from 5, six primes: 541, 547, 521, 523, 563, 569, 587, etc With increasing number of moves, the problem should be solved by program. Several Qs: What is the maximal number 2-,3-,4-,....10-digit primes, using the given start position? What is the best start position (giving more primes). What about larger board? Go! Zak mikeoakes2@aol.com Jul 13, 2003 View Source In a message dated 13/07/03 15:35:51 GMT Daylight Time, seidovzf@... writes: > Several Qs: > What is the maximal number 2-,3-,4-,....10-digit primes, > using the given start position? > What is the best start position (giving more primes). > What about larger board? Interesting idea, Zak. We could replace your 3rd Q with another: What about smaller board? and consider a 2x2 board. (There are 4 of these sub-boards in a 3x3 board.) The 2-D aspect now actually vanishes ! , and your first two Qs become re-statable as:- What is the maximal number 2-,3-,4-,....10-digit primes, using a given set of 4 digits? What is the best set of 4 digits (giving more primes). These problems are certainly easier to program - and it might help to walk before we run:-) Mike [Non-text portions of this message have been removed] Zak Seidov Jul 13, 2003 View Source Take the standard 3x3 position: 1 2 3 4 5 6 7 8 9 King's moves taking maximum three cells give the next primes: 2 3 5 7 = 4 23 41 47 53 59 89 = 6 151 157 241 251 257 263 269 353 359 421 457 487 521 523 541 547 563 569 587 653 659 751 757 853 857 859 863 953 =28 ====== total =38 this all can be done by hand more long routes? Zak Show message history Jon Perry Jul 13, 2003 View Source [Zak Seidov] King's moves taking maximum three cells give the next primes: [Jon Perry] Why precisely is the question forcing a King? A Queen or Rook should also be allowed. A Knight on a larger board would be cool (I forget when a Knight's tour becomes possible on a n.n board). Another variation - take a chessboard and number 1..64 (or 0..63 - and another point - why must the ordering be horizontally biased?). Play a game of chess whereby our 'chess number' is the concatenation of all squares moved to by the combination of both players (or produce white and black numbers). What is the smallest checkmate prime? Jon Perry perry@... http://www.users.globalnet.co.uk/~perry/maths/ http://www.users.globalnet.co.uk/~perry/DIVMenu/ BrainBench MVP for HTML and JavaScript http://www.brainbench.com mikeoakes2@aol.com Jul 14, 2003 View Source I have programmed the 2x2 board version. The method used is exhaustive search, calling recursively (for increasing no. of moves) a simple "evaluate" procedure. It took less than 1 hour to code and get working, and to adapt it to the MxN board case is straightforward (but I am late for work already...). However, execution times will get horrendous: a 3x3 board has 10^5 times as many starting configurations as a 2x2. Execution time: 1.5 mins on 2.08 GHz Athlon. Not that the "best starting board" is not unique; what is given here is the first one found, with the boards being enumerated in sequential numerical order (0000 thru 9999), and "1133" meaning the board 11 33. Results:- 1+no. of moves best starting board no. of primes 1 2222 4 2 1111 12 3 1133 28 4 1118 48 5 1117 132 6 1119 384 7 1333 1008 8 1177 1768 9 1113 6216 Mike [Non-text portions of this message have been removed] Zakir Seidov Jul 14, 2003 View Source OK, Mike, you did a JOB, now i think that may be only distinct primes count, what do you think about this in your program - rejecting repeating primes, thanks, zak ...really looking at 2222 or 1111 i see only one prime (not 4 or 12!)... --- Mikeoakes2@... wrote: > I have programmed the 2x2 board version. The method > used is exhaustive > search, calling recursively (for increasing no. of > moves) a simple "evaluate" > procedure. > > It took less than 1 hour to code and get working, > and to adapt it to the MxN > board case is straightforward (but I am late for > work already...). > However, execution times will get horrendous: a 3x3 > board has 10^5 times as > many starting configurations as a 2x2. > > Execution time: 1.5 mins on 2.08 GHz Athlon. > > Not that the "best starting board" is not unique; > what is given here is the > first one found, with the boards being enumerated in > sequential numerical order > (0000 thru 9999), and "1133" meaning the board > 11 > 33. > > Results:- > 1+no. of moves best starting board no. of primes > 1 2222 4 > 2 1111 12 > 3 1133 28 > 4 1118 48 > 5 1117 > 132 > 6 1119 > 384 > 7 1333 > 1008 > 8 1177 > 1768 > 9 1113 > 6216 > > Mike > > __________________________________ Do you Yahoo!? SBC Yahoo! DSL - Now only $29.95 per month! http://sbc.yahoo.com mikeoakes2@aol.com Jul 14, 2003 View Source In a message dated 14/07/03 14:51:36 GMT Daylight Time, seidovzf@... writes: > now i think that may be only distinct primes count, > what do you think about this in your program - > rejecting repeating primes, > What I think is: let's stick with the problem you originally defined. It's a relatively trivial complication so code up, and would slow the progrtam a tiny bit, but we'll never get anywhere if the spec. keeps changing... The full (3x3) board has so far been running for 3 hours, and is analysing the 2-moves case, which will take about another 10 hours. The outputs for the 0-moves and 1-move cases are as expected, i.e. ... ... ... (easy exercise for the reader:-) Mike [Non-text portions of this message have been removed] Zak Seidov Message 8 of 28 , Jul 15, 2003 View Source At 2x2 board, the number of n-digit numbers (after n-1 moves) is 4*3^(n-1), so according to Mike's calcs, the percentage of n-digit primes gradually decreases from 1 (n=1 and 2!) to .202=442/2187 (n=8), while suprisingly for n=9, is larger than for n=8: .237=518/2187. At 3x3 board, the number of n-digit numbers (after n-1 moves) is 4*3^(n-1)+4*5^(n-1)+8^(n-1), that is: {9, 40, 200, 1120, 6920, 46240, 327560, 2418400, 18365960}, let's wait for Mike's results... zak Show message history mikeoakes2@aol.com Jul 15, 2003 View Source In a message dated 15/07/03 18:52:24 GMT Daylight Time, seidovzf@... writes: > At 2x2 board, > the number of n-digit numbers (after n-1 moves) is > 4*3^(n-1), > so according to Mike's calcs, > the percentage of n-digit primes gradually decreases > from 1 (n=1 and 2!) to .202=442/2187 (n=8), > while suprisingly for n=9, is larger than for n=8: > .237=518/2187. Zak: I agree with your formula for the count of numbers. But where does 2187 come from? (you seem to have forgotten the "4*") > At 3x3 board, > the number of n-digit numbers (after n-1 moves) is > 4*3^(n-1)+4*5^(n-1)+8^(n-1), that is: > {9, 40, 200, 1120, 6920, 46240, 327560, 2418400, 18365960}, Sorry, but that formula is too simplistic. The correct counts (found by a program, execution time 15 GHz-mins) are:- n count 1 9 2 40 3 200 4 952 5 4624 6 22272 7 107648 8 519552 9 2509056 10 12113920 11 58492928 12 282425344 13 1363677184 14 6584401920 Can anyone find (e.g.) a recurrence relation for these values, I wonder? Mike [Non-text portions of this message have been removed] sleephound Jul 15, 2003 View Source Here's the relationship 3 ways - as a Matrix recursion, as an explicit formuula, and as a 3-term recursion. MATRIX VERSION: There are three kinds of squares - corner squares, side squares, and middle squares. From a Corner you can move to two side squares or a middle square, so C(n) = 2*S(n-1) + M(n-1) From a side you can move to two corners, two sides, or a middle squareL S(n) = 2*C(n-1) + 2*S(n-1) + M(n-1) From the middle you can move to four corners or four sides, so M(n) = 4*C(n-1) + 4*S(n-1) If we let Xn be the vector of moves possible from Corner, Side, orMiddle in n steps, we have the Matrix Recursion X(n) = M * X(n-1) Where M is 0 2 1 2 2 1 4 4 0 The initial condition is a vector of all ones, usually denoted as "e". The total number of moves can start in any of 4 corners, 4 sides, or the middle, so the total number of moves in "N+1" steps is [4 4 1] * M^N * e EXPLICIT SOLUTION The Eigenvalues of M are -2, 2+2sqrt(2) and 2-2sqrt(2). Knowing this, we also know there should be an answer in the form of a(-2)^N + b*(2+2sqrt(2))^N + c*(2-2sqrt(2))^N The values turn out to be a=1/2 b=17/4 + 3sqrt(2) c=17/4 - 3sqrt(2) RECURSION Since the matrix is 3x3, there should be a 3-term recursion. It turnsout to be F(n) = 2*F(n-1) + 12*F(n-2) + 8*F(n-3) All three solutions will exactly reproduce your table and can be used to extend the table. Show message history mikeoakes2@aol.com Jul 16, 2003 View Source In a message dated 16/07/03 00:27:22 GMT Daylight Time, sleephound@... writes: > Here's the relationship 3 ways - as a Matrix recursion, as an explicit > formuula, and as a 3-term recursion. > A perfect presented solution! (I had found that RECURSION by way of the identical MATRIX VERSION argument, and was going to wait before posting; but I had missed your eigenvalue trick to get that nice EXPLICIT SOLUTION.) Of course, exactly the same steps will give formulae for the MxN square. If we represent the different "kinds of squares" by "a", "b", ..., then for the boards a a and a a a a there will clearly be a recurrence relation of the form F(n) = c_1 * F(n-1); for the boards a b a a b a and a b b a a b b a there will be a recurrence relation of the form F(n) = c_1 * F(n-1) + c_2 * F(n-2); for the boards a b a b c a a b a a b b a b c c b a b b a and a b b a b c c b b c c b a b b a there will be a relation of the form F(n) = c_1 * F(n-1) + c_2 * F(n-2) + c_3 * F(n-3; and so on. There's one other remarkable property of those 3x3 counts that I haven't fathomed yet. If you completely factorise each of the count(n) values, you find that count(2*n) and count(2*n+1) "pair up" in this remarkable fashion:- count(2*n) = 2^(n-1) * s * t count(2*n+1) = 2^n * t^2 where s = 4, 14, 12, 41, 140, 239, ... and t = 3, 10, 34, 116, 396, 1352, 4616, ... Anyone? Mike [Non-text portions of this message have been removed] Zak Seidov Jul 16, 2003 View Source Are you sure that there are no misprints: ... a(-2)^N + b*(2+2sqrt(2))^N + c*(2-2sqrt(2))^N The values turn out to be a=1/2 b=17/4 + 3sqrt(2) c=17/4 - 3sqrt(2) ... zak --- In primenumbers@yahoogroups.com, "sleephound" <sleephound@y...> wrote: > Here's the relationship 3 ways - as a Matrix recursion, as an explicit > formuula, and as a 3-term recursion. > > MATRIX VERSION: > There are three kinds of squares - corner squares, > side squares, and middle squares. From a Corner > you can move to two side squares or a > middle square, so > > C(n) = 2*S(n-1) + M(n-1) > > From a side you can move to two corners, > two sides, or a middle squareL > > S(n) = 2*C(n-1) + 2*S(n-1) + M(n-1) > > From the middle you can move to four corners > or four sides, so > > M(n) = 4*C(n-1) + 4*S(n-1) > > If we let Xn be the vector of moves possible from > Corner, Side, orMiddle in n steps, we have the Matrix Recursion > > X(n) = M * X(n-1) > > Where M is > 0 2 1 > 2 2 1 > 4 4 0 > > The initial condition is a vector of all ones, usually > denoted as "e". The total number of moves can start in > any of 4 corners, 4 sides, or the middle, so the total > number of moves in "N+1" steps is > > [4 4 1] * M^N * e > > > > EXPLICIT SOLUTION > The Eigenvalues of M are -2, 2+2sqrt(2) and 2-2sqrt(2). > Knowing this, we also know there should be an answer in > the form of > > a(-2)^N + b*(2+2sqrt(2))^N + c*(2-2sqrt(2))^N > > The values turn out to be > a=1/2 > b=17/4 + 3sqrt(2) > c=17/4 - 3sqrt(2) > > > RECURSION > Since the matrix is 3x3, there should be a 3-term recursion. > It turnsout to be > > F(n) = 2*F(n-1) + 12*F(n-2) + 8*F(n-3) > > > All three solutions will exactly reproduce your table > and can be used to extend the table. > > > > > --- In primenumbers@yahoogroups.com, mikeoakes2@a... wrote: > > In a message dated 15/07/03 18:52:24 GMT Daylight Time, > seidovzf@y... > > writes: > > > > > At 2x2 board, > > > the number of n-digit numbers (after n-1 moves) is > > > 4*3^(n-1), > > > so according to Mike's calcs, > > > the percentage of n-digit primes gradually decreases > > > from 1 (n=1 and 2!) to .202=442/2187 (n=8), > > > while suprisingly for n=9, is larger than for n=8: > > > .237=518/2187. > > > > Zak: I agree with your formula for the count of numbers. > > But where does 2187 come from? (you seem to have forgotten the "4*") > > > > > At 3x3 board, > > > the number of n-digit numbers (after n-1 moves) is > > > 4*3^(n-1)+4*5^(n-1)+8^(n-1), that is: > > > {9, 40, 200, 1120, 6920, 46240, 327560, 2418400, 18365960}, > > > > Sorry, but that formula is too simplistic. > > > > The correct counts (found by a program, execution time 15 GHz- mins) Show message history sleephound Jul 16, 2003 View Source --- In primenumbers@yahoogroups.com, "Zak Seidov" <seidovzf@y...> wrote: > Are you sure that there are no misprints: > > ... > a(-2)^N + b*(2+2sqrt(2))^N + c*(2-2sqrt(2))^N > > The values turn out to be > a=1/2 > b=17/4 + 3sqrt(2) > c=17/4 - 3sqrt(2) > ... There's a missing "*" between the "a" and the "(-2)". There's a fencepost problem about whether we count the number of moves the king makes or the number of squares the king lands on. Because of this difference, the "N" in this expression is one different from Mike's "N" values. I don't think there is any other issue. Zak Seidov Jul 16, 2003 View Source > > b=17/4 + 3sqrt(2) > > c=17/4 - 3sqrt(2) > > ... seems to be b=17/4 + 5 sqrt(2) c=17/4 - 5 sqrt(2) ?? zak --- In primenumbers@yahoogroups.com, "sleephound" <sleephound@y...> wrote: > --- In primenumbers@yahoogroups.com, "Zak Seidov" <seidovzf@y...> > wrote: > > Are you sure that there are no misprints: > > > > ... > > a(-2)^N + b*(2+2sqrt(2))^N + c*(2-2sqrt(2))^N > > > > The values turn out to be > > a=1/2 > > b=17/4 + 3sqrt(2) > > c=17/4 - 3sqrt(2) > > ... > > There's a missing "*" between the "a" and the "(-2)". > > There's a fencepost problem about whether we count the number of moves > the king makes or the number of squares the king lands on. Because of Show message history sleephound Jul 16, 2003 View Source --- In primenumbers@yahoogroups.com, "Zak Seidov" <seidovzf@y...> wrote: > > > b=17/4 + 3sqrt(2) > > > c=17/4 - 3sqrt(2) > > > ... > > seems to be > b=17/4 + 5 sqrt(2) > c=17/4 - 5 sqrt(2) > ?? > zak Evaluating a*(-2)^N + b*(2+2sqrt(2))^N + c*(2-2sqrt(2))^N a=1/2 N Sleep's Zak's 0 9 9 1 40 56 2 200 264 3 952 1272 4 4624 6160 5 22272 29696 6 107648 143488 7 519522 692608 8 2509056 3344640 Zakir Seidov Jul 16, 2003 View Source yes, you are right, misteriously my Mma program kept giving 5s not 3s?? now at last i've found the error, thanks, zak --- sleephound <sleephound@...> wrote: > --- In primenumbers@yahoogroups.com, "Zak Seidov" > <seidovzf@y...> > wrote: > > > > b=17/4 + 3sqrt(2) > > > > c=17/4 - 3sqrt(2) > > > > ... > > > > seems to be > > b=17/4 + 5 sqrt(2) > > c=17/4 - 5 sqrt(2) > > ?? > > zak > > Evaluating a*(-2)^N + b*(2+2sqrt(2))^N + > c*(2-2sqrt(2))^N > a=1/2 > > N Sleep's Zak's > 0 9 9 > 1 40 56 > 2 200 264 > 3 952 1272 > 4 4624 6160 > 5 22272 29696 > 6 107648 143488 > 7 519522 692608 > 8 2509056 3344640 > __________________________________ Do you Yahoo!? SBC Yahoo! DSL - Now only $29.95 per month! http://sbc.yahoo.com Zak Seidov Jul 17, 2003 View Source Numbers of N-move routes of chess king at three boards > > Sleep's Zak's board 3x3 4x4 5x5 > > N > > 0 9 16 25 > > 1 40 84 144 > > 2 200 492 912 > > 3 952 2880 5832 > > 4 4624 16860 37680 > > 5 22272 98700 243264 > > 6 107648 577800 1572768 > > 7 519522 3382500 10164600 > > 8 2509056 19801500 65708928 > > 9 12113920 115920000 424734192 N=0 corresponds to starting cells. Mike and Sleep, what are your figures, please? I've found this solving recurrent equations with Matematica. BTW I'll look for other boards... Zak sleephound Jul 17, 2003 View Source I get the same values. For the 4x4 board the eigenvalues are 0 (5+3sqrt(5))/2 (5-3sqrt(5))/2 The eigenvalue of zero results in a two-term recursion that is only valid from the fourth term (N=3) forward. That recursion is F(N)=5*F(N-1)+5*F(N-2) I guess that in some formal sense the recursion is really F(N)=5*F(N-1)+5*F(N-2)+0*F(N-3) Which "explains" why the recursion doesn't work for N=2. The eigenvalues for the 5x5 board are 0 -3 +sqrt(3) -sqrt(3) 3+2sqrt(3) 3-2sqrt(3) There is a zero eigenvalue here, too, so there should be a five term recursion that isn't valid until the seventh term. --- In primenumbers@yahoogroups.com, "Zak Seidov" <seidovzf@y...> wrote: Show message history mikeoakes2@aol.com Jul 19, 2003 View Source On 16/07/03 I wrote:- > There's one other remarkable property of those 3x3 counts that I haven't > fathomed yet. > > If you completely factorise each of the count(n) values, you find that > count(2*n) and count(2*n+1) "pair up" in this remarkable fashion:- > > count(2*n) = 2^(n-1) * s * t > count(2*n+1) = 2^n * t^2 > > where s = 4, 14, 12, 41, 140, 239, ... > and t = 3, 10, 34, 116, 396, 1352, 4616, ... > After playing around with these factorisations a bit more today, I have found the right way to express them. Sit back and I will show you something magical! The move counts for the 3x3 board (using my/sleephound's formulae) are:- N F(N) 1 9 = 2^0 * (3)^2 2 40 = 2^2 * [2] * (5) 3 200 = 2^3 * (5)^2 4 952 = 2^3 * [7] * (17) 5 4624 = 2^4 * (17)^2 6 22272 = 2^6 * [12] * (29) 7 107648 = 2^7 * (29)^2 8 519552 = 2^7 * [41] * (99) 9 2509056 = 2^8 * (99)^2 10 12113920 = 2^10 * [70] * (169) 11 58492928 = 2^11 * (169)^2 12 282425344 = 2^11 * [239] * (577) 13 1363677184 = 2^12 * (577)^2 14 6584401920 = 2^14 * [408] * (985) 15 31792332800 = 2^15 * (95)^2 The pattern is:- F(2*n) = 2^(2*n-eps) * u(n) * v(n) F(2*n+1) = 2^(2*n+1-eps) * v(n)^2 where eps = 1 - (n mod 2), i.e. eps = 0 if n is odd, else 1. The sequence u(n), i.e. the numbers in [ ] brackets is: 2,7,12,41,70,239,408,... and this is series A084068 in the On-line Encyclopedia of Integer Sequences [OEIS]: http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum =A084068 The sequence v(n), i.e. the numbers in ( ) brackets is: 3,5,17,29,99,169,577,985,... and this is A079496: http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum =A079496 The sequence u(n) can be defined by u(-1) = 0 u(0) = 1 and the following recurrence relations:- u(2*n) = 4*u(2*n-1) - u(2*n-2) u(2*n+1) = 2*u(2*n) - u(2*n-1) The sequence v(n) can be defined by v(-1) = 1 v(0) = 3 v(2*n) = 4*v(2*n-1) - v(2*n-2) v(2*n+1) = 2*v(2*n) - v(2*n-1) which are precisely the same recurrence relations, but different initial values. [Note: this is just like the relationship between the Fibonacci and Lucas series, both of which satisfy f(n) = f(n-1) + f(n-2) but differ in their starting values.] If we tabulate the first few values of these 2 series, we see many relationships between them:- n u(n) v(n) -1 0 1 0 1 3 1 2 5 2 7 17 3 12 29 4 41 99 5 70 169 6 239 577 7 408 985 For odd n, v(n) + u(n) = u(n+1) and v(n) - u(n) = v(n-1) For even n, v(n) + u(n) = 2*u(n+1), and v(n) - u(n) = 2*v(n-1) So, once u(n) has been defined, v(n) is in fact completely specified (including its initial values) by:- v(2*n-1) =u(2*n) - u(2*n-1) v(2*n) = 2*u(2*n+1) - u(2*n) If you write out the differences between successive u(n) terms, you get 1,1,5,5,29,29,169,169,.. which are just the odd v(n)'s. If you write out the differences between successive v(n) terms, you get 2,2,12,12,70,70,408,408,.. which are just the odd u(n)'s. Isn't it pretty how the series intertwine with each other? These two series don't seem to have been connected with each other before. And who would have thought that they had anything to do with King moves on a 3x3 board! Mike [Non-text portions of this message have been removed] mikeoakes2@aol.com Jul 20, 2003 View Source A final despatch from the programming front:- I have speeded up the program by a factor of about 30, by 3 independent tricks:- (a) If you distribute the numbers 0 .. 9 over a 3x3 board, there are 10^9 arrangements; but by taking advantage of the symmetry of the square, this can be reduced by a factor of almost 8: rotate until the biggest digit is in the top-left-hand corner (say), and then flip along the main diagonal so that the top-right-hand corner digit is at least as big as the bottom-left-hand corner digit. (b) at the last-but-one stage of the recursion, don't do the place-digit-and-see-if-resulting-number-is-prime procedure at all if the resulting number would be divisible by 2 or 3 or 5; by keeping the sum-of-digits-so-far mod 3 at every stage of the recursion, the cost of eliminating multiples of 3 is effectively zero, as is the cost of checking that the final digit being placed is 1 or 3 or 7 or 9; there are only 8 numbers out of every 30 which pass this test, giving a speed-up factor of about 3. (c) a coding improvement gave about another 30% speed-up: store the path in a single global vector, so that only one memory byte needs to be updated when extending or back-tracking the recursive enumeration of all King-move paths. So, the final program does in a day what the original would take a month for; and after 4.5 days continuous running at 2.08 (Athlon (Barton)) GHz, here are the results. 2x2 board --------------- 1+no. best no. of no. of prime of moves board primes numbers ratio 1 2222 4 4 1.000 2 1111 12 12 1.000 3 3113 28 48 0.583 4 7333 48 192 0.250 5 7111 132 768 0.172 6 9111 384 3072 0.125 7 3313 1008 12288 0.082 8 7117 1768 49152 0.036 9 3111 6216 196608 0.032 3x3 board --------------- 1+no. best no. of no. of prime of moves board primes numbers ratio 1 222222222 9 9 1.000 2 111111111 40 40 1.000 3 111333111 162 200 0.810 4 111181111 464 952 0.487 5 777797777 2112 4624 0.457 6 111919111 8880 22272 0.399 The 2x2 board took 6 secs. The last row of the 3x3 table took 3.5 days - it had to construct and then test the primality of about (10^9/8)*(22272*8/30)=750,000,000,000 6-digit numbers. It has been a fun exercise, but this program will now be "retired". Anyone want to extend these results? Mike [Non-text portions of this message have been removed] Zak Seidov Jul 20, 2003 View Source Mike, it's a real pity that your >program will now be "retired". I don't think that none else can meet the challenge... Still, if you keep your results, can your present number of distinct primes and primes themselves? Also it should be taken from the beginning that 9 digits all are present and only their arrangements counts... In that case I think your great efforts will give even more interesting results. Anyway, you did a great JOB, thank you on behalf of THE KING MOVING FOR PRIMES, Zak Personal request: is your program user-friendly, can you present it say to me, i need only the part which counts the moves (say 6-step etc) FOR THE GIVEN POSITION AT BOARD, say 123456789, i don't need (if any) a part for search of best position > 6 8880 22272 you know 22272 is nothing to calculate (i mean time not programming), and i use only Mathematica, thank you again, Zak Show message history Décio Luiz Gazzoni Filho Jul 20, 2003 View Source -----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 > The 2x2 board took 6 secs. > The last row of the 3x3 table took 3.5 days - it had to construct and then > test the primality of about (10^9/8)*(22272*8/30)=750,000,000,000 6-digit > numbers. Was the primality testing slowing down your program? Because there are only 900k 6-digit numbers (assuming no other restrictions placed on these numbers, I haven't been following this problem to tell), and half of them are even, so you could easily store a bitmap of the odd ones in 57 KB, meaning this bitmap would stay inside the L1 D-cache of your Athlon at all times. But perhaps you've implemented this already? Hope that helps. Décio -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.2.2 (GNU/Linux) iD8DBQE/GtLZce3VljctsGsRAp7eAJ4n8Z4qeg1zK6frf+13b86YGPWYsQCdFhys 2Uzysv7B75IQ5VsTBCVQ8JA= =DSXg -----END PGP SIGNATURE----- mikeoakes2@aol.com Jul 20, 2003 View Source In a message dated 20/07/03 18:35:59 GMT Daylight Time, decio@... writes: > Was the primality testing slowing down your program? Because there are only > 900k 6-digit numbers (assuming no other restrictions placed on these > numbers, > I haven't been following this problem to tell), and half of them are even, > so > you could easily store a bitmap of the odd ones in 57 KB, meaning this > bitmap > would stay inside the L1 D-cache of your Athlon at all times. But perhaps > you've implemented this already? > The primality test was indeed simply a 1-bit test in a bit-array of all odd primes (as you recommend), and therefore ultra-fast. For the 2x2 board up to depth 9, this bit array (all primes < 10^9) was 5*10^8 bits = 62.5 Mb, and took about a couple of mins to initialize. Thanks for your interest. Mike [Non-text portions of this message have been removed] Zak Seidov Jul 20, 2003 View Source I wrote: > Personal request: > is your program user-friendly, > can you present it say to me, > i need only the part which counts the > moves (say 6-step etc) > FOR THE GIVEN POSITION AT BOARD, > say 123456789, At this night i did it myself, and here are some results: i consider 3x3 board with figures 1,2,3,4,5,6,7,8,9 each in one cell, then (for a time being) not taking into account rotations and reflections, there are totally 9! = 362880 positions, starting with 123/456/789 and ending with 987/654/321 (which of course are the same!). What i did till now is a complete enumeration of all 2-move routes in all 362880 positions, (for 1-move we have for all positions the same, i.e. four primes: 2,3,5,7 which are ALL 1D primes). We have exactly 20 2D primes: 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97. So formally in all 362880 positions it may be minimum 0 2D primes and maximum 20 2D primes. In turns out however that: a) minimum number of 2D primes is FOUR and occur in 240 positions, starting with 123586749 (primes 23,83,47,89) and ending with 963485127(=127584369!) (primes 47,53,83,89) b) maximum number of 2D primes is EIGHTEEN and occur in 192 positions, starting with 234517896 and 234571896 (both with all 2D primes except 29, and 83), and ending with 234817596 and 234871596 (both with all 2D primes except 29, and 53). Sure it's interesting to remove all reflections/rotations, but i'd not done it yet... Instead, i did a full analysis of the "initial" position 123456789: 1D primes: {2, 3, 5, 7} (all possible 1D primes) the part of 1D primes from all 1D numbers at the board is p1=4/9=0.4444 2D primes: {23, 41, 47, 53, 59, 89} (6 2D primes of all 20 2D primes) the part of 2D primes from all 2D numbers at the board is p2=6/40=3/20=0.1500 3D primes: {151, 157, 241, 251, 257, 263, 269, 353, 359, 421, 457, 487, 521, 523, 541, 547, 563, 569, 587, 653, 659, 751, 757, 787, 853, 857, 859, 863, 953} (29 3D primes) p3=29/200 = 0.145 4D primes: {1259,1423,1451,1453,1459,1487,1489,1523,2141, 2153,2351,2357,2423,2459,2521,2621,2657,2659,2687,2689, 3251,3253,3257,3259,3541,3547,3623,3659,4153,4157,4159, 4241,4253,4259,4523,4547,4751,4759,4787,4789,5147,5153, 5323,5351,5623,5651,5653,5657,5659,5689,5741,5851,5857, 5869,5953,5987,6247,6257,6263,6269,6323,6353,6359,6521, 6547,6563,6569,6841,6857,6863,6869,6959,7451,7457,7459, 7487,7489,7523,7541,7547,7589,7841,7853,8423,8521,8563, 8623,8689,8741,8747,8753,8951,8963,8969,9521,9547,9587, 9623,9689,9851,9857,9859} (102 4D primes) p4=102 / 952 = 0.107143 5D primes: {12157, 12323,..., 98953, 98963} (394 5D primes) p5=394 / 4624 = 0.0852076 6D primes: {121259, 121421, ...,989687, 989869} (1555 6D primes) p6=1555 / 22272 = 0.0698186 7D primes: {1212121, 1212487,..., 9898457, 9898547} (5995 7D primes) p7=5995 / 107648 = 0.0556908 8D primes: {12121423, 12121451, ...,98989687, 98989841} (25072 8D primes) p8=25072 / 519552 = 0.048257 9D primes: {121212521,121212569,...,989898653,989898989} (106057 9D primes) p9=106057 / 2509056 = 0.0422697 10D primes: (sorry N/A yet) p10=? / 12113920 = ? Anybody wish to check and beat this? Zak The King Prime We often err but never lie -- In primenumbers@yahoogroups.com, "Zak Seidov" <seidovzf@y...> wrote: > Mike, > it's a real pity that your > > >program will now be "retired". > > I don't think that none else > can meet the challenge... > > Still, if you keep your results, > can your present number of distinct primes > and primes themselves? > > Also it should be taken from the beginning > that 9 digits all are present > and only their arrangements counts... > > In that case I think your great efforts > will give even more interesting results. > > Anyway, you did a great JOB, > thank you on behalf of > THE KING MOVING FOR PRIMES, > Zak > > Personal request: > is your program user-friendly, > can you present it say to me, > i need only the part which counts the > moves (say 6-step etc) > FOR THE GIVEN POSITION AT BOARD, > say 123456789, > i don't need (if any) a part for search of best position > > > 6 8880 22272 > > you know 22272 is nothing to calculate > (i mean time not programming), > and i use only Mathematica, > thank you again, > Zak > > > > --- In primenumbers@yahoogroups.com, mikeoakes2@a... wrote: > > A final despatch from the programming front:- > > > > I have speeded up the program by a factor of about 30, by 3 > independent > > tricks:- > > (a) If you distribute the numbers 0 .. 9 over a 3x3 board, there > are 10^9 > > arrangements; but by taking advantage of the symmetry of the > square, this can be > > reduced by a factor of almost 8: rotate until the biggest digit is > in the > > top-left-hand corner (say), and then flip along the main diagonal > so that the > > top-right-hand corner digit is at least as big as the bottom-left- > hand corner > > digit. > > (b) at the last-but-one stage of the recursion, don't do the > > place-digit-and-see-if-resulting-number-is-prime procedure at all > if the resulting number > > would be divisible by 2 or 3 or 5; by keeping the sum-of-digits- so- > far mod 3 at > > every stage of the recursion, the cost of eliminating multiples of > 3 is > > effectively zero, as is the cost of checking that the final digit > being placed is 1 or > > 3 or 7 or 9; there are only 8 numbers out of every 30 which pass > this test, > > giving a speed-up factor of about 3. > > (c) a coding improvement gave about another 30% speed-up: store the > path in a > > single global vector, so that only one memory byte needs to be > updated when > > extending or back-tracking the recursive enumeration of all King- > move paths. > > > > So, the final program does in a day what the original would take a > month for; > > and after 4.5 days continuous running at 2.08 (Athlon (Barton)) > GHz, here are > > the results. > > > > 2x2 board > > --------------- > > 1+no. best no. of no. of prime > > of moves board primes numbers ratio > > 1 2222 4 4 1.000 > > 2 1111 12 12 1.000 > > 3 3113 28 48 0.583 > > 4 7333 48 192 0.250 > > 5 7111 132 768 0.172 > > 6 9111 384 3072 0.125 > > 7 3313 1008 12288 0.082 > > 8 7117 1768 49152 0.036 > > 9 3111 6216 196608 0.032 > > > > 3x3 board > > --------------- > > 1+no. best no. of no. of prime > > of moves board primes numbers ratio > > 1 222222222 9 9 1.000 > > 2 111111111 40 40 1.000 > > 3 111333111 162 200 0.810 > > 4 111181111 464 952 0.487 > > 5 777797777 2112 4624 0.457 > > 6 111919111 8880 22272 0.399 > > > > The 2x2 board took 6 secs. > > The last row of the 3x3 table took 3.5 days - it had to construct > and then > > test the primality of about (10^9/8)*(22272*8/30)=750,000,000,000 6- > digit > > numbers. > > > > It has been a fun exercise, but this program will now be "retired". Show message history mikeoakes2@aol.com Jul 21, 2003 View Source In a message dated 21/07/03 06:52:46 GMT Daylight Time, seidovzf@... writes: > I wrote: > > Personal request: > > is your program user-friendly, > > can you present it say to me, > > i need only the part which counts the > > moves (say 6-step etc) > > FOR THE GIVEN POSITION AT BOARD, > > say 123456789, > > At this night i did it myself, > and here are some results: > > i consider 3x3 board with figures 1,2,3,4,5,6,7,8,9 > each in one cell, then (for a time being) > not taking into account rotations and reflections, > there are totally 9! = 362880 positions, > starting with 123/456/789 and ending with 987/654/321 > (which of course are the same!). > [snip] > Anybody wish to check and beat this? Nice work, Zak, and everything you posted seems to be correct. Your yesterday's post had already inspired me to alter my program for this different-digit-in-each-square problem for the 3x3 board. It is of course a much smaller space of boards to search: 9! instead of 10^9. So it only took 4 hrs 10 mins to analyse all the way up to depth 9. Here are the results, extending yours:- 3x3 board --------------- 1+no. best no. of no. of prime of moves board primes numbers ratio 1 452678193 4 9 0.444 2 614738295 18 40 0.450 3 825317496 49 200 0.245 4 816579234 169 952 0.178 5 876913542 623 4624 0.135 6 836719245 2444 22272 0.110 7 896413572 9655 107648 0.090 8 896713245 39964 519552 0.077 9 825713496 169901 2509056 0.068 This version of the problem is, I agree, rather more "natural" than the unrestricted-digit one, but has the disadvantage that it doesn't readily generalise to other board sizes - except perhaps to 2x5. Mike [Non-text portions of this message have been removed] Jon Perry Jul 21, 2003 View Source A novel 'call me Carlos' extension, which 3*3(*3) board produces the most primes where each square (cube) is itself a distinct prime? The obvious extension of the King into 3D applies. Jon Perry perry@... http://www.users.globalnet.co.uk/~perry/maths/ http://www.users.globalnet.co.uk/~perry/DIVMenu/ BrainBench MVP for HTML and JavaScript http://www.brainbench.com Zakir Seidov Jul 21, 2003 View Source Jon, here my initial results: Take 3x3 board with 9 first primes {2,3,5,7,11,13,17,19,23} each in one cell, then 2-move routes give minimal 6 primes (in 224 positions), and maximal 22 primes (in 96 positions), two examples: position: {19,13,17,7,3,11,5,23,2}, 22 primes: {23,37,53,73,113,137,173,193,197,211,223,233,311,313, 317,523,719,1117,1123,1319,1913,2311} position: {2,7,11,17,5,13,19,23,3}, 6 primes: {53,137,233,313,523,1723}. I can't yet do it for longer routes... Zak On Routes --- Jon Perry <perry@...> wrote: > A novel 'call me Carlos' extension, > > which 3*3(*3) board produces the most primes where > each square (cube) is > itself a distinct prime? > > The obvious extension of the King into 3D applies. > > Jon Perry > perry@... > http://www.users.globalnet.co.uk/~perry/maths/ > http://www.users.globalnet.co.uk/~perry/DIVMenu/ > BrainBench MVP for HTML and JavaScript > http://www.brainbench.com > > __________________________________ Do you Yahoo!? SBC Yahoo! DSL - Now only $29.95 per month! http://sbc.yahoo.com Zak Seidov Message 28 of 28 , Jul 23, 2003 View Source Mike and all, I have expansion in the direction of larger board but only for N=2 routes (that is concatenations of any two adjacent cells). Take MxM board with numbers from 1 to M^2 in each cell, all arranged in "the first lexicographic order": 1, 2,...,M M+1, M+2,...,2M ....................... ....................... ....................... M(M-1)+1,M(M-1)+2,...M^2. Then number NP of primes for each M is {M, NP}: {1,0},{2,5},{3,6},{4,17},{5,27}, {6,30},{7,42},{8,61},{9,70}, {10,88},{11,99},{12,113},{13,129}, {14,139},{15,174},{16,219},{17,250}, {18,273},{19,314},{20,274},{21,220}, {22,239},{23,343},{24,486},{25,422}, {26,457},{27,356},{28,514},{29,554}, {30,722},{31,787},{32,650},{33,662}, {34,533},{35,749},{36,770},{37,1004}, {38,878},{39,885},{40,922},{41,941}, {42,963},{43,854},{44,1090},{45,1130}, {46,1392},{47,1442},{48,1288},{49,1320}, {50,1386},{51,1438},{52,1475},{53,1543}, {54,1568},{55,1468},{56,1492},{57,1737}, {58,1954},{59,2046},{60,2091},{61,2187}, {62,2031},{63,2004},{64,1928},{65,1990}, {66,2048},{67,2289},{68,2533},{69,2415}, {70,2498},{71,2558},{72,2305},{73,2320}, {74,2408},{75,2960},{76,2837},{77,2684}, {78,2783},{79,3058},{80,3342},{81,3399}, {82,3529},{83,3396},{84,3404},{85,3458}, {86,3758},{87,3656},{88,3789},{89,3858}, {90,3870},{91,3940},{92,4038},{93,4347}, {94,4442},{95,4520},{96,4589},{97,4547}, {98,4443},{99,4477},{100,4722}, {200,17007},{300,35924}, {400,58903},{500,87057}. Remarkably, NP is NOT a strictly monotonic function of M. Is there any formula NP(M)? Anybody wish to check and expand this? Zak