Write a number as the sum of consecutive primes
How to check if a n
sequence of consecutive primes can be split into the sum.
For example, 12
equal 5+7
, where 5 and 7 are consecutive primes, but 20
equal 3+17
, which 3 and 17 are not consecutive.
Please note that repetition is not allowed.
My idea is to find and list all the primes below n
and then use 2 loops to sum all the primes. The first 2 numbers, the second 2 numbers, the third 2 numbers, etc., and then the first 3 numbers, and also 3 numbers and so far. But it takes a lot of time and memory.
source to share
Understand that a sequential list of primes is defined by only two pieces of information, a seed and an ending prime. You just need to find these two numbers.
I assume you have all the simple ones at your disposal, sorted in an array called primes
. Store three variables in memory:, sum
initially 2 (the smallest prime), first_index
and last_index
, which are initially 0 (the index of the smallest prime in the array primes
).
Now you need to "tune" these two indices and "move" the array along the path in a loop:
If sum == n
finished. You have found your sequence of prime numbers.
If sum < n
, then enlarge the list by adding the next available prime. Increment last_index
by one, and then increment sum
by the new prime value, which is primes[last_index]
. Repeat the cycle. But if there is primes[last_index]
more than n
, then there is no solution and you must end.
If sum > n
, then reduce the list by removing the smallest number from the list. Decrease sum
by that value, which is equal primes[first_index]
, and then increase first_index
by one. Repeat the cycle.
source to share
To begin with, for a pair of consecutive primes to sum a number, one of the primes must be less than N / 2 and the other prime must be greater than N / 2. In order for them to be consecutive strokes, they must be next to N / 2, one smaller and the other larger.
If you start with a table of primes, you are basically doing a binary search for N / 2. Look at the primes more and less at once. Add these numbers together and see if they match your target number. If they don't, then it can't be the sum of two consecutive primes.
Unless you start with a table of primes, it works in much the same way - you still start with N / 2 and find the next larger prime (let's call it prime1). Then you subtract N-prime1 to get a prime2 candidate. Check if this is a prime, and if there is, search the line for prime2 ... N / 2 for other primes to see if there was a space in between. If there is a space between your number, it is the sum of non-consecutive primes. If there is no other number in this range, then it is the sum of consecutive primes.
The same basic idea applies for sequences of 3 or more primes, except (of course) your search starts with N / 3 (or whatever number of primes you want to add to get to the number).
So, for three consecutive primes summed with N, 2 of the three must be the first prime less than N / 3, and the first prime greater than N / 3. So we'll start by finding those, then calculate N- (prime1 + prime2). This makes it possible to use our third candidate. We know that these three numbers add up to N. We still need to prove that this third number is prime. If it is simple, we need to check that it is consistent with the other two.
To give a concrete example, for 10 we start with 3.333. The next smallest prime is 3, and the next is greater than 5. Those add to 8. 10-8 = 2. 2 is simply and consistently 3, so we found three consecutive primes that add to 10.
There are other clarifications you can make. The most obvious is that all primes (except 2) are odd numbers. So (assuming we can ignore 2) an even number can only be the sum of an even number of primes, and an odd number can only be the sum of an odd number of primes. So, given 123456789
, we know right away that it cannot be the sum of two (or 4, 6, 8, 10, ...) consecutive primes, so the only candidates to consider are 3, 5, 7, 9. ... prime numbers. Of course, the opposite also works: given, say,12345678
, the simple fact that it even allows us to immediately exclude the possibility that it could be the sum of 3, 5, 7 or 9 consecutive primes; we only need to consider sequences of 2, 4, 6, 8, ... primes. We only break this basic rule when we get enough primes to include as part of the sequence.
I didn't go through the math to figure out exactly how many would be for a given number, but I'm sure it should be pretty easy, and that's what we want to know anyway (because it's an upper limit on the number of consecutive primes to search for for this number). If we use M for the number of primes, the limit should be approximately M <= sqrt (N), but this is definitely only an approximation.
source to share
The fact that the primes must be sequential allows us to quite effectively solve this problem in terms of n. Let me assume that we have precomputed all primes less than or equal to n. Therefore, we can easily calculate the sum (i) as the sum of the first i primes.
If this function is precomputed, we can iterate over numbers less than or equal to n and see if there is such a length that, starting from that number, we can sum up to n. But note that for a fixed initial stroke, the sequence of sums is monotonic, so we can binary search by length.
Thus, let k be the number of primes less than or equal to n. Pre-calculating the sums has a cost of O (k) and the cycle has a cost of O (klogk), dominating the cost. Using the type number theorem , we know that k = O (n / logn) and then the whole algorithm has a cost of O (n / logn log (n / logn)) = O (n).
Let me put the C ++ code to make it clearer, hopefully there are no errors:
#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;
int main() {
//Get the limit for the numbers
int MAX_N;
cin >> MAX_N;
//Compute the primes less or equal than MAX_N
vector<bool> is_prime(MAX_N + 1, true);
for (int i = 2; i*i <= MAX_N; ++i) {
if (is_prime[i]) {
for (int j = i*i; j <= MAX_N; j += i) is_prime[j] = false;
}
}
vector<int> prime;
for (int i = 2; i <= MAX_N; ++i) if (is_prime[i]) prime.push_back(i);
//Compute the prefixed sums
vector<ll> sum(prime.size() + 1, 0);
for (int i = 0; i < prime.size(); ++i) sum[i + 1] = sum[i] + prime[i];
//Get the number of queries
int n_queries;
cin >> n_queries;
for (int z = 1; z <= n_queries; ++z) {
int n;
cin >> n;
//Solve the query
bool found = false;
for (int i = 0; i < prime.size() and prime[i] <= n and not found; ++i) {
//Do binary search over the lenght of the sum:
//For all x < ini, [i, x] sums <= n
int ini = i, fin = int(prime.size()) - 1;
while (ini <= fin) {
int mid = (ini + fin)/2;
int value = sum[mid + 1] - sum[i];
if (value <= n) ini = mid + 1;
else fin = mid - 1;
}
//Check the candidate of the binary search
int candidate = ini - 1;
if (candidate >= i and sum[candidate + 1] - sum[i] == n) {
found = true;
cout << n << " =";
for (int j = i; j <= candidate; ++j) {
cout << " ";
if (j > i) cout << "+ ";
cout << prime[j];
}
cout << endl;
}
}
if (not found) cout << "No solution" << endl;
}
}
Input example:
1000 5 12 20 28 17 29
Output example:
12 = 5 + 7
No solution
28 = 2 + 3 + 5 + 7 + 11
17 = 2 + 3 + 5 + 7
29 = 29
source to share
The dialectical algorithm is the classic O (m) -time, O (1) -space way of solving this type of problem (here I will use m to represent the number of primes less than n). It doesn't depend on any mysterious properties of prime numbers. (Interestingly, for the particular case of primes, the AlexAlvarezis also linear time!). Dialecticus gives a clear and correct description, but it seems to be able to explain why it is correct, so I'll try to do it here. I really think it's worth taking the time to understand this particular proof-of-correct algorithm: although I had to read a number of explanations before it finally "sank", it was a real "Aha!" the moment it was! :) (Besides, there are quite a few problems that can be effectively solved in the same way.)
The candidate solutions this algorithm tries to try can be represented as ranges of numbers (i, j), where i and j are just the indices of the first and last prime in the list of primes. The algorithm gains its efficiency by eliminating (i.e. not considering) multiple ranges of numbers in two different ways. To prove that it always gives the correct answer, we need to show that it never excludes a single range with the correct amount. To do this, it suffices to prove that it never excludes the first (leftmost) range with the correct amount, which we will do here.
The first rule that applies is that whenever we find a range (i, j) with the sum (i, j)> n, we exclude all ranges (i, k) that have k> j. It is easy to see why this is justified: the amount can only increase as we add more terms, and we determine that it is already too large.
The second, more complex rule, deciding the complexity of linear time, is that whenever we start the starting point of the range (i, j) from i to i + 1, instead of "starting again" from (i + 1, i + 1), we start with (i + 1, j), i.e. avoid considering (i + 1, k) for all i + 1 <= k <k. Why is this normal? (To put the question differently: Couldn't it be that this makes us skip some range with the correct amount?)
[EDIT: The original version of the next paragraph obscures the subtlety: we could have promoted the endpoint of the range to j in any previous step.]
To see that it never misses the valid range, we need to think about the range (i, j-1). For the algorithm to be able to advance the starting point of the current range so that it changed from (i, j) to (i + 1, j), it had to be the sum of (i, j)> n; and, as we will see, to switch to the program state in which the range (i, j) is considered, first of all, it must be that the sum (i, j-1) <n. This second statement is subtle, because in This state of the program has two different ways: either we just increase the end point, that is, the previous range was (i, j-1), and this range turned out to be too small (in this case, obviously, our desired sum of properties (i, j-1) <n); or we just increment the starting point after considering (i-1,j) and consider it too large (in this case, it is not obvious that the property is still satisfied).
However, we know that regardless of whether the endpoint was increased from j-1 to j in the previous step, it was definitely increased some time before the current step, so let's name the range that caused this endpoint to increase (k , j-1). It is clear that the sum is (k, j-1) n, since it is (by definition) the range that caused us to increase the end point from j-1 to j; and similarly k <= i, since we only process ranges in ascending order of their starting points. Since i> = k, sum (i, j-1) is the same as the sum (k, j-1) but with zero or more terms removed from the left end, and all those terms are positive, so it must that the sum ( i, j-1) <= sum (k, j-1) <p.
So, we have established that whenever we increase i to i + 1, we know that the sum is (i, j-1) n. To complete the analysis of this rule, what we (again) have to use is is that the terms discarding from either end of this sum cannot make it larger , Removing the first term leaves us with the sum (i + 1, j-1) <= sum (i, j-1) <n. Starting from this sum and successively removing the terms from the other end, we get the sum (i + 1, j-2), sum (i + 1, j-3), ..., sum (i + 1, i + 1), all of which we know should be less than n, i.e. none of the ranges corresponding to these amounts can be a valid solution. Therefore, we can safely avoid looking at them in the first place and what the algorithm does.
One final potential sticking point is that since we are advancing two loop indices, the time complexity should be O (m ^ 2). But note that every time through the body of the loop, we advance one of the indices (i or j) by one, and we never move any of them back, so if we are still working after iterations of the 2m loop, we must have i + j = 2nd. Since none of the indices can ever exceed m, the only way to keep this going is if i = j = m, which means that we have reached the end: that is, we guarantee completion after no more than 2m iterations.
source to share