n queen topics
Home
Group actions
Search algorithm
Use symmetry, regular NQ problem
Evolution trees
Special properties
Necklaces
Conflicts
Conflict tables
Smallest solutions and greedy sequence
World records
Tables of counting results
Images for n=8
Torus images for n=13
Other pages to the n queens problem
Bibliografy

Other themes
Primes from wrong binomic formula
Numbers by primes distribution

German
A short sequence in the Encylopedia of Integer Sequences (EIS) caused me to do some further investigation. The sequence had the attributes "more" and "hard", and I thougth "more" is right but "hard" is not.
The sequence is A088627. It counts how many primes arise if you factorize a given (even) number into two factors, and then sum the two factors.
For those who like to read it in a more formal way: Let 2n = r*s, a(n) = number of primes of the form r+s.
To give an example: a(9) = 2. For figuring that out, we start with 2 * n which is 18. We have the the factorizations 18 = 1*18, 18 = 3 * 6 and 18 = 2*9; Summing the factors gives 1+18 = 19, 3+6 = 9, and 2+9 = 11. Of these three values, 9 is not prime, but 11 and 19 are. So, two primes arise.
Only 12 values were contained. Here are the first 1000 values:
 1 1 2 0 2 2 0 1 2 0 . 2 1 0 2 4 0 1 2 0 2 . 4 0 1 1 0 2 1 0 2 4 . 0 0 2 0 4 2 0 1 4 0 . 2 2 0 2 3 0 0 1 0 2 4 0 1 2 0 2 2 0 1 3 . 0 0 2 0 4 3 0 1 3 0 . 1 0 0 2 3 0 2 2 0 1 . 2 0 1 3 0 2 2 0 1 3 . 0 1 1 0 4 2 0 2 4 0 1 2 0 1 8 0 1 0 0 2 . 3 0 1 4 0 2 1 0 3 4 . 0 0 1 0 2 3 0 1 2 0 . 1 1 0 2 4 0 1 2 0 4 . 3 0 1 1 0 1 2 0 1 3 0 0 2 0 4 4 0 2 2 0 . 3 0 0 0 8 0 0 2 0 3 . 3 0 1 2 0 2 1 0 2 1 . 0 2 2 0 2 4 0 0 4 0 . 2 1 0 2 5 0 1 4 0 2 2 0 1 4 0 1 1 0 3 7 . 0 1 0 0 2 2 0 1 3 0 . 4 1 0 2 3 0 1 2 0 3 . 8 0 1 1 0 1 1 0 2 3 . 0 0 1 0 3 3 0 1 3 0 . . . . . . . . . . . . . . . . . . . . . 1 2 0 2 5 0 0 0 0 4 . 4 0 0 2 0 3 2 0 1 4 . 0 0 4 0 3 1 0 1 2 0 . 2 2 0 2 5 0 1 2 0 1 . 3 0 1 3 0 2 0 0 2 2 0 0 2 0 3 3 0 2 3 0 . 1 2 0 0 8 0 0 1 0 1 . 2 0 2 1 0 2 0 0 4 7 . 0 0 1 0 2 4 0 2 1 0 . 3 0 0 1 6 0 1 1 0 4 3 0 0 4 0 1 4 0 1 3 . 0 0 2 0 3 2 0 0 2 0 . 4 2 0 3 2 0 2 2 0 4 . 2 0 0 1 0 2 2 0 0 5 . 0 0 2 0 3 3 0 1 6 0 0 2 0 2 2 0 2 1 0 2 . 2 0 2 4 0 0 2 0 2 7 . 0 0 1 0 2 2 0 1 7 0 . 2 1 0 2 6 0 2 2 0 3 . 4 0 1 1 0 1 1 0 0 3 0 0 2 0 7 3 0 1 4 0 . 1 4 0 2 5 0 0 2 0 4 . 2 0 2 1 0 3 2 0 0 2 . 0 0 4 0 4 0 0 1 1 0 . 1 2 0 3 5 0 2 1 0 0 . . . . . . . . . . . . . . . . . . . . . 3 0 0 3 0 4 1 0 1 4 . 0 0 1 0 3 4 0 1 4 0 . 1 0 0 2 7 0 1 1 0 3 . 2 0 1 4 0 1 0 0 3 1 . 0 0 1 0 3 8 0 1 2 0 2 1 0 2 6 0 0 3 0 3 . 7 0 0 4 0 0 1 0 1 4 . 0 2 1 0 4 2 0 1 2 0 . 3 1 0 1 8 0 0 1 0 3 . 2 0 1 1 0 2 2 0 1 2 0 2 0 0 2 3 0 2 5 0 . 4 1 0 2 6 0 1 2 0 2 . 1 0 1 4 0 1 3 0 3 5 . 0 0 0 0 1 1 0 3 4 0 . 2 1 0 3 7 0 0 2 0 2 7 0 1 2 0 1 1 0 2 8 . 0 0 3 0 5 3 0 0 2 0 . 2 1 0 0 2 0 0 0 0 4 . 3 0 1 1 0 2 1 0 2 8 . 0 1 3 0 2 2 0 1 3 0 0 1 0 2 3 0 1 1 0 1 . 3 0 1 7 0 1 1 0 1 1 . 0 0 1 0 4 3 0 1 1 0 . 2 2 0 0 5 0 2 2 0 2 . 5 0 1 4 0 1 1 0 2 3 . . . . . . . . . . . . . . . . . . . . . 0 1 1 0 3 3 0 1 5 0 . 1 1 0 1 7 0 2 0 0 7 . 3 0 0 3 0 2 3 0 3 4 . 0 1 2 0 3 1 0 0 2 0 . 3 0 0 1 3 0 0 3 0 2 1 0 2 1 0 3 2 0 2 3 . 0 2 2 0 2 3 0 1 7 0 . 1 1 0 0 4 0 1 2 0 3 . 3 0 2 3 0 2 2 0 0 4 . 0 0 0 0 1 3 0 1 2 0 3 1 0 4 7 0 1 3 0 4 . 7 0 0 0 0 1 0 0 1 7 . 0 0 1 0 3 4 0 1 2 0 . 1 0 0 2 4 0 0 2 0 2 . 3 0 2 2 0 1 3 0 1 3 0 0 2 0 4 3 0 0 2 0 . 1 1 0 1 5 0 2 1 0 3 . 2 0 2 7 0 1 1 0 0 4 . 0 1 2 0 8 2 0 1 2 0 . 0 1 0 1 7 0 0 1 0 3 1 0 1 1 0 1 2 0 2 2 . 0 1 1 0 2 8 0 1 3 0 . 0 1 0 2 8 0 0 0 0 2 . 3 0 0 3 0 2 2 0 4 5 . 0 0 2 0 1 3 0 2 2 0 . . . . . . . . . . . . . . . . . . . . .
