/* Successive prime differences (Rosetta code) in Picat. http://rosettacode.org/wiki/Successive_prime_differences """ The series of increasing prime numbers begins: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, ... The task applies a filter to the series returning groups of successive primes, (s'primes), that differ from the next by a given value or values. Example 1: Specifying that the difference between s'primes be 2 leads to the groups: (3, 5), (5, 7), (11, 13), (17, 19), (29, 31), ... (Known as Twin primes or Prime pairs) Example 2: Specifying more than one difference between s'primes leads to groups of size one greater than the number of differences. Differences of 2, 4 leads to the groups: (5, 7, 11), (11, 13, 17), (17, 19, 23), (41, 43, 47), .... In the first group 7 is two more than 5 and 11 is four more than 7; as well as 5, 7, and 11 being successive primes. Differences are checked in the order of the values given, (differences of 4, 2 would give different groups entirely). Task In each case use a list of primes less than 1_000_000 For the following Differences show the first and last group, as well as the number of groups found: 1. Differences of 2. 2. Differences of 1. 3. Differences of 2, 2. 4. Differences of 2, 4. 5. Differences of 4, 2. 6. Differences of 6, 4, 2. Show output here. Note: Generation of a list of primes is a secondary aspect of the task. Use of a built in function, well known library, or importing/use of prime generators from other Rosetta Code tasks is encouraged. """ This program was created by Hakan Kjellerstrand, hakank@gmail.com See also my Picat page: http://www.hakank.org/picat/ */ % import v3_utils. import util. % import cp. main => go. /* There are 78498 primes until 1000000 [time(ms) 123] [1] number: 1 ( 9ms) first: [2,3] last: [2,3] [2] number: 8169 (10ms) first: [3,5] last: [999959,999961] [2,2] number: 1 (10ms) first: [3,5,7] last: [3,5,7] [2,4] number: 1393 (11ms) first: [5,7,11] last: [999431,999433,999437] [4,2] number: 1444 (11ms) first: [7,11,13] last: [997807,997811,997813] [2,4,6] number: 279 (12ms) first: [17,19,23,29] last: [997097,997099,997103,997109] [2,6,4] number: 297 (12ms) first: [29,31,37,41] last: [979541,979543,979549,979553] [4,2,6] number: 162 (12ms) first: [67,71,73,79] last: [980587,980591,980593,980599] [4,6,2] number: 300 (12ms) first: [19,23,29,31] last: [997099,997103,997109,997111] [6,2,4] number: 159 (12ms) first: [1601,1607,1609,1613] last: [997091,997097,997099,997103] [6,4,2] number: 306 (12ms) first: [31,37,41,43] last: [997141,997147,997151,997153] [6,4,2,4] number: 62 (14ms) first: [31,37,41,43,47] last: [959461,959467,959471,959473,959477] CPU time 0.0 seconds. Backtracks: 0 picat_run successive_prime_differences.pi go 0,28s user 0,04s system 99% cpu 0,316 total Larger instances: There are 664579 primes until 10000000 [time(ms) 2044] [1] number: 1 (74ms) first: [2,3] last: [2,3] [2] number: 58980 (74ms) first: [3,5] last: [9999971,9999973] [2,2] number: 1 (88ms) first: [3,5,7] last: [3,5,7] [2,4] number: 8543 (89ms) first: [5,7,11] last: [9999161,9999163,9999167] [4,2] number: 8677 (90ms) first: [7,11,13] last: [9997873,9997877,9997879] [2,4,6] number: 1484 (101ms) first: [17,19,23,29] last: [9993911,9993913,9993917,9993923] [2,6,4] number: 1530 (100ms) first: [29,31,37,41] last: [9998741,9998743,9998749,9998753] [4,2,6] number: 749 (101ms) first: [67,71,73,79] last: [9993337,9993341,9993343,9993349] [4,6,2] number: 1495 (101ms) first: [19,23,29,31] last: [9993079,9993083,9993089,9993091] [6,2,4] number: 725 (102ms) first: [1601,1607,1609,1613] last: [9969221,9969227,9969229,9969233] [6,4,2] number: 1602 (102ms) first: [31,37,41,43] last: [9980281,9980287,9980291,9980293] [6,4,2,4] number: 268 (114ms) first: [31,37,41,43,47] last: [9980281,9980287,9980291,9980293,9980297] CPU time 0.0 seconds. Backtracks: 0 picat_run successive_prime_differences.pi go2 3,21s user 0,21s system 99% cpu 3,415 total hakank 8:02 jaco (~/picat/me): time picat_run successive_prime_differences.pi go2 Compiling:: /home/hakank/picat/me/run_program.pi run_program.pi compiled in 1 milliseconds loading... program = successive_prime_differences.pi Compiling:: successive_prime_differences.pi successive_prime_differences.pi compiled in 3 milliseconds loading... goal = go2 There are 5761455 primes until 100000000 [time(ms) 22546] [1] number: 1 (650ms) first: [2,3] last: [2,3] [2] number: 440312 (673ms) first: [3,5] last: [99999587,99999589] [2,2] number: 1 (754ms) first: [3,5,7] last: [3,5,7] [2,4] number: 55600 (761ms) first: [5,7,11] last: [99992771,99992773,99992777] [4,2] number: 55556 (759ms) first: [7,11,13] last: [99999073,99999077,99999079] [2,4,6] number: 8700 (870ms) first: [17,19,23,29] last: [99986477,99986479,99986483,99986489] [2,6,4] number: 8728 (864ms) first: [29,31,37,41] last: [99999539,99999541,99999547,99999551] [4,2,6] number: 3987 (869ms) first: [67,71,73,79] last: [99997867,99997871,99997873,99997879] [4,6,2] number: 8625 (869ms) first: [19,23,29,31] last: [99990577,99990581,99990587,99990589] [6,2,4] number: 3983 (873ms) first: [1601,1607,1609,1613] last: [99954551,99954557,99954559,99954563] [6,4,2] number: 8893 (878ms) first: [31,37,41,43] last: [99985147,99985153,99985157,99985159] [6,4,2,4] number: 1299 (972ms) first: [31,37,41,43,47] last: [99954721,99954727,99954731,99954733,99954737] CPU time 0.0 seconds. Backtracks: 0 picat_run successive_prime_differences.pi go2 32,36s user 1,65s system 99% cpu 34,014 total */ % {{trans|Prolog}} go => Num is 1_000_000, statistics(runtime,[Start|_]), PrimeList = primes(Num), NumPrimes = PrimeList.len, statistics(runtime,[Stop|_]), RunTime = Stop - Start, printf("There are %w primes until %w [time(ms) %w]%n",NumPrimes, Num, RunTime), DiffList = [[1], [2], [2,2], [2,4], [4,2], [2,4,6], [2,6,4], [4,2,6], [4,6,2], [6,2,4], [6,4,2],[6,4,2,4]], run(DiffList, PrimeList). primesByDiffs([],_,[]). primesByDiffs([Prime|Primes], Diff, [Slide|Slides]):- Slide = new_list(Diff.len+1), append(Slide, _, [Prime|Primes]), select(Diff, Slide),!, primesByDiffs(Primes, Diff, Slides). primesByDiffs([_|Primes], Diff, Slides):- primesByDiffs(Primes, Diff, Slides). select([],_). select([Diff|Diffs],[S1, S2|Stail]):- S2 = S1 + Diff, select(Diffs, [S2|Stail]). run([],_). run([Diff|Dtail], PrimeList):- statistics(runtime,[Start|_]), primesByDiffs(PrimeList, Diff, SlideList), Num = SlideList.len, statistics(runtime,[Stop|_]), Runtime = Stop - Start, printf("%-10w number: %5w (%2wms) first: %-22w last: %-22w\n", Diff, Num, Runtime, SlideList.first, SlideList.last), !, run(Dtail, PrimeList). % {{trans|Go}} % This works but it's way too slow!. 17,675s just for [6,4,2] go2 => Limit = 1_000_000, Primes = primes(Limit), Res = successivePrimes(Primes, [6,4,2] ), % println(Res), println(len=Res.len), nl. successivePrimes(Primes, Diffs ) = Results.reverse => DL = Diffs.len, % println(dl=DL), Results = [], % outer: foreach(I in 1..Primes.len-DL) Group := new_list(DL), Group[1] = Primes[I], Continue = false, foreach(J in I..I+DL-1, break(Continue != false)) if Primes[J+1]-Primes[J] != Diffs[J-I+1] then Group := [], Continue := true else Group[J-I+1] := Primes[J+1] end end, if Group != [] then Results := [Group|Results], Group := [] end end. % comparison of prime calculations % Built-in primes/1: 120ms % This variant: 1011ms % swipl takes 7220ms! % go3 => Num = 1_000_000, statistics(runtime,[Start|_]), Primes = [N : N in 1..Num, prime2(N)], statistics(runtime,[End|_]), printf("%wms\n",End-Start), println(len=Primes.len), nl. prime2(2). prime2(N):- N /\ 1 > 0, % odd M is floor(sqrt(N)) - 1, % reverse 2*I+1 Max is M // 2, % integer division foreach(I in 1..Max) N mod (2*I+1) > 0 end.