1
$\begingroup$

I am a hobby computer scientist and im looking for simple fast ways to generate gigantic primes, specifically the ones im describing in this post. So leave out prime factorization for a moment. Observe the primes: 2, 5, 17, 41, 197, 281, 7699, 8893,.. and so forth (A013918).

These are primes that are sums of other primes. OEIS has a list.

Example: Number 11 is not in the list because 2+3+5=10, 2+3+5+7=17. No other consecutive addition of primes add up to that prime. We can do the same for the other primes and find that they are not in the list.

I find these primes a special type in the sense described above. So my first question is this: Does these primes have an own name? Or are they just called prime sums? There's a small section about these specific primes here.

More info

The number of terms we need to get to that prime number (A013916): 1, 2, 4, 6, 12, 14, 60.. (further down i call these numbers weights)

$n: p_1+p_2..+p_n\\ 1: 2\\ 2: 2+3 = 5.\\ 4: 2+3+5+7 = 17.\\ 6: 2+3+..+13 = 41.\\ 12: 2+3+..+37 = 197.$

etc. where n is number of terms (the weight).

same as

$\sum_{i=1}^n p_n$

Info we should know

  • how many terms to add

  • all the consecutive primes up to that point

We know the number of additions are exactly even for each new prime.

Problem

Finding mersenne primes are computational very challenging (ref. mathworld). What about these specific primes in the list above? There should be a method to compute these primes by adding previous primes.

We do not need to find all the primes between one prime and the next: example 5,17: to get 17 we added 2+3+5 and 7. not 11 and 13.

What we need is a (preferably simple) way to generate a list of weights for these? (number of terms to add). If we know this we can compute gigantic primes, because we do not need to check if the number is a prime or not, right?

The numbers we are dealing with are non-negative integers, and of course primes. There is a way to add gigantic numbers that requires approx. one hundred megabyte of memory (which is approx. the space needed for generating primes up to to the largest mersenne prime found today) and should be really fast using a homogeneous structure.

Is there a sieve method to compute these primes (2,5,17,41..)? Or is there a way to compute the weights (number of terms) to get to those primes?

$\endgroup$
  • 1
    $\begingroup$ Those primes are those which the sum of all the initial primes (i.e. the prime numbers in OEIS A007504. There are other primes which are the sums of distinct primes such as $13=2+11$ $\endgroup$ – Henry Nov 25 '17 at 16:42
0
$\begingroup$

Primes are mysterious. No one knows when the next prime is gonna come. So I think when you can not predict the next prime, then how can you predict when the sum of primes is gonna be prime. I think you can not make the way unless we know the method to predict nth prime.

$\endgroup$
  • $\begingroup$ I have not down-voted but I disagree with the answer. I wouldn't describe primes as mysterious any more than any other set of numbers. Certainly not knowing one thing may not necessarily mean you can't know another. I'm sure I've heard that there are formula available for primes only that they are impractical. I could be mistaken on the last part though. $\endgroup$ – Karl Nov 25 '17 at 16:58
  • $\begingroup$ @Karl Thank you for not voting down. Take sequences of even numbers, odd numbers. Take a sequence of primes. There are no such formula to generate nth prime. $\endgroup$ – hemu Nov 25 '17 at 17:20
  • 1
    $\begingroup$ @shrinit: There are formulae to generate the nth prime involving factorials for example, but they all become impractical for calculating large primes. $\endgroup$ – James Arathoon Nov 25 '17 at 17:23
  • $\begingroup$ It depends on whether you mean no such formula that is efficiently computable is known. $\endgroup$ – Karl Nov 25 '17 at 17:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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