Subarray Sum Equals K - If the same prefix sum is encountered why does it follow 1,3,7,15,31 pattern?

Question

This is an interesting property I have noticed in the problem:

Subarray Sum Equals K

The basic algorithm is as follows:

1. You start with calculating the prefix (running sum).
2. You check if the prefixsum - requiredSum has occurred
3. If it has you add the number of occurrences to the answer and increment the occurrence by 1.

Here is the code if anyone wants a clearer picture:

def subarraySum(self, nums: List[int], k: int) -> int:

        ans=0
        prefsum=0
        d={0:1}

        for num in nums:
            prefsum = prefsum + num

            if prefsum-k in d:
                ans = ans + d[prefsum-k]

            if prefsum not in d:
                d[prefsum] = 1
            else:
                d[prefsum] = d[prefsum]+1

        return ans

What's interesting is how occurrences add up when the prefixSum repeats

Lets imagine prefix sum array in a more generalized way:

$$a_1,a_2,...k...k...k...k...k...a_{n-1},a_{n}$$

$k$ is the same prefix sum occurring multiple times. So all elements between the occurrences sum up to 0.

First time $k$ occurs count = 0

Second time $k$ occurs count = 1

Third time $k$ occurs count = 3

Fourth time $k$ occurs count = 7

Fifth time $k$ occurs count = 15

...so on

I searched OEIS and this pattern is $2^n-1$ or the Mersenne numbers.

Is there any reason why this happens ?

Does it have a special significance in combinatorics ?

What does it really mean ? Given similar points how many ways there are to group them maybe ?

Answer 1

First of all, it does not follow the $0, 1, 3, 7, 15, 31, \dots$ pattern. The sequence continues $0, 1, 3, 6, 10, 15, 21, \dots$ where the $n^{\text{th}}$ term is $\binom n2 = \frac{n(n-1)}{2}$. This is the number of ways to choose $2$ objects out of $n$ options.

The combinatorial reason for this is simply that if you have $n$ places where the partial sum $k$ occurs, we can choose any two of them and the sum of the interval between them will be $0$.

The algebraic reason is that after the $j^{\text{th}}$ occurrence of the number $k$, you add $j-1$ to the answer, and the sum $0 + 1 + 2 + \dots + (n-1)$ is equal to $\frac{n(n-1)}{2}$.