# counting arithmetic progressions $a, a+r, a+2r$ in a list

I have a large list $L$ of numbers and I need to count instances of elements $a,b,c \in L$ such that $a +c = 2b$. A brute-force approach would be to check all possible triples $(a,b,c)$ and this will run in $L^3$ time.

Can I do any better?

• What kind of numbers? It is probably easy if you consider $\mathbb{Z}/2$, but possibly harder with complex numbers in $\mathbb{C}$. Commented Aug 5, 2014 at 16:37
• @babou integers or integers mod p. Commented Aug 5, 2014 at 16:46
• Let $max(L) = m$, I believe you can use FFT for a runtime of $\mathcal{O}(m \log{m} + n)$. See: stackoverflow.com/questions/1560523/… Commented Aug 5, 2014 at 20:07
• How many triples, which satisfy the condition $a + c = 2b$, are in the list $(0, 0)$? It seems to me, 8 Commented Aug 6, 2014 at 18:48
• @MichaelXu I notice it uses a bitmask rather than the list of number itself, which is fine. The FFT approach shoudl be related to Roth's theorem in mathematics, counting arithmetic progressions like these. Commented Aug 6, 2014 at 19:04

Given that the OP is rather unprecise as to the kind of numbers he is considering (though he later said integers or integers modulo $p$ in a comment), I will try to answer nevertheless, by trying to limit the number of assumptions I can make. And while I am at it anyway, I will generalize a bit.

This builds on the contributions of previous answer and comments, by Rick Decker, Hendrik Jan. and HEKTO.

Generalized statement of the problem

We consider four sets of values $\mathcal{U}, \mathcal{V}, \mathcal{W}, \mathcal{Z}$, two functions $f:\mathcal{U}\times \mathcal{V}\to \mathcal{Z}$ and $g:\mathcal{W}\to\mathcal{Z}$. Given 3 sets or lists of values $U,V,W$, respectively from $\mathcal{U}, \mathcal{V}, \mathcal{W}$, count the number of triples $(u,v,w)\in U\times V\times W$ such that $f(u,v)=g(w)$. Each computation of the functions $f$ and $g$ is supposed to be in constant time.

Let $n=max(|U|,|V|,|W|)$

General solution

This is essentially HEKTO's suggestion.

Build a hash table containing each value $w\in W$ indexed by $g(w)$. This has a cost $O(n)$ under the Simple Uniform Hashing Assumption(SUHA). Without the SUHA, one can use a balanced tree with complexity $O(n\log n)$.

Then for each $u\in U$ and for each $v\in V$ check whether $f(u,v)$ is in the hash table in constant time (or in the balanced tree in logarithmic time). If it is in an entry $g(w)$, then add $(u,v,w)$ to the list of solutions (or increase the solution count by one).

Complexity is $O(n^2)$ with hash table, under SUHA, or $O(n^2\log n)$ with a balanced tree.

Case of ordered sets

This is essentially Hendrik Jan's suggestion.

We assume that one of the two sets $\mathcal{U}$ or $\mathcal{V}$ (say $\mathcal{V}$, w.l.o.g.) and the set $\mathcal{Z}$ are totally ordered and that the function $f$ is monotonic with respect to the argument in the ordered set (here the second argument).

Then we can have a modified algorithm that does not need a hash table.

First sort the set $V$.

Build a list $L$ of pairs $(w,g(w))$ for all $w\in W$, sorted with respect to the second element.

Then for each $u\in U$, compare the ordered values of $f(u,v)$ with the ordered values $g(w)$ of the pairs in $L$, by moving up the two list $V$ and $L$ as you would do for set intersection, and add the answer $(u,v,w)$ whenever $f(u,v)=g(w)$ for some pair $(w,g(w))$.

Complexity is $O(n^2)$.

Application to "numbers" and arithmetic progression

We consider the initial problem of detecting arithmetic progressions in the elements of a list.

The three lists of the abstract case are the same list. The function $f$ is addition, and the function $g$ is doubling (i.e. product by 2).

The ordered set solution applies well to integers, rationals, or reals (with some care).

Complex numbers are not an ordered field. However they can be considered as an ordered groups with respect to addition, by prioritizing coordinates, so that $a+ib> a'+ib'$ iff $a>a' \vee (a=a' \wedge b>b')$. So the ordered set construction can be used.

The hash table algorithm seems necessary in the case of $\mathbb{Z}/p$ (i.e. integers modulo $P$) since non-trivial linearly ordered groups are necessarily infinite, which is not the case for $\mathbb{Z}/p$.

However the ordered set construction could be adapted to $\mathbb{Z}/p$ without loss in complexity, by allowing the list $L$ to be scanned twice, with some proper bookkeeping.

