20151021, 15:48  #1 
(loop (#_fork))
Feb 2006
Cambridge, England
13×491 Posts 
Efficiently finding a linear progression in data
Say I have set of a few hundred thousand 64bit integers.
Is there a cleverer way of finding cases where three of them are in arithmetic progression than trying all possible A, all possible B, and seeing (using a hashtable or similar) whether 2BA is in the set? Obviously, for the stupid algorithm, I can look for longer arithmetic progressions: just keep looking until (k+1)*Bk*A is not in the set. Is there something cleverer I can do? ( Sorting the set of differences feels like a way to start, but I suspect that is just as expensive as the stupid algorithm because the set of differences is of length O(n^2) ) 
20151021, 16:05  #2 
Sep 2002
Database er0rr
5^{3}×29 Posts 
For my part in searching for titanic AP9s, a primorial form was chosen for density and the I ran 16 threads on a bit map  1 bit representing prime and 0 a composite. I think I had to use ~5.5 GB map. The downside was the overhead fetching a byte from RAM and decoding it. If I had had more RAM I would have used a byte per prime. Each thread stepped through the map looking for AP2, AP3, AP4 etc. We collected AP5s (or more) so that we could look outside the range for (probable) primes. Over about 2 years we found 5 titanic AP9s.
Last fiddled with by paulunderwood on 20151021 at 16:35 
20151021, 16:06  #3  
"Forget I exist"
Jul 2009
Dumbassville
20300_{8} Posts 
Quote:


20151021, 16:57  #4  
Nov 2003
7460_{10} Posts 
Quote:
Sort. Compute the successive differences. Compute the accumulated sums of the differences and do a bucket sort on them. For each nonempty cell X in the bucket see if 2X is also nonempty. e.g. 1 7 9 20 25 39 49 differences are: 6 2 11 5 14 10 The accumulated differences are: 8 19 24 38 48. Thus, place a 1 in each cell of the bucket in locations 8, 19, 24, 38, 48. Now, if index k has a 1, see if index 2k also has a 1. We see that location 19 is lit, so is 38. > Thus, 1, 20, 39 We see that location 24 is lit, so is 48, > Thus 1, 25, 49 

20151021, 17:10  #5 
Tribal Bullet
Oct 2004
DD1_{16} Posts 
Does the Hough transform work in three dimensions?

20151021, 17:16  #6  
"Robert Gerbicz"
Oct 2005
Hungary
1,459 Posts 
Quote:
Note that the 3sum is a decision problem, but I think that the new alg. also finds the triplet (if the answer is yes) just like the easy O(n^2) alg. For the reduction (it is pretty trivial): Say array "a" holds the integers. Create three arrays X,Y,Z: X[i]=10*a[i]+1 Y[i]=10*a[i]+2 Z[i]=20*a[i]3 For the concatenation of these three array run the 3sum algorithm. Seeing the last digit there is only one way to get zero: if you use one term from X and Y and Z array, for such hit: X[i]+Y[j]+Z[k]=0, then 10*a[i]+10*a[j]20*a[k]=0, so a[k]=(a[i]+a[j])/2 what you needed. And in the other direction: if (a[i]+a[j])/2=a[k], then X[i]+Y[j]+Z[k]=0. Last fiddled with by R. Gerbicz on 20151021 at 17:22 

20151021, 17:39  #7 
Bamboozled!
"πΊππ·π·π"
May 2003
Down not across
10100110011000_{2} Posts 
Yes, it works in arbitrarily large number of dimensions, AFAIK. It also works in many (all? don't know for sure) smooth manifolds  meaning you can look for curves such as conic sections by deforming the manifold until the curves are define by a set of linear equations.
A good imaging processing text might be a way into this field. Image processing and machine vision is where I learned about the Hough transform and its applicability. 
20151021, 18:30  #8  
Nov 2003
7460_{10} Posts 
Quote:
higher genus. I need to check into this; my algebraic geometry knowledge is pretty basic. 

20151022, 07:09  #9  
Romulan Interpreter
Jun 2011
Thailand
11·853 Posts 
Quote:
2. How does this solves the bidimensional problem? (i.e a progression can start from 7, or from 9, on your example, not always from 1) 3. Last fiddled with by LaurV on 20151022 at 07:16 

20151022, 09:40  #10 
Nov 2003
2^{2}×5×373 Posts 

20151023, 09:57  #11 
(loop (#_fork))
Feb 2006
Cambridge, England
18EF_{16} Posts 
{53307 258162 463017} is, among threeterm arithmetic progressions with n*2^10000+1 prime, the one with smallest largest term.
{10838076 13044603 15251130 17457657} is the same for fourterm arithmetic progressions The first fiveterm one has largest term >2^28 I can't find those particular numbers on the Web already, but I suppose people pick the place to search pretty much at random. For n*2^4000+1: 3 42537 56685 70833 4 2131248 3470313 4809378 6148443 5 86742492 99272412 111802332 124332252 136862172 Last fiddled with by fivemack on 20151023 at 12:51 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
How do you efficiently sieve for prime 3/4tuples?  PuzzlePeter  Software  156  20190603 20:19 
Exponent Progression  storm5510  Information & Answers  15  20170726 18:02 
Bertrand's Theorem for Arithmetic Progression  literka  Math  0  20130601 12:42 
Milestone Progression Update  NBtarheel_33  Data  2  20100902 03:14 
nth prime number in an arithmetic progression  Unregistered  Information & Answers  1  20100404 22:06 