Conference rusure::math

        Hint: :-)
        
        Just thinking for a few momemts after reading the problem
        I figured out what N was.
        
        Dan

Drat! I just discovered that the solution is not unique. What a 
disappointment! (I overlooked a class of solutions to the Q-problem that 
contains at least one other solution. I will have to tighten up the 
analysis.)

 :-(

        (n = 7)
        
          _______________		  _______________
        7 | |Q| | | | | |		7 | | | | | |Q| |
        6 | | | | |Q| | |		6 | | |Q| | | | |
        5 |Q| | | | | | |		5 |Q| | | | | | |
        4 | | | |Q| | | |		4 | | | |Q| | | |
        3 | | | | | | |Q|		3 | | | | | | |Q|
        2 | | |Q| | | | |		2 | | | | |Q| | |
        1 | | | | | |Q| |		1 | |Q| | | | | |
          ---------------		  ---------------
        Prime:	5724613			Prime:	5164273
        
        There are no solutions to the n queens problem for n < 4.
        The use of digits suggests n < 10.  For n = 5, 6, 8, and 9 
        the sum of the digits 1+...+n is a multiple of three and
        so no permutation can yield a prime.  A quick examination
        of the diagram in .0 shows there are no prime solutions
        to the 4-queens problem.  Therefore it makes sense to
        search for solutions with n = 7.  I went into VAX LISP
        and generated a list of all 5040 permutations and
        rejected those that didn't yield primes, leaving 534
        permutations which I then tested for 7-queenness.  The
        two passed are above.
        
        Dan

Good work, Dan. You could have saved some effort by working from the set of 
solutions to the 7-queens problem and testing for primality only those that 
end in 1,3 or 7; that way you only need to factor a couple of dozen 
candidates. But your solutions are the ones we found.

        Thank you.  I was hoping to avoid generating the
        solutions to the 7-queens problem. :-)  It was easy to
        generate all of the permutations interactively in VAX
        LISP, and to filter those for primes, and it seemed
        [before I started] there wouldn't be that many that were
        prime.  Unfortunately, way too many were prime, and so I
        had to filter the non-7-queens permutations anyway.
        
        Roughly how many of 5040 seven-digit numbers should I
        have expected to be prime?
        
        Dan
        

        Oh, and *my* effort wouldn't have been any less.  I had
        to type in each "filter" as a function and map each over
        the permutations.  Doing them in the other order would at
        most have saved some CPU and elapsed time. :-)
        
        Dan

.5>     Roughly how many of 5040 seven-digit numbers should I
.5>     have expected to be prime?
        
    Probably wrong, but I'd guess about 0405.
    
      John

    I would expect more primes than from a set of random seven-digit
    numbers.  Here's why:

    Think of using a sieve to eliminate all non-primes, in order to leave
    only the primes.

    First you sieve with 2.  In a random set of seven digit numbers, half
    would be eliminated this way.  However out of the seven digits
    available 3 are even.  Therefore only 3/7 (=.43) of the permutations will
    have a low order digit which is even, and therefore 4/7 (=.57) of the
    permutations will survive the first step.

    Next you sieve with 3.  In a random set of seven digits, a further 1/3
    would be eliminated this way.  At this point in the process of sieving
    the random set we would have eliminated 2/3 of the candidates (1/2 +
    1/3*1/2) leaving 1/3 potential primes.  A number is divisible by 3,
    however, only if the sum of its digits is divisible by 3, regardless
    of the order of the digits.  Since the sum of the digits 1 to 7 is
    not divisible by 3, none of the permutations will be eliminated at
    this stage.  4/7 of the permutations also survive the second step.

    The next step is to sieve with 5.  As it turns out, the remaining
    permuted numbers are "richer" in numbers divisible by 5 (1 out of 4)
    than the randomly selected ones (1 out of 5), but this is not enough to
    make up for the earlier "advantage" for the permuted numbers in
    producing primes.  The score at this point is that 4/15 (=.27) of the
    randomly selected numbers are candidates for primeness, while 3/7
    (=.42) of the permutations are candidates for primeness.

    Quiting at this point, we see that the permutations of the digits 1-7
    are likely to be particularly rich in primes, since they are "poor"
    in numbers divisible by 2 or 3.

    (My guess is, by the way, that 7 does not favor either one
    significantly, and that the "randoms" have more numbers divisible by
    11).

				    Topher

>    The next step is to sieve with 5.  As it turns out, the remaining
>    permuted numbers are "richer" in numbers divisible by 5 (1 out of 4)
>    than the randomly selected ones (1 out of 5), ...

Umm. I think that's 1 out of 7, not 4... no zeroes. So 5 as a divisor is 
rarer than normal.

The larger divisors appear superficially to be about normally frequent.

        No, after taking out the numbers ending in 2, 4, or 6
        (for being even), then only the numbers ending in 1, 3,
        5, and 7 are left...and 1/4 of those end in 5.
        
        Dan

