×

# CLSUMG - Editorial

Author: Avijit Agarwal
Tester and Editorialist: Soumik Sarkar

MEDIUM

# PREREQUISITES:

Prime sieve, Fast fourier transform

# PROBLEM:

Let $f(x)=$ the number of pairs $(a, b)$ such that $0 \le a \le b < x$ and $a$ and $b$ are prime and $x = a + b$. Given a number $N$, find the number of pairs $(a, b)$ such that $0 \le a \le b < x$ and $f(N) = f(a) + f(b)$.

# EXPLANATION:

This problem was inspired by Goldbach's conjecture :D

Let us assume can find $f(x)$ in constant time for any given $x$. Then for a query $N$ naively trying all pairs will result in a complexity of $\mathcal{O}(N^2)$. Instead we can build up a frequency map/array of the sequence $f$ by upto index $N-1$. Let's call this frequency map $cnt$. Now we can count how many pairs add up to $f(N)$ by iterating over suitable $i$ and adding $cnt(i) \times cnt(f(N)-i)$ to the total. Note that we are looking for pairs where $a \le b$ so we must make sure not to double count any pair. The complexity is $\mathcal{O}(N)$ for one query.

This approach relies on the availability of all $f(x)$ in constant time. One way to achieve that would be to calculate all primes upto the required range beforehand using a sieve. Let there be $P$ such primes, then we can compute the array $f$ in $\mathcal{O}(P^2)$ time, but that would be too slow.

For an efficient solution, consider the polynomial $P(x) = x^2 + x^3 + x^5 + .... + x^p$ where in each term the exponent of $x$ is a prime and $p$ is the last prime we need to be concerned with.

$$P(x)^2 = ( x^2 + x^3 + x^5 + ....)^2 = x^4 + 2x^5 + x^6 + 2x^7 + 2x^8 + ...$$

Multipying $x^a$ and $x^b$ gives $x^{a+b}$. Thus in the polynomial above the coefficient of $x^k$ is the number of ways to represent $k$ as a sum of 2 primes. Note that here the pairs $(a, b)$ and $(b, a)$ for $a \ne b$ are counted separately, so the values must be adjusted to suit the given definition of $f(x)$.

Squaring a polynomial of degree $n$ naively takes $\mathcal{O}(n^2)$ time. However there exists the awesome method of Fast Fourier Transform which can be used to efficiently compute the product of two polynomials in $\mathcal{O}(n \log n)$.

The complexity is $\mathcal{O}(N \log N + TN)$.

# AUTHOR'S AND TESTER'S SOLUTION:

Author's solution can be found here
Tester's solution can be found here.

6★meooow ♦
6.6k617
accept rate: 49%

19.0k348495533

 0 Never knew we can use fft so easily in python! Can you explain a bit or give some link for understanding the functions involved? answered 17 Apr, 01:38 589●1●8 accept rate: 11% 1 You can refer to the documentation for numpy.fft and scipy.fftpack. There is one useful function in scipy.signal, which is fftconvolve that I have used. (18 Apr, 20:29) meooow ♦6★
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×14,487
×2,413
×325
×245
×52
×5