/* 

  Sequence of non-squares in Picat.

  http://rosettacode.org/wiki/Sequence_of_non-squares
  """
  Show that the following remarkable formula gives the sequence of non-square 
  natural numbers:

     n + floor(1/2 + sqrt(n))

  - Print out the values for n in the range 1 to 22
  - Show that no squares occur for n less than one million
  - This sequence is also known as A000037. 
  """

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

*/

import cp.

main => go.


go =>
  
  println([f(I) : I in 1..22]),
  nl,
  check(1_000_000), 
  nl.

% The formula
f(N) = N + floor(1/2 + sqrt(N)).

check(Limit) =>
  Squares = new_map([I*I=1:I in 1..sqrt(Limit)]),
  Check = [[I,T] : I in 1..Limit-1, T=f(I), Squares.has_key(T)],
  println(check=Check.len).

% plain list and membchk: 3.2s
check2 =>
  Squares=[I*I:I in 1..1000],
  Check = [[I,T] : I in 1..1000000-1, T=f(I), membchk(T,Squares)],
  println(check=Check.len).