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