2
$\begingroup$

A set of distinct positive integers is said to be a prime tree of integers if the graph obtained by letting the integers be its vertices, two of which are joined by an edge if (and only if) their sum is a prime, is a tree.

At most how many integers can such a set have if all of them are less than or equal to 100? Less than or equal to 1000?

$\endgroup$
3
  • 4
    $\begingroup$ Is the answer, or the method of finding it, particularly interesting? Otherwise this must surely be off-topic. $\endgroup$
    – Bass
    Jun 4 at 21:05
  • 3
    $\begingroup$ Turning a general undirected graph into a maximal tree (or a forest) by removing nodes is known to be NP-hard, so unless OP has some trick up his sleeve (he didn't respond to the comment asking if that's the case), this cannot be solved without brute force, and therefore is a computation problem rather than a puzzle. $\endgroup$
    – Bass
    Jun 6 at 7:23
  • 2
    $\begingroup$ A solution for N=100, found by integer programming: 2 4 10 12 16 18 20 22 26 32 34 36 40 42 43 44 46 48 50 52 56 58 59 60 62 66 68 70 72 74 75 76 78 80 82 84 90 92 94 96 (40 nodes) $\endgroup$ Jun 8 at 3:02
4
$\begingroup$

For n=100, is the answer?

26

How?

There are 25 odd prime numbers up to 102. Subtract 2 from each of these and connect the resulting numbers directly to a 2 in the middle.

For other n

For 1000, or any other values of n, we just need to find all odd prime numbers up to n+2, subtract 2 from them and connect each of the resultants to 2. Voila! Your tree is ready. The size of the set is simply the number of prime numbers up to n.

How are we sure it's a tree?

For each of the 25 elements connected to 100, we have to ensure that there are no connections between any of them, to ensure acyclicity. Since they are all odd numbers >=3, their sum will be even and hence composite. This is sufficient to ensure that there are no edges between them.

$\endgroup$
5
  • 3
    $\begingroup$ Welcome to PSE, this is a really nice answer! :) This might be a good lower-bound candidate for now, though we shall see whether there is a better answer or this is already optimal. (Namely, maybe it is possible to have multiple edges with the same sum of primes.) $\endgroup$
    – athin
    Jun 5 at 11:11
  • 2
    $\begingroup$ E.g. for $n = 6$, your method will give an answer of $4$ (as the odd primes up to $6 + 2 = 8$ are $3, 5, 7$). But the optimal answer should be $5$, achieved by either $\{1, 3, 4, 5, 6\}$ or $\{2, 3, 4, 5, 6\}$. $\endgroup$
    – WhatsUp
    Jun 5 at 15:23
  • 1
    $\begingroup$ Hmm, you're right. Can you think of a failing case for larger n? Or does the strategy fail only for small n? $\endgroup$ Jun 5 at 16:15
  • 2
    $\begingroup$ It seems to me that there's nothing special about 2 in this construction. Replacing it with any other integer would generate a set of numbers with the same property. In particular, 3 and 1 can be easily seen to generate the same size tree as 2. $\endgroup$
    – Steve
    Jun 7 at 12:23
  • 1
    $\begingroup$ I agree. 2 is an example, and this probably works with a host of other central numbers too. I see that the question has been closed as off-topic, but I'd still like to hear what the OP had in mind. @Bernardo Recamán Santos $\endgroup$ Jun 7 at 18:55

Not the answer you're looking for? Browse other questions tagged or ask your own question.