• I don't understand why your General Solution is O(n^2). The checking in hashtable is O(n), this should be O(n^3). The solution for case of ordered sets is very well explained. Commented Aug 6, 2014 at 6:08
• @randomA You are correct in the sense that my answer was not precise enough. This is true only under the Simple Uniform Hashing Assumption (SHUA). Though often used, this is not a totally inoccuous assumption, and I should have been more careful. This a bit glossed over in a text on hash tables I had just looked at. I will amend the answer accordingly, as soon as I finish some minor changes I was preparing. Thanks. - - - - I did not much like the H-table anyway. Commented Aug 6, 2014 at 8:10
• @randomA Actually, I think it is not the hash table check in constant-time that you should criticize, as much as my assertion that the hash table building is in linear time. If the checking is not in constant time, then building the table cannot be linear. Commented Aug 6, 2014 at 8:56
• you are right, that one as well Commented Aug 6, 2014 at 9:10
• @randomA Modified. Is it clear? Commented Aug 6, 2014 at 9:39

An often-useful technique is to sort the list first. Then, starting with the smallest element, $x_1$, consider pairing $x_1$ with $x_2$. For them to be the first two terms in an arithmetic sequence, you'll need to have an $x_i = (x_2-x_1)+x_2$. You can find such an element by, say, a binary search. If that fails, look at the pair $x_1, x_3$ and do the same thing. Once you've exhausted the pairs starting at $x_1$, look at the pairs $x_2, x_3$, then $x_2, x_4$ and continue, counting the successes.

The sorting will take $O(n\log n)$ steps. You'll have to check $O(n^2)$ pairs and for each do a binary search for the third element, for a total of $O(n\log n+n^2\log n)$ steps.

There are some improvements you can make to this algorithm, but this should get you started.

• Avoid the binary search. Sort the list. For each fixed $x_1=a$ let $x_3=c$ run over the list, and check whether $x_1=x_3$ equals $2x_2=2b$ for some element $x_2$ in the list by moving $x_2$ over the list together with $x_2$. $O(n^2)$. Commented Aug 5, 2014 at 14:30
• @HendrikJan - no need to move the $x_2$. We can create a hash table from the original list and verify that $(x_1 + x_3) / 2$ is in the table in $O(1)$ time Commented Aug 5, 2014 at 15:25
• I do not see that using a hash table will improve the complexity, but it might hurt the efficiency (more complex code). However, for numbers that cannot be sorted, you can apply @HendrikJan 's method to the list in any order, and have the list of doubles $2b$ in a hash table for checking. This can be abstracted to apply to lots of data with whatever weird operator you wish to use. Commented Aug 5, 2014 at 17:06

Sort the list increasingly, in time $O(n\log(n))$.

For every $j$, consider the two sequences formed by the left-differences $L[j]-L[j-1], L[j]-L[j-2],L[j]-L[j-3]...$ and the right-differences $L[j+1]-L[j],L[j+2]-L[j],L[j+3]-L[j]...$

By a simple list merging process, you will detect all equal values in the two lists, corresponding to arithmetic triples, using no more than $\min(j,n-j)$ comparisons.

Repeating for all $j$, you count all arithmetic triples in time $\Theta(n^2)$.

# Input (presorted)
L= [ 1, 2, 3, 6, 7, 9, 11 ]; n= len(L)

# Try all middle elements
for j in range(1, n - 1):
# Detect all arithmetic triples by merging the left and right lists
i= j - 1; k= j + 1
while 0 <= i and k < n:
if L[j] - L[i] < L[k] - L[j]:
# Advance in the left list
i-= 1
elif L[j] - L[i] > L[k] - L[j]:
# Advance in the right list
k+= 1
else:
# Report a triple and advance in both lists
print L[i], L[j], L[k]; i-= 1; k+= 1


Output:

1 2 3
3 6 9
1 6 11
3 7 11
7 9 11


This is worst-case optimal, as a perfect arithmetic sequence has $\Omega(n^2)$ arithmetic triples. Constant extra space.

A much harder challenge is to find an output-sensitive solution (when the number of arithmetic triples is $o(n^2)$).

• Before you learn it the hard way: after 10 edits, your contribution automatically becomes community wiki. And you no longer get rep for the upvotes. So avoid minor edits, or save them for later. Commented Aug 5, 2014 at 20:30
• Thanks for the tip. Usually I can't help it: proofreading and proofreading again.
– user16034
Commented Aug 5, 2014 at 20:31
• It definitely does not! We like well-prepared posts, but we also like improvements, of course. This has been discussed/explained on Computer Science Meta before (1, 2). However, many (insignificant) edits are troublesome because it keeps bumping the thread. Find some recommendations on preparing posts here. (cc @babou) Good to have another user on board who cares about quality! Commented Aug 6, 2014 at 10:19
• @babou Well, I agree that preventing small polishing is not ideal, but given how the platform works it can't be helped. There are many discussions on Meta Stack Exchange on this, including proposals to just not bump minor edits to the main page, but no one knows how to reliably detect such edits. So, as you say, we'll have to live with the limitations reality puts on our ideals. Commented Aug 6, 2014 at 11:05
• @babou That is to be expected. The proper response is to improve the question (which I'd assume would be necessary), comment, vote for reopening and maybe take it to Computer Science Meta. Anyway, if you want to continue discussing these things, please do so in Computer Science Chat; this is not the right place. Commented Aug 6, 2014 at 13:34