.8>    producing primes.  The score at this point is that 4/15 (=.27) of the
.8>    randomly selected numbers are candidates for primeness, while 3/7
.8>    (=.42) of the permutations are candidates for primeness.
    
    I accept your logic will produce a better estimate.  But what is it?
    (3/7) * 0405 / (4/15) ~= 651, or something else?
    
      John

    OK.  Let's give it a shot.

    There are 5040 (7!) permutations.  Of those 5040*3/7=2160 are not
    divisible by 2, 3, or 5.  Call these the "candidate set."

    If we assume that there are no significant further divisibility biases
    in this set (I suspect there are, in fact, further biases, but their
    effect will be quite small), then the candidate set can be treated as a
    random selection of the integers between 1234567 and 7654321
    (inclusive) which are not divisible by 2, 3, or 5 (call this the
    population set).  This means that the proportion of the candidate set
    which is prime will be approximately equal to the proportion of the
    population set which is prime.

    The size of the population set is approximately

	(7654321 - 1234567 + 1)*4/15 = 1711934.667

    (see note .8).

    The number of primes in the population set is the same as the number
    of primes in the set of integers between 1234567 and 7654321.  By
    Gauss's prime number theorem that is equal to approximately 

	   7654322         1234567
	------------- - ------------- = 394880.2859
	 ln(7654322)     ln(1234567)

    The proportion of primes is therefore approximately: .2306631752 (its
    easier to keep the extra precision MAPLE gives me than to decide how
    much to keep).  Multiplying that by 2160 gives us 498.

    That's not real close to the 534 that Dan says he found in reply .3,
    but it is obviously better than the estimate of 310 primes that you
    would guess without taking into account the divisibility constraints.

    There are four possible reasons for the discrepancy (ignoring the
    distinct possibility of an error on my part -- that's for you guys
    to find):

	    1) Dan's primality tester counted some composites as primes.

	    2) There are further divisibility biases with significant
	       effects in the permutations.

	    3) The prime number theorem is not sufficiently accurate.

	    4) The permutations just happen to make an extreme biased
	       sample (in regards to primality) on the integers between
	       1234567 and 7654321.

    Of course a combination of these factors may be the cause.

    Things to check out: rate of convergence/accuracy as approximation
    results for the prime number theorem; use of some of the more
    accurate modern prime-number-density results; replication of Dan's
    figure for the number of 7-permutation primes; Monte Carlo sampling
    of the "population set" to derive a figure for the proportion of
    primes.

    Any takers?

					Topher

n/ln n is really a very coarse estimate of the number of primes < n. A far 
better estimate is due to Riemann:

	Li(x) = integral(1/ln t) from t=2 to x
	PrimesLessThan(n) ~= Li(n) - Li(n^.5)/2

Using MAPLE and this estimate, I find that the number of primes between
1234567 and 7654321 is about 4.38E5, so Topher's proportion becomes about
.256 and the product of that by 2160 is ~553, which is quite accurate given
the quality of these estimation formulae (rarely better than 3 places). 


Ref.: A. H. Beiler, "Recreations in the Theory of Numbrs", P. 224.

        Come on, just ask MAPLE how many primes there are in
        [1234567,7654321]. :-)
        
        Dan

RE: .13 (Lynn)

    Great, Lynn.  The approximation in terms of Li was what I had in mind
    when I refered to:

>    use of some of the more accurate modern prime-number-density results;

    but I didn't remember the details, nor was I sure that a tighter
    approximation wasn't available now.  I was hoping for something within
    1 or 2% (this gets us about 3.5%) of Dan's answer.  Does your source
    give estimates of the error for Riemann's method?

					    Topher

.13>	Li(x) = integral(1/ln t) from t=2 to x
.13>	PrimesLessThan(n) ~= Li(n) - Li(n^.5)/2
.13>
.13> Using MAPLE and this estimate, I find that the number of primes between
.13> 1234567 and 7654321 is about 4.38E5, so Topher's proportion becomes about
    
    Lynn, do you know how MAPLE calculated the definite integral for Li(x)?
    
      John
    
    p.s., thanks for rearranging the reply with the very long lines, I can't read past column 80 with the character-cell version of NOTES I use.

re .16,
    
>    p.s., thanks for rearranging the reply with the very long lines, I can't read past column 80 with the character-cell version of NOTES I use.

Like that line?, which turns out to be:

>    p.s., thanks for rearranging the reply with the very long lines, I can't
>read past column 80 with the character-cell version of NOTES I use.

Possibilities in character-cell notes:

	Use REPLY, go into the extract window, select and remove the
	long lined text, go back to the reply editing window, insert
	the text, position the cursor over a paragraph, hit the Do key,
	and enter the FILL command.  Do this for each paragraph.

	Or, use EXTRACT/BUFFER buffer_name
		EVE BUFFER buffer_name
	and again FILL each paragraph.  Use ctrl-z to get back to notes.

In xnotes, though, just select the text of the message, call up the reply
window, press MB2 to insert the selected text, then press the Wrap Text
button. :-)

Dan

Re .15:
>	... 				I was hoping for something within
>    1 or 2% (this gets us about 3.5%) of Dan's answer.  Does your source
>    give estimates of the error for Riemann's method?

The distribution of primes in this region is so irregular that no simple
approximation can be very good over all of it. However, Riemann's approx.
is within 1% in the region of interest. According to Beiler, ''Riemann's
graph [of np(n) and the function I cited] touches or crosses the "no
deviation" axis no less than 19 times in the interval between 1 and
9000000.'' The absolute error is <60 below n~8,800,000.

I think it's our process of elimination that is not completly accurate.


Re .16: I am not sure what integration method is used by MAPLE - I think I
recall reading that it's something like an adaptive Runge-Kutta - but the
output agrees with Beiler's tables to 5 sig figs so it's not too far off.
MAPLE did NOT integrate it symbolically.