# Subsets of maximized length from a sorted list of integers

GROUPS:
 A relatively simple mathematical problem/not for me though/Given is a sorted list of integers: a = {a1,a2,a3,...an}I need to find a subset b={b1,b2,b3...bm}such thatb2-b1=xb3-b2=xb4-b3=x...Where x is an integer and x>0.Among all possible subsets b, I'm interested in the ones with the maximum length, ie m should be as big as possibleHow does one go about finding the x and the subset b ?Thanks in advancePS> Here's a sample list to work with:a={459, 468, 486, 495, 549, 567, 576, 594, 639, 648, 657, 675, 693, \729, 738, 783, 792, 819, 837, 846, 864, 873, 891, 918, 927, 936, 945, \954, 963, 972, 981};
4 years ago
4 Replies
 Ilian Gachevski 4 Votes A naive brute force approach would be to iterate through all possible values for b1 and x, keeping track of the maximal b found so far, for example  In[2]:= Module[{b = {}, i, k, m = 1, s, x},  For[i = 1, i < Length[a], i++,   For[x = 1, x < (Last[a] - a[[i]])/m, x++,    s = {}; k = 0;    While[MemberQ[a, a[[i]] + k x], AppendTo[s, a[[i]] + k x]; k++];    If[Length[s] >= m, b = s; m = Length[s]]    ]   ];  b]Out[2]= {918, 927, 936, 945, 954, 963, 972, 981} For a much more efficient algorithm with O(n^2) complexity, see this article.