Loading ...
Sorry, an error occurred while loading the content.

Re: [PrimeNumbers] Re: combinatorial question

Expand Messages
  • James Merickel
    Three problems for the price of one. Np. Let me first say that again I was making a mistake on the problem I thought you introduced. Though what I call a
    Message 1 of 7 , Aug 18, 2011
    • 0 Attachment
      Three problems for the price of one. Np.

      Let me first say that again I was making a mistake on the problem I thought you introduced. Though what I call a greedy solution was primarily introduced to get to the number 64 for the maximum, it still needs to be said that a) the smallest prime for the set can be as little as the size of the set and b) one cannot follow a simple greedy path to construction on account of going afoul of the second smallest prime (but close, and it still qualifies to my mind to say it is a greedy solution.

      As far as the original is concerned, I am glad I made a gross error amounting to 1+1+1=3, because it forced me to prove to myself that you are correct about divisibility by 5 (The part I just erased here ;) ). There is no combinatorial problem of depth on the specifics I was inquiring about. I am beginning to feel like I don't have time for nonsense more than ever (Supposedly, I am getting a perfect GRE math score and trying to get one in physics this fall. Right now, the first looks like a bit of a joke and the second looks like I am on crack).
      JGM

      On Thu Aug 18th, 2011 1:23 PM EDT Mark wrote:

      >
      >
      >
      >
      >
      >Please excuse the top posting.
      >
      >Jim, upon closer reading I see that our problems are only superficially similar, so I apologize for muddying the waters. For the seven numbers [a,b,c,d,e,f,g], I was using all seven numbers to generate each prime. Specifically, I was wanting (the absolute value of)
      >a +/- b +/- c +/- d +/- e +/- f +/- g to be prime in all 2^6 possible additive ways.
      >
      >Your problem involved addition only and using a varying (odd) number of the seven numbers to sum to a prime.
      >
      >But as you have already deduced, even considering only sets of three numbers from the seven, it is impossible to produce only primes. Upon cursory inspection at least five of the (7*6*5)/(3*2*1) = 35 outcomes must have a factor of three. When looking at choosing five of the seven numbers, at least three of the 21 outcomes must have a factor of three. (Good thing is, factors of five and up can be avoided.) So it looks like the theoretical maximum of primes that can be produced from the 64 possible numbers generated (from the combined group sizes of 1,3,5 and 7) is 64 - 5 - 3 = 56. Your 50 primes (48 distinct primes) is pretty close!
      >
      >Mark
      >
      >
      >
      >--- In primenumbers@yahoogroups.com, James Merickel <merk7777777@...> wrote:
      >>
      >> Further correction (Here I go again!): Something akin to a greedy solution should exist for each size set separately, but you would be starting with the first prime larger than 2^(n-2) with n the size of the set. Anyway, this wasn't really the topic. Point was just that the 64 given in the older nearly identical problem is clear after a little thought.
      >> Jim
      >>
      >> On Thu Aug 18th, 2011 12:53 AM EDT James Merickel wrote:
      >>
      >> >Correction: Such a greedy solution would exist, most surely, but starting with 3 would, of course, be out of the question (and it's likely that further small primes, at least 5 if not also 7 and 11, would cause problems as well).
      >> >Jim
      >> >
      >> >On Thu Aug 18th, 2011 12:11 AM EDT James Merickel wrote:
      >> >
      >> >>Okay, figured out what you meant, I think. The maximum for my distinct problem would consist of all primes, but the limitation was no even numbers. There are 127 distinct sums from a set of 7 elements, or 120 if they do not include single-member sums. In my problem, there are 7+7*6*5/6+7*6*5*4*3/120+1=64 possibilities looking only at odd numbers, but a minimum of 6 are divisible by 3 and not equal to it, and not all of the others may be prime, as I stated. Anyway, seeing your 64 there is a little confusing, but it's cute that the number of distinct primes in my collection so far is also 48. A greedy solution of your problem is to start with 3 and 5 and then to add the first number that adds to all of the primes obtained so far to get new primes for all, so your 64 is clear. Of course, that greedy solution is probably intractable beyond a set of 6 numbers.
      >> >>Jim
      >> >>
      >> >>On Wed Aug 17th, 2011 10:11 PM EDT Mark wrote:
      >> >>
      >> >>>
      >> >>>
      >> >>>
      >> >>>--- In primenumbers@yahoogroups.com, James Merickel <merk7777777@> wrote:
      >> >>>>
      >> >>>> Dear group,
      >> >>>> I am wondering if anybody can point me to literature on a question and its generalizations. I suspect this has been asked before, but I am working out the theoretical maximum of the number of primes that can arise as sums of an odd number (including 1) of members of a set consisting of 7 odd numbers (They would be primes under the safe assumption the theoretical is possible, where theoretical maximum deals with local questions). I have found this is a bit hard, though I will be able to work the specifics out after a little more paperwork. If it were simply a matter of settling the question modulo 3 and then getting others to fit, there could be as few as 6 composites, five being sums of three numbers and one a sum of five; but all roads lead to at least one additional composite by consideration modulo 5. Plausibly from what I can see so far, interference from modulo-7 considerations is also possible.
      >> >>>> Anyway, if anybody can help with literature on the question I would appreciate it. I think I have a decent empirical computer search in mind that will be slightly superior to trying to work this out entirely by hand and solving the specific problem--though not writing it up at all elegantly--should still be easy.
      >> >>>> FWIW, so far a search of all combinations of distinct odds through the largest of the set of 7 being 139 produces 50 primes (Some may repeat) with {13,17,23,31,53,83,127}.
      >> >>>> Jim
      >> >>>>
      >> >>>
      >> >>>A few years ago I tried something similar, but I did not restrict the seven numbers to be prime because I wanted to maximize the number of primes produced. Of course the theoretical maximum is 64. With all seven numbers below 840, I got as high as 63 primes generated (with repeats). I also had three cases of seven numbers generating 60 distinct primes.
      >> >>>
      >> >>>http://tech.groups.yahoo.com/group/primenumbers/message/19728
      >> >>>
      >> >>>Perhaps a month later I changed my technique and privately found that the seven numbers
      >> >>>
      >> >>>1371, 1170, 825, 756, 700, 615, 414
      >> >>>
      >> >>>generate all primes in their 64 additive combinations, but there are repeats. (It yields just 48 distinct primes.)
      >> >>>
      >> >>>This was an exhaustive search. If 64 distinct primes are to be generated, the largest prime generated will have to be greater than 5851.
      >> >>>
      >> >>>Mark
      >> >>>
      >> >>>
      >> >>>
      >> >>>
      >> >>
      >> >
      >>
      >
      >
    Your message has been successfully submitted and would be delivered to recipients shortly.