What is the largest number of distinct positive integers you can have such that most of their pairwise differences are prime?
For example, among (2, 4, 6, 11, 13, 15) there are 15 pairwise differences, of which 10 are prime.
My best answer is 13
As the numbers grow, the primes get sparse rather quickly. As the number of integers increases, the number of differences also increases. So even with the best possible set it shouldn't take long to end with fewer than half the differences primes.
I don't know if this assumption is warranted but let's have the set consist of
A=a subset of a consecutive even numbers and
B=a subset of b consecutive odd numbers.
This gives (a-1) + (b-1) differences of 2.
If we then make an 'infinite' table of possible differences of A and B and for each (A,B) define
M=maximum number of primes in any axb rectangle in the table. (since the primes get sparse, we can search for rectangles close to zero.)
We require ((a-1)+(b-1)+M)/((a+b)(a+b-1)/2) > 1/2
so
M > (a+b)(a+b-1)/4 - a - b + 2 = T the target value
I made a spreadsheet of target values from 1 to 11 for A and B.
Then I made a second spreadsheet, listing whether each odd from 1 to 33 was prime. For each value of A, I found the B with the maximum sum. This wasn't very efficient as I had to keep updating B. I'm no spreadsheet master.
From this I made, a table of M for each A,B pair. Then I compared M to T. There were no M>T if either A or B>7. The solutions with the largest A+B are (A,B)=(6,7) and (7,6), both with 13 distinct positive integers.
The sets are
{2,4,6,8,10,12,14,15,17,19,21,23,25}
and
{2,4,6,8,10,12,13,15,17,19,21,23,25}
40 of the 78 pairwise differences are primes. They actually have the same count of each prime difference (eleven 2's, two 3's, etc.)
|
|
Posted by Jer
on 2024-04-26 17:19:54 |
Probable answer