/* 

  Ludic numbers (Rosetta code) in Picat.

  http://rosettacode.org/wiki/Ludic_numbers
  """
  Ludic numbers are related to prime numbers as they are generated by a sieve quite 
  like the Sieve of Eratosthenes is used to generate prime numbers.

  The first ludic number is 1.
  To generate succeeding ludic numbers create an array of increasing integers starting from 2

    2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 ... 

   (Loop)

    Take the first member of the resultant array as the next Ludic number 2.
    Remove every 2'nd indexed item from the array (including the first). 

        2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 ... 

    (Unrolling a few loops...)
    Take the first member of the resultant array as the next Ludic number 3.
    Remove every 3'rd indexed item from the array (including the first). 

        3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 51 ... 

    Take the first member of the resultant array as the next Ludic number 5.
    Remove every 5'th indexed item from the array (including the first). 

        5 7 11 13 17 19 23 25 29 31 35 37 41 43 47 49 53 55 59 61 65 67 71 73 77 ... 

    Take the first member of the resultant array as the next Ludic number 7.
    Remove every 7'th indexed item from the array (including the first). 

        7 11 13 17 23 25 29 31 37 41 43 47 53 55 59 61 67 71 73 77 83 85 89 91 97 ... 

    ...
    Take the first member of the current array as the next Ludic number L.
    Remove every L'th indexed item from the array (including the first).
    ... 

  Task

    - Generate and show here the first 25 ludic numbers.
    - How many ludic numbers are there less than or equal to 1000?
    - Show the 2000..2005'th ludic numbers.
    - A triplet is any three numbers x, x + 2, x + 6 where all three numbers are also 
      ludic numbers. Show all triplets of ludic numbers < 250 (Stretch goal) 
  """

  This Picat model was created by Hakan Kjellerstrand, hakank@gmail.com
  See also my Picat page: http://www.hakank.org/picat/

*/


% import util.
% import cp.


main => go.


go =>
 time(check(ludic)),
 time(check(ludic2)),
 nl.


check(LudicFunc) =>

  % below 1000
  println(ludicFunc=LudicFunc),
  Ludic = apply(LudicFunc,1000),
  println(ludic_below_1000=Ludic),
  println(len=Ludic.length),
  % first 25
  println(first25=[Ludic[I] : I in 1..25]),

  % Triplets
  Ludic2 = apply(LudicFunc,2500),
  println(triplets=[[N,N+2,N+6] : N in 1..Ludic2.length, member(N,Ludic2), member(N+2,Ludic2), member(N+6,Ludic2)]),

  % 2000..2005
  Ludic3 = apply(LudicFunc,22000),
  println(len22000=Ludic3.length),
  println(ludic_2000_2005=[Ludic3[I] : I in 2000..2005]),
  nl.


%
% recursive (faster)
%
ludic(N) = Ludic =>
  ludic(2..N, [1], Ludic).
ludic([], Ludic0, Ludic) => 
  Ludic = Ludic0.reverse().
ludic(T, Ludic0, Ludic) =>
  T2 = ludic_keep(T),
  ludic(T2,[T[1]|Ludic0],Ludic).

% which elements to keep
ludic_keep([]) = [].
ludic_keep([H|List]) = Ludic =>
  ludic_keep(H,1,List,[],Ludic).

ludic_keep(_H,_C,[],Ludic0,Ludic) ?=>
  Ludic = Ludic0.reverse().
ludic_keep(H,C,[H1|T],Ludic0,Ludic) =>
  (
  C mod H > 0 ->
    ludic_keep(H,C+1,T,[H1|Ludic0],Ludic)
  ;
   ludic_keep(H,C+1,T,Ludic0,Ludic)
  ).


%
% imperative approach (slower)
%
ludic2(N) = Ludic =>
  A = 1..N,
  Ludic = [1],
  A := delete(A, 1),
  while(A.length > 0)
    T = A[1],
    Ludic := Ludic ++ [T],
    A := delete(A,T),
    A := [A[J] : J in 1..A.length, J mod T > 0]
  end.