Non-attacking Queens

 I came across this interesting tweet today. Figure 1 shows a snapshot of it.

Figure 1

Here is the Python code that was used:

from itertools import permutations

col = range(8)

for vec in permutations(col):

    if (8 == len(set(vec[i]+i for i in col) == len(set(vec[i]-i for i in col))):

        print(vec)

The algorithm works perfectly well. Here is the output:

(0, 4, 7, 5, 2, 6, 1, 3)

(0, 5, 7, 2, 6, 3, 1, 4)

(0, 6, 3, 5, 7, 1, 4, 2)

(0, 6, 4, 7, 1, 3, 5, 2)

(1, 3, 5, 7, 2, 0, 6, 4)

(1, 4, 6, 0, 2, 7, 5, 3)

(1, 4, 6, 3, 0, 7, 5, 2)

(1, 5, 0, 6, 3, 7, 2, 4)

(1, 5, 7, 2, 0, 3, 6, 4)

(1, 6, 2, 5, 7, 4, 0, 3)

(1, 6, 4, 7, 0, 3, 5, 2)

(1, 7, 5, 0, 2, 4, 6, 3)

(2, 0, 6, 4, 7, 1, 3, 5)

(2, 4, 1, 7, 0, 6, 3, 5)

(2, 4, 1, 7, 5, 3, 6, 0)

(2, 4, 6, 0, 3, 1, 7, 5)

(2, 4, 7, 3, 0, 6, 1, 5)

(2, 5, 1, 4, 7, 0, 6, 3)

(2, 5, 1, 6, 0, 3, 7, 4)

(2, 5, 1, 6, 4, 0, 7, 3)

(2, 5, 3, 0, 7, 4, 6, 1)

(2, 5, 3, 1, 7, 4, 6, 0)

(2, 5, 7, 0, 3, 6, 4, 1)

(2, 5, 7, 0, 4, 6, 1, 3)

(2, 5, 7, 1, 3, 0, 6, 4)

(2, 6, 1, 7, 4, 0, 3, 5)

(2, 6, 1, 7, 5, 3, 0, 4)

(2, 7, 3, 6, 0, 5, 1, 4)

(3, 0, 4, 7, 1, 6, 2, 5)

(3, 0, 4, 7, 5, 2, 6, 1)

(3, 1, 4, 7, 5, 0, 2, 6)

(3, 1, 6, 2, 5, 7, 0, 4)

(3, 1, 6, 2, 5, 7, 4, 0)

(3, 1, 6, 4, 0, 7, 5, 2)

(3, 1, 7, 4, 6, 0, 2, 5)

(3, 1, 7, 5, 0, 2, 4, 6)

(3, 5, 0, 4, 1, 7, 2, 6)

(3, 5, 7, 1, 6, 0, 2, 4)

(3, 5, 7, 2, 0, 6, 4, 1)

(3, 6, 0, 7, 4, 1, 5, 2)

(3, 6, 2, 7, 1, 4, 0, 5)

(3, 6, 4, 1, 5, 0, 2, 7)

(3, 6, 4, 2, 0, 5, 7, 1)

(3, 7, 0, 2, 5, 1, 6, 4)

(3, 7, 0, 4, 6, 1, 5, 2)

(3, 7, 4, 2, 0, 6, 1, 5)

(4, 0, 3, 5, 7, 1, 6, 2)

(4, 0, 7, 3, 1, 6, 2, 5)

(4, 0, 7, 5, 2, 6, 1, 3)

(4, 1, 3, 5, 7, 2, 0, 6)

(4, 1, 3, 6, 2, 7, 5, 0)

(4, 1, 5, 0, 6, 3, 7, 2)

(4, 1, 7, 0, 3, 6, 2, 5)

(4, 2, 0, 5, 7, 1, 3, 6)

(4, 2, 0, 6, 1, 7, 5, 3)

(4, 2, 7, 3, 6, 0, 5, 1)

(4, 6, 0, 2, 7, 5, 3, 1)

(4, 6, 0, 3, 1, 7, 5, 2)

(4, 6, 1, 3, 7, 0, 2, 5)

(4, 6, 1, 5, 2, 0, 3, 7)

(4, 6, 1, 5, 2, 0, 7, 3)

(4, 6, 3, 0, 2, 7, 5, 1)

(4, 7, 3, 0, 2, 5, 1, 6)

(4, 7, 3, 0, 6, 1, 5, 2)

(5, 0, 4, 1, 7, 2, 6, 3)

(5, 1, 6, 0, 2, 4, 7, 3)

(5, 1, 6, 0, 3, 7, 4, 2)

(5, 2, 0, 6, 4, 7, 1, 3)

(5, 2, 0, 7, 3, 1, 6, 4)

(5, 2, 0, 7, 4, 1, 3, 6)

(5, 2, 4, 6, 0, 3, 1, 7)

(5, 2, 4, 7, 0, 3, 1, 6)

(5, 2, 6, 1, 3, 7, 0, 4)

(5, 2, 6, 1, 7, 4, 0, 3)

(5, 2, 6, 3, 0, 7, 1, 4)

(5, 3, 0, 4, 7, 1, 6, 2)

(5, 3, 1, 7, 4, 6, 0, 2)

(5, 3, 6, 0, 2, 4, 1, 7)

(5, 3, 6, 0, 7, 1, 4, 2)

(5, 7, 1, 3, 0, 6, 4, 2)

(6, 0, 2, 7, 5, 3, 1, 4)

(6, 1, 3, 0, 7, 4, 2, 5)

(6, 1, 5, 2, 0, 3, 7, 4)

(6, 2, 0, 5, 7, 4, 1, 3)

(6, 2, 7, 1, 4, 0, 5, 3)

(6, 3, 1, 4, 7, 0, 2, 5)

(6, 3, 1, 7, 5, 0, 2, 4)

(6, 4, 2, 0, 5, 7, 1, 3)

(7, 1, 3, 0, 6, 4, 2, 5)

(7, 1, 4, 2, 0, 6, 3, 5)

(7, 2, 0, 5, 1, 4, 6, 3)

(7, 3, 0, 2, 5, 1, 6, 4)

In this output, 0 represents the first or bottom row, 1 the second and so on. The case of [0, 6, 3, 5, 7, 1, 4, 2], shown in the tweet, is highlighted above in bold red. I use the Mathematics specific SageMathCell which is built on top of Python and when using this the permutation function is built in (so no need to import) but it uses a capital P. Similarly, the set function uses a capital S. I've modified the code accordingly and have outputted the number of acceptable configurations. Here is the code (permalink):

L=[]
count=0
col = range(8)
for vec in Permutations(col):
    if (8 == len(Set(vec[i]+i for i in col)) == len(Set(vec[i]-i for i in col))):
        count+=1
        L.append(vec)
print("There are",count,"number of ways to arrange 8 non-attacking queens on a chessboard. They are:")
print()
for n in L:
    print(n)

The output is the same as for the Python code except that it displays the fact that there are 92 possible configurations (out of a total of 40320).

So what's going on in this algorithm. Well, let's start with col = 0, 1, 2, 3, 4, 5, 6, 7. Whatever our permutation, the elements in this range get added and subtracted sequentially to the elements in our permutation. Let's use [5, 2, 4, 6, 3, 0, 7, 1] as an example of a permutation that does equate to a successful configuration. This is shown in Figure 2 (created using a Google Worksheet). Note how the top row (Added) and the bottom row (Subtracted) each contain eight distinct numbers so that the set of both rows has a length of 8.

Figure 2

Let's now consider the permutation [5, 2, 4, 6, 3, 0, 7, 1] that does not lead to a successful configuration. This is shown in Figure 3 where it can be noted that both the top and bottom rows each contain duplicate numbers so that the length of the set is not equal to 8.

Figure 3

 It's quite a succinct and clever algorithm and it's easily modifiable to accommodate any size chess board. To investigate this further it's best to modify the algorithm slightly so that it's more flexible. Here we replace the number 8 with a variable called "size". Here is the modified algorithm with size = 7 (permalink).

L=[]
size=7
count=0
col = range(size)
for vec in Permutations(col): 

    if (size == len(Set(vec[i]+i for i in col))== len(Set(vec[i]-i for i in col))):
        count+=1
        L.append(vec)
print("There are",count,"number of ways to arrange",size,"non-attacking queens on a chessboard. They are:")
print()
for n in L:
    print(n)

The output reveals that there are 40 ways (out of a total of 5040) in which 7 non-attacking queens can be placed on a 7 x 7 chessboard. Here is the output:

 There are 40 number of ways to arrange 7 non-attacking queens on a chessboard. They are:

[0, 2, 4, 6, 1, 3, 5]

[0, 3, 6, 2, 5, 1, 4]

[0, 4, 1, 5, 2, 6, 3]

[0, 5, 3, 1, 6, 4, 2]

[1, 3, 0, 6, 4, 2, 5]

[1, 3, 5, 0, 2, 4, 6]

[1, 4, 0, 3, 6, 2, 5]

[1, 4, 2, 0, 6, 3, 5]

[1, 4, 6, 3, 0, 2, 5]

[1, 5, 2, 6, 3, 0, 4]

[1, 6, 4, 2, 0, 5, 3]

[2, 0, 5, 1, 4, 6, 3]

[2, 0, 5, 3, 1, 6, 4]

[2, 4, 6, 1, 3, 5, 0]

[2, 5, 1, 4, 0, 3, 6]

[2, 6, 1, 3, 5, 0, 4]

[2, 6, 3, 0, 4, 1, 5]

[3, 0, 2, 5, 1, 6, 4]

[3, 0, 4, 1, 5, 2, 6]

[3, 1, 6, 4, 2, 0, 5]

[3, 5, 0, 2, 4, 6, 1]

[3, 6, 2, 5, 1, 4, 0]

[3, 6, 4, 1, 5, 0, 2]

[4, 0, 3, 6, 2, 5, 1]

[4, 0, 5, 3, 1, 6, 2]

[4, 1, 5, 2, 6, 3, 0]

[4, 2, 0, 5, 3, 1, 6]

[4, 6, 1, 3, 5, 0, 2]

[4, 6, 1, 5, 2, 0, 3]

[5, 0, 2, 4, 6, 1, 3]

[5, 1, 4, 0, 3, 6, 2]

[5, 2, 0, 3, 6, 4, 1]

[5, 2, 4, 6, 0, 3, 1]

[5, 2, 6, 3, 0, 4, 1]

[5, 3, 1, 6, 4, 2, 0]

[5, 3, 6, 0, 2, 4, 1]

[6, 1, 3, 5, 0, 2, 4]

[6, 2, 5, 1, 4, 0, 3]

[6, 3, 0, 4, 1, 5, 2]

[6, 4, 2, 0, 5, 3, 1]

These numbers (92 for \(n\)=8, 40 for \(n\)=7 etc.) constitute OEIS A000170:

A000170

Number of ways of placing \(n\) nonattacking queens on an \(n \times n\) board.

The initial members of the sequence are:

• \(n=0\) --> \(1\)
• \(n=1\) --> \(1\)
• \(n=2\) --> \(0\)
• \(n=3\) --> \(0\)
• \(n=4\) --> \(2\)
• \(n=5\) --> \(10\)
• \(n=6\) --> \(4\)
• \(n=7\) --> \(40\)
• \(n=8\) --> \(92\)
• \(n=9\) --> \(352\)
• \(n=10\) --> \(724\)
• \(n=11\) --> \(2680\)
• \(n=12\) --> \(14200\)
• \(n=13\) --> \(73712 \)

One might struggle with the concept of a 0 x 0 sized chessboard but I guess it's a bit like 0!=1 and 1!=1. The algorithm, when run on SageMathCell, timed out for the cases of \(n=10\) and above.

Primes from Primes

I've begun reading "The Man Who Loved Only Numbers" by Paul Hoffman, a biography of Paul Erdös. Figure 1 shows the front cover of the book. It motivated me to be a little more energetic in my daily number analysis at least for today because today was a prime day.

Figure 1

THE STORY OF PAUL ERDÖS AND THE SEARCH FOR MATHEMATICAL TRUTH

***

By that I mean I turned a prime number of days old, specifically 26371. Initially, I'd found that this number was a member of OEIS A255543:

A255543

Unlucky array: Row \(n\) consists of unlucky numbers removed at the stage \(n\) of Lucky sieve.

Figure 2, taken from the OEIS entry comments, shows what is meant by this:

Figure 2

Looking at the first row, it can seen that 2 and all multiples of 2 are removed. In the second row, every third remaining number is removed and so on for successive rows. 26371 lies in the 29th row that lists all the numbers removed when every 29th number is struck off. This was interesting but didn't relate to any specific properties of 26371 as a prime number. A little more research, motivated by Erdös's indefatigable research, led me to OEIS A249350:

A249350

Prime numbers Q such that the concatenation Q, 6, Q is prime.

As a member of this sequence, 26371 has the property that 26371626371 is a prime number. Up to 26371, the list of such primes is:

[13, 23, 29, 41, 53, 59, 71, 73, 89, 107, 149, 167, 173, 197, 239, 241, 257, 293, 349, 379, 383, 397, 439, 457, 461, 479, 503, 521, 547, 569, 607, 617, 631, 643, 677, 691, 727, 733, 757, 821, 887, 919, 941, 947, 953, 967, 1051, 1061, 1069, 1097, 1103, 1187, 1213, 1217, 1237, 1279, 1297, 1373, 1399, 1409, 1423, 1433, 1451, 1453, 1471, 1483, 1499, 1567, 1609, 1619, 1621, 1667, 1709, 1721, 1723, 1783, 1787, 1789, 1861, 1867, 1889, 1913, 1993, 1997, 2011, 2017, 2029, 2063, 2099, 2113, 2251, 2269, 2273, 2357, 2393, 2441, 2473, 2503, 2557, 2609, 2647, 2657, 2659, 2687, 2699, 2711, 2713, 2777, 2843, 2897, 2927, 2953, 3037, 3061, 3079, 3137, 3217, 3271, 3323, 3343, 3499, 3511, 3527, 3547, 3557, 3593, 3631, 3659, 3673, 3733, 3779, 3851, 3911, 4051, 4093, 4129, 4241, 4243, 4253, 4327, 4339, 4373, 4391, 4457, 4493, 4519, 4561, 4583, 4597, 4603, 4639, 4643, 4663, 4723, 4787, 4789, 4801, 4813, 4877, 4933, 4951, 4967, 5011, 5023, 5051, 5179, 5209, 5333, 5413, 5527, 5557, 5647, 5807, 5851, 5857, 5867, 5903, 6067, 6113, 6173, 6199, 6311, 6353, 6379, 6553, 6571, 6659, 6781, 6827, 6841, 6871, 6949, 6997, 7013, 7079, 7151, 7177, 7193, 7237, 7349, 7393, 7459, 7481, 7523, 7529, 7541, 7559, 7573, 7589, 7607, 7621, 7673, 7687, 7793, 7817, 7823, 7841, 7867, 7873, 7907, 8087, 8093, 8101, 8209, 8317, 8369, 8387, 8419, 8429, 8447, 8461, 8467, 8573, 8623, 8647, 8677, 8681, 8699, 8741, 8779, 8803, 8821, 8861, 8971, 8999, 9013, 9059, 9133, 9137, 9181, 9199, 9239, 9283, 9337, 9343, 9419, 9431, 9461, 9473, 9511, 9533, 9539, 9629, 9767, 9883, 10103, 10133, 10223, 10357, 10487, 10559, 10691, 10729, 10847, 10853, 10909, 10957, 10979, 11083, 11093, 11117, 11159, 11177, 11243, 11273, 11321, 11329, 11369, 11393, 11471, 11483, 11489, 11491, 11813, 11887, 12007, 12049, 12119, 12211, 12239, 12253, 12281, 12289, 12379, 12413, 12479, 12517, 12527, 12553, 12647, 12703, 12721, 12889, 12919, 13003, 13037, 13043, 13147, 13163, 13171, 13381, 13499, 13679, 13757, 13877, 14009, 14051, 14057, 14071, 14081, 14207, 14423, 14449, 14627, 14723, 14767, 14813, 14869, 14879, 14939, 15031, 15061, 15101, 15131, 15173, 15193, 15299, 15373, 15377, 15383, 15541, 15559, 15629, 15643, 15649, 15787, 15877, 15919, 15923, 16189, 16333, 16339, 16361, 16427, 16487, 16529, 16607, 16649, 16763, 16871, 16903, 16931, 17011, 17021, 17029, 17033, 17077, 17137, 17419, 17483, 17729, 17747, 17749, 17851, 17903, 17921, 17957, 17981, 18041, 18049, 18169, 18257, 18397, 18413, 18517, 18541, 18583, 18671, 18691, 18701, 18719, 18749, 18757, 18803, 18973, 19069, 19211, 19213, 19289, 19379, 19463, 19471, 19489, 19603, 19819, 19843, 19861, 19919, 20071, 20101, 20147, 20261, 20297, 20399, 20443, 20681, 20707, 20731, 20849, 20897, 20921, 20939, 21001, 21011, 21059, 21089, 21121, 21163, 21169, 21221, 21227, 21313, 21341, 21401, 21407, 21467, 21523, 21569, 22109, 22129, 22171, 22247, 22349, 22639, 22643, 22741, 22769, 22787, 22811, 22961, 23027, 23041, 23143, 23201, 23203, 23339, 23357, 23369, 23459, 23537, 23627, 23629, 23747, 23767, 23819, 23857, 23879, 23887, 24007, 24019, 24029, 24061, 24097, 24151, 24391, 24407, 24421, 24683, 24767, 24851, 24953, 25033, 25147, 25253, 25321, 25439, 25643, 26119, 26189, 26237, 26357, 26371]

26371 is the 2897th prime and the primes listed above total 502. This means that of all the primes up 26371, 502 or about 16.8% generate a new prime according the Q + 6 + Q concatenation. I wondered what numbers arise when the digits 1, 2, 3, 4, 5, 7, 8 and 9 are used instead. Inserting 0 between the two primes cannot produce a prime because the resulting concatenated number is always divisible by Q. Here are the figures for the digits from 1 to 9:

1     278

2     238

3     528

4     242

5     258

6     502

7     296

8     247

9     512

total is 3101

It can be seen that the record is held by the digit 3, although 6 and 9 are close behind. Well back however, are the digits 1, 2, 4, 5, 7 and 8. I thought I'd extend this to the first one million primes and Figure 3 shows the results obtained:

Figure 3

The proportions remain about the same with the exception of the digit 7. Figure 4 shows a table summarising the results:

Figure 4

Why do the digits 3, 6 and 9 produce about twice as many primes as the digits 1, 2, 4, 5 and 8? Why does the digit 7 produce significantly fewer primes that 1, 2, 4, 5 and 8? These are questions that I don't know the answer to but I'm keen to investigate.

One doesn't have to stop at the digit 9. What happens for the digits 10 to 19? Figure 5 tells the tale.

Figure 5

Figure 6 shows the same results in tabular form. It's clear that the multiples of 3 (12, 15 and 18) always win the day and with consistent frequency. The digits 10, 16 and 17 produce about half as many primes as their multiple of 3 counterparts, while 11, 13, 14 and 19 produce less than a third of even this number.

Figure 6

One might surmise that the frequency for multiples of 3 remains relatively constant as we investigate higher digits. After all, the numbers for 3, 6, 9, 12, 15 and 18 have been quite consistent. However, 21 = 3 x 7 breaks the pattern. See Figure 7.

Figure 7

The figure for 21 is not as low as for 22, 26 and 28 but it significantly lower than even the figures for 20, 23, 25 and 29. Figure 8 presents the results in tabular form.

Figure 8

Multiples of 7, 11 and 13 seem to produce far fewer primes when concatenated using Q + digit + Q. Figure 9 provides an overview of the digits from 1 to 99:

Figure 9

Clearly, there is more to be discovered here but I'll finish up at this point. What this post teaches us more than anything else is to not let a good prime go to waste and to be a little more energetic in my investigations.

The Chi-Square Statistic: \( \chi^{^2}_{_{_c}} \)

While perusing YouTube, the idea of a watching a video about the Chi-Square test popped into my head today and I decided to watch the video with the most views: 1,867,764 views uploaded on November 14th 2011, almost ten years ago.

I thought about how the test might be carried out in SageMath. My initial investigation didn't find anything conclusive so I turned to the trusty spreadsheet, specifically Google Sheets. I've tended to neglect spreadsheets since making use of SageMath and so this was an opportunity to revisit old territory.

What the chi-square statistic looks like is shown in Figure 1:

Figure 1

The \(c\) represents the numbers of degrees of freedom. O represents the observed frequencies and E represents the expected frequencies. For the 36 tosses of a fair die, the expected frequencies are all 6. Figure 2 shows what I came up with in Google Sheets.

Figure 2: link

The chi-square function takes the observed and expected frequencies and returns the probability that the results are due to chance alone. In the example shown in Figure 2, the probability is 0.0853 or a little over 8%. This falls short of the less than 5% that is usually regarded as the minimum requirement. 

In the worksheet, I've added superfluous information for the purpose of showing how things wre done in "the old days". I've calculated the differences between O and E, squared these and then divided by E as per the formula. The total is 9.67 and, looking at the black table in Figure 2, the cut-off point is 11.070 that appears in the 0.05 column with 5 degrees of freedom. 

Figure 3 shows the expected versus the observed results:

Figure 3

It's easy enough to get SageMath cell to carry out the necessary steps to arrive at the 9.67 result. Figure 4 shows a screenshot of the algorithm along with the permalink.

Figure 4: permalink

What I was looking for in SageMath was a function that would take the two lists as input and output the probability in the same way as the spreadsheet did. Perhaps it's possible. I'll keep investigating.

UPDATE on June 21st 2021

I just watched a video on YouTube demonstrating the application of the Chi-Square test using Excel. A manual method is used as well as making use of the built in Chi-Square function. The video does a good job of explaining the statistic using a 3 x 3 table as an example.

The Egg Drop Numbers

It's always a delight to suddenly come across a new category of numbers that I haven't heard of before. Today I turned 26332 days old and discovered that this number is a member of OEIS A116082: 

A116082

a(n) = C(n,7) + C(n,6) + C(n,5) + C(n,4) + C(n,3) + C(n,2) + C(n,1).

The sequence members, up to 26332, are as follows:

0, 1, 3, 7, 15, 31, 63, 127, 254, 501, 967, 1815, 3301, 5811, 9907, 16383, 26332

What caught my attention however, was a reference in the OEIS comments to The Egg Drop Numbers. This led to an interesting investigation, beginning with the so-called Two Egg Problem that is clearly stated on this site:

Egg Dropping Puzzle (2-egg, 100-floor version)

“Figure out the highest floor of a 100-floor building an egg can be dropped without breaking,  given two eggs”. The Egg Dropping Puzzle is a mathematical puzzle that has been around the internet for some time now, which is known to be adopted in interviews of major companies like Google, Microsoft, Accenture and even Hewlett Packard. You are to determine the minimum number of attempts required in the worst case scenario to find the critical floor.

 Assumptions in the Egg Dropping Puzzle:

• The two eggs are identical.
• If an egg does not break by dropping from a certain floor, it will not break dropping from any floor below that.
• If an egg breaks by dropping on a certain floor, it will break dropping from any floor above that.
• An egg may break by dropping on the 1st floor.
• An egg may not break by dropping even on the 100th floor.

I won't repeat the explanation of how to solve this problem here, because that's provided on the site, but I will display the formula that is established viz.:

With \(x\) eggs and \(m\) trials, the maximum number of floors of a building we can test is given by: $$\binom {m}{1} +\binom {m}{2} + \dots + \binom {m}{x}$$

The site provides a spreadsheet that lists a wide range of results for different values of \(x\) and \(m\). Figure 1 shows an excerpt from the spreadsheet with some annotations added.

Figure 1

The members of OEIS A116082 appear as the entries in far right column under 7 eggs. Thus it is seen that:$$26332=\binom {16}{1} +\binom {16}{2} + \binom {16}{3}+\binom {16}{4} + \binom {16}{5} + \binom {16}{6} + \binom {16}{7}$$Thus, armed with 7 eggs, we can, with at most 16 trials, find the critical floor in a building with as many as 26332 floors. This is rather remarkable I think. 

Without the egg dropping association, OEIS A116082 would be rather bland but now I've become aware of a whole new category of numbers, The Egg Drop Numbers. On June 6th, 2025 (the anniversary of D-Day by the way), I will enjoy the next egg drop number, 27823, which is the maximum number of floors for which someone, armed with 9 eggs, will be able to determine the critical floor with at most 15 trials.

One last point to make is that, in the unlikely event that the number of eggs \(x\) exceeds the number of trials \(m\), then the formula becomes:$$\binom {m}{1} +\binom {m}{2} + \dots + \binom {m}{\min(x, m)}$$