As you see, the first values are very small. I wondered if there are larger values, and when they occur. So, I defined another sequence which is now A091350 in the EIS. It is the sequence of first occurrences of n in the original sequence. However, I took the (even) number that is factorized as value. So, the sequence has only non-negative, even values. To say it in a formal way, the new sequence b(n) is defined as
```   b(n) = k    if there is an even k, a(k/2) = n,
and a(p) != n  for all p < k/2
= 0    if there is no such k.
```
I think the value 0 will not occur in the sequence; or, stated the other way, there will be a number k from which n primes arise, for every n.
On the other hand, I cannot even exclude that the sequence is constantly 0, from a certain n on.
Here are the first 30 values of the sequence of first occurrences, from 0 to 29: 8, 2, 6, 90, 30, 390, 690, 420, 210, 4290, 3990, 8778, 2310, 3570, 4830, 11550, 38850, 84630, 66990, 79170, 39270, 30030, 51870, 46410, 43890, 111930, 163020, 221340, 419430, 131670.
As you see, the sequence is not monotone.
My search also produced the values b(34) = 746130, b(35) = 903210, b(36) = 570570, b(40) = 510510, b(41) = 690690, and b(46) = 870870.
In my search, I just factorized all even numbers from 2 to 1,000,000. Therefore, b(n) > 1000000 for n in { 30, 31, 32, 33, 37, 38, 39, 42, 43, 44, 45} and for n > 46.
Perhaps, you have seen also that some of the values have the same sequence of digits for the "thousands" as for the hundreds, tens and unitys, for example b(36) = 570570 which has 570 written two times in sequence, as a decimal number. The same happens for b(40), b(41), b(46), and also for b(21) = 30030 if you add a leading zero. That is due to the fact that 1001 = 7 * 11 * 13 is a product of small primes, and products of many primes lead to many factorizations and to many possibilities for primes arising from these factorizations.
That leads to an upper bound for the original sequence a(n) = A088627.
(I inserted this Lemma as .gif because latex2html is not yet installed correctly on my machine)
Prepared by Matthias Engelhardt

last change: 2010-03-29