Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

This question is related to numbers found in the OEIS sequence A191837.

In this sequence, $a(2) = 48 = 5 + 7 + 17 + 19$, where the summands of 48 are all prime numbers that are less than or equal to $48/2=24$. The prime factors of 48 are $2^4$ and $3$, and neither $2$ nor $3$ are summands in $a(2)$. Similarly, $a(3) = 108 = 5 + 7 + 11 + 19 + 29 + 37$ and the prime factors of $108$ ($2^2$ and $3^3$) are not summands in $a(3)$. This appears to hold for all fourteen (verified and unverified) integers in the sequence.

Is there some way to prove or disprove the conjecture that for every integer in sequence A191837, the prime factors of $a(n)$ will never be an element of the summands of $a(n)$?

share|improve this question
3  
I'm not sure how you are defining the sequence, but the headline definition in Oeis is "Least even number m which can be written as sum of 2n primes p[1] < ... < p[2n] < m/2 such that m-p[i] also is prime for i=1,...,2n." and the last condition would imply that none of the summands is a factor. But if you have got your sequence from a different place it might not be obvious that the definitions are the same. –  Mark Bennet Jul 9 '11 at 6:58
    
@mark Sorry, which condition? I am trying to extend the sequence and looking for ways to reduce the workload. If it is true that the factors will NEVER be an element of the summands then I can remove them from the list of candidate summands. Removing even just a few candidates will speed up the search. –  jnthn Jul 9 '11 at 7:20
3  
"m-p[i] also is prime for i=1,...,2n", so p[i] cannot be a factor of m unless m=2p[i], and that is excluded by p[i]<m/2. –  Mark Bennet Jul 9 '11 at 7:35
    
Is it obvious that $a(n)$ exists for every $n$? –  Andrea Mori Jul 9 '11 at 9:54
    
@mark Got it. If instead, the restriction on p[i] were relaxed to p[i]<=m/2, then there would be the additional case where 2 and m/2 would be candidates, whenever m==2*prime. But would relaxing the restricting be a bad thing? In the "COMMENTS" section, it says: "Moreover, we restrict these summands to be the lesser one of the decompositions p+q=m", and this would still hold, even if p[i]=m/2. Or am I wrong about that? –  jnthn Jul 9 '11 at 18:02
show 2 more comments

1 Answer

up vote 0 down vote accepted

Yes, of course, it's easy to prove the statement. In fact, the greatest common divisor of $a(n)$ and any of the summands $s$ in $a(n)$ has to be equal to one - they have to be relatively prime.

If they were not relatively prime, then we could look at the greatest common divisor $g>1$ of $s$ and $a(n)$. If $g<s$, then $s$ wouldn't be a prime because it would have a divisor $g$, and such composite $s$ isn't allowed as a summand of $a(n)$ in the sequence.

If $g=s$, then we couldn't prove that $s$ is non-prime. However, $a(n)-s$ would also be a multiple of $g$ but we would have $a(n)-s > a(n)/2 > g$, so $a(n)-s$ wouldn't be a prime which would again violate the condition that both the summands $s$ and the differences $a(n)-s$ have to be prime for the elements $a(n)$ of your sequence (check the page you linked to carefully how the numbers are defined).

Not only you can omit candidate summands of $a(n)$ that are prime factors of $a(n)$: you may omit all candidate summands that fail to be relatively prime with $a(n)$. Well, truth to be told, it's almost the same thing if you know that the summands have to be prime.

share|improve this answer
1  
Thanks Lubos! I just needed to be certain that removing the factors of m wouldn't cause erroneous results, and now I am. –  jnthn Jul 9 '11 at 18:25
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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