# Finite or infinite set?

Due to my not-so-advanced math skills, this question may take a few attempts to state clearly:

Consider the unordered pair (2-tuple) partitions of n (e.g. with n=4, we have {{4,0},{3,1},{2,2}}). Take the low value from each pair and add them together and call this total T1. Take the high value from each pair and add them together and call this total T2. Let r = T2 / T1. For what values of n will r be an integer? What can we conclude about the minimum and maximum values of r, integer or not, for n={1,2,3,...,infinity)?

Clearly the sequence of ratios r is infinite, as is the subset of integer ratios r. The minimum integer is either 0 or 1, depending upon whether or not we consider the null set equal to zero. As for the maximum, it appears that for all r, r < 4 (?), and I assume this has to do with things like modular arithmetic, congruences, and the elements of T2 >= n/2 and the elements of T1 <= n/2.

(The real question) Now restrict the pairs to just those composed of prime numbers (again, with n=4, we would toss out {{4,0},{3,1}} and end up with just {2,2} and 2/2=1. By restricting the pairs in this way and requiring r be an integer, we get what appears to be a finite set of values for n: {4, 6, 16, 18, 20, 32, 52, 72, 102, 180, 3212}. I say "appears" because after 3212, no more terms are found for n < 10^7. I suspect these are all the terms, because as n grows large, T2 will always contain elements that can't be canceled by elements in T1, thus the set is finite. Is this true? If not, is there a way to determine where the next term might be?

One more example with n=18:

Partitions are: {{9,9},{10,8},{11,7},{12,6},{13,5},{14,4},{15,3},{16,2},{17,1},{18,0}}.
{11,7} are both prime, and {13,5} are both prime, so T2 = 11+13 = 24, and T1 = 7 + 5 = 12. r = T2 / T1 = 24 / 12 = 2.

One other observation:

If we generalize and let the elements of T2 >= n/x and the elements of T1 <= n/x, and restrict x to prime number, the integer value of r will tend to be 2x-1 (i.e. in the case above, x=2, 2 is prime, and the integer value of r tends to be 3 = 2(2)-1.

Thanks

Mathematica:

okQ[n_] := Module[{p, q}, p = Select[Prime[Range[PrimePi[n]]],
PrimeQ[2 n - #] &]; q = 2 n - p; Mod[Plus @@ q, Plus @@ p] == 0];
2*Select[Range[2, 5000], okQ]

-

When you talk about the partitions, all you're doing is representing $n$ as the sum of two other numbers. One will be $\geq \frac n 2$, and one will be $\leq \frac n 2$, as you've noticed. If both were bigger they'd add up to a number too large (similar situation for both being less). In fact you're just summing these. The upper sum is just the sum of the numbers $\geq n/2$ (since you'll get exactly one partition for each such number), and similarly for the lower sum. So your lower sum is always

$$\frac {n(n+2)}8, n \text{ even}$$ $$\frac{(n-1)(n+1)}8, n \text{ odd}$$

and your upper sum is always

$$\frac{3n(n+2)}8, n \text{ even}$$ $$\frac{3n^2+4n+1}8, n \text{ odd}$$

I can add derivations of these if you'd like; they're just applying the formula for $\sum_i i$ to $n$ and $n/2$. So when are these integers? For $n$ odd:

$$\frac{3n^2+4n+1}{n^2-1}=\frac{3(n^2-1)+4n+4}{n^2-1}=3+\frac{4}{n-1}$$

which is an integer for $n=3,5$ (remember, $n$ is odd in these formulas), giving you $5$ and $4$ as answers. For $n$ even:

$$\frac{3n(n+2)}{n(n+2)}=3$$

...well that's interesting. There might be a deeper reason for that, but as I don't know any number theory I'm afraid I can't enlighten you.

The prime question looks a lot harder, basically because primes are a lot harder. You're requiring both $x$ and $n-x$ to be prime in the pair ${x,n-x}$. Since we don't know how prime numbers are distributed (except asymptotically), you aren't going to have a closed formula here. Maybe someone with more expertise can shed light on any asymptotic results here, or whether or not there are actually finitely many solutions, but I'm kind of doubtful.

-
Asymptotically one could probably prove that $T_2/T_1 \to 3$ for a subsequence containing most even $n$ (this is similar to proofs that Goldbach's conjecture holds for all $n$ outside a sparse set). However, just having $T_1$ and $T_2$ being well-defined for all (even) $n$ is equivalent to Goldbach's conjecture. –  Erick Wong Sep 12 '12 at 2:25
If $T_2/T_1$ converged to a non-integer constant, then there might be hope of showing that there are very few examples. But as it stands, I suspect this is a very delicate question. The only hope would be to show that $T_2/T_1$ is typically very close to $3 + c/\log n$ for some $c \ne 0$, and thereby for many values of $n$ it is not an integer. This requires pretty tight control over error terms. –  Erick Wong Sep 12 '12 at 2:29
@Robert: Thanks! As Erik says, the prime question is a Goldbach one, so it's the evens that we are really concerned with. But the equation for odds will be useful too. I want to look at what happens when subsets of the partitions are taken. Using your equations as a guide, I will be able come up with similar ones for the various combinations of subsets. –  jnthn Sep 12 '12 at 17:15
@Erik: I wrote a program to change the ranges of T1 and T2 so that T1 is 1/3, 1/4, 1/5,...,1/100, of T2, and found 1/7 the most interesting. It is the only case where r never varies -- the ratio for all terms is 13:1, and I'll bet it's not a coincidence that (with x=7) 2x-1 = 13 and 13 is the larger of twin primes. Also, in all 100 variations, the sequences behave the same -- terms for smallish values of n can be found, but then the terms vanish. –  jnthn Sep 12 '12 at 17:40

This was becoming a little too long to be a comment.

Some very simple observations on "the real question". First $n$ will be even (because an odd number can be the sum of two primes in only one way $2+p$ and $p$ is not even unless it is 2).

Second, if you could find a prime pair $12x \pm 1$ then $$12x+4=3+(12x+1)=5+(12x-1)$$ while $$T_1=8 \text{ and } T_2=24x \text{ so } \frac {T_2}{T_1} = 3x$$

So, to show that the sequence comes to an end you would have to show (amongst other things) that every sufficiently large example of a number $12x+4$ with $12x \pm1$ being twin primes is the sum of at least one additional pair of primes. The same idea works with the numbers 5 and 7 and any pair of large odd primes (these are always of the form $6x\pm1$).

-
Thanks, Mark. When I first looked at this question, dropping the larger of twin primes, for the reason you state, was about the only search optimization that I could easily find. I see the rather abrupt jump from 180 to 3212 as a clue to what is going on here, and perhaps the distance between twin prime plays a roll. I will look for sequences related to the spacing of twin primes to see if anything jumps out at me. –  jnthn Sep 12 '12 at 17:25
@jnthn I think that you can take sets of low primes and do something similar (e.g. with three or four primes too, or with pairs of primes which differ by 4) - wherever the pattern of differences seems to persist. If you manage to prove your case, it will because the primes are dense enough to provide "extra pairs" in the cases you'd like to keep "pure" - and that seems quite a subtle thing. –  Mark Bennet Sep 12 '12 at 17:59
no comment -- oops –  jnthn Sep 12 '12 at 22:33

It seems to me that $T1$ is just the sum of all the integers less or equal than $\frac{n}{2}$ while $T2$ is the sum of the integers $\frac {n}{2} \le i \le n$, thus it should not be hard to find a closed formula for $r$, and also verifying when it is an integer.

As for the real question, I'll think about it. I suspect a closed formula is much harder to find because asking both numbers of the pair to be prime appears to be quite an unstable condition. Perhaps you should check if the numbers $n$ for which $r$ is an integer (you listed them above) have some number-theoretical significance.

-