4

Is it possible to make a constraint for an integer to say it can not be a (Perfect) square number?

I have:

square(Square):- N#>0, Square #= N*N.

How do I define notsquare(Notsquare):- ...

My first thought was to have P*P =Q*Q*Notsquare and Remainder #>0, Remainder #= P rem Q.

But P and Q need to be able to be non integers so this didn't work.

false
  • 10,264
  • 13
  • 101
  • 209
user27815
  • 4,767
  • 14
  • 28

1 Answers1

5

What about

notSquare(S):- N #> 0, R #>0, R #< 2*N+1, S #= N*N+R.

?

Should work if S > 0; if you need to work with negative numbers too, I suppose you could modify it as

notSquare(S):- S #> 0, N #> 0, R #>0, R #< 2*N+1, S #= N*N+R.
notSquare(S):- S #< 0, SM #= -S, notSquare(SM).
max66
  • 65,235
  • 10
  • 71
  • 111
  • @user27815 - modified my answer to consider the negative number (`S < 0`) case – max66 Aug 18 '16 at 13:19
  • Wow, very nice! And it would be still greater if the last two clauses you show also worked for example for the most general query and others like it. Try for example: `?- notSquare(N).` The solution is simple: Use CLP(FD) constraints for more generality! – mat Aug 18 '16 at 13:44
  • Its interesting to compare this slight variant `square_t(Square,T):-N#>=0,Square #=N*N, T=true. square_t(S,T):-N #> 0, R #>0, R #< 2*N+1, S #= N*N+R, T=false.` to http://stackoverflow.com/questions/295579/fastest-way-to-determine-if-an-integers-square-root-is-an-integer - it is fast and simple! – user27815 Aug 18 '16 at 13:55
  • And more general! You can pull the `T=true` and `T=false` unifications into the clause heads. Note by the way that you can use bitwise operations too in CLP(FD) as provided by SWI. – mat Aug 18 '16 at 14:10
  • @mat - Do you mean that `S > 0` should be `S #> 0` and that `S < 0` should be `S #< 0`? Modified my answer in this way. Ps. thanks for your help: my first answer was a disaster; I even didn't know that gprolog support something equivalent to clpfd. – max66 Aug 18 '16 at 17:20
  • And prob change the `is` ? – user27815 Aug 18 '16 at 18:55
  • Yes, exactly, to **all** of your points! Forget `(is)/2`, use `(#=)/2` **instead** for integer arithmetic! Easy to teach, easy to learn, easy to use. And yes, you are right about your first answer, and I am happy that you figured this out yourself. In such cases, telling the truth to others would invariably seem extremely condescending ;-) GNU Prolog is a nice case where CLP(FD) constraints are available right out of the box, which is also the case for example in B-Prolog. I recommend to configure other systems in the same way, so that CLP(FD) constraints are readily available in all programs. – mat Aug 18 '16 at 19:00
  • Try `member(N,[5,10,17,26,37]), notSquare(N).` – false Aug 19 '16 at 11:32
  • @false - with `main :- member(N,[5,10,16,17,25,26,36,37]), notSquare(N), write(N), write(' '), fail, halt(0).` I obtain `5 10 17 26 37`; this is bad? – max66 Aug 19 '16 at 18:11
  • @max66: That's pointless. Use the toplevel and look at the particular answers. – false Aug 20 '16 at 00:07
  • @false what is the problem? – user27815 Aug 20 '16 at 11:14
  • @user27815: `between(0,40, N), call_residue_vars(notSquare(N), Vars), Vars = [_|_]` to see the problem: There are hidden unresolved constraints. – false Aug 20 '16 at 16:59
  • @false - from top level, `?- member(N,[5,10,17,26,37]), notSquare(N).`, I get `N = 5 ?`; I press semicolon and I get `N = 10 ?`, and `N = 17 ?`, and `N = 26 ?`, and `N = 37 ?`, and (finally) `no`. Take in count that I'm using gprolog (version 1.3.0) and (if I'm not wrong) I can't use `call_residue_vars/2` – max66 Aug 20 '16 at 19:44
  • @max66: So far, the question was about SWI/SICStus which features `call_residue_vars/2`. And yes, you cannot directly observe the problem with GNU-Prolog. – false Aug 20 '16 at 21:31
  • @false so do we need to add more constraints to the definition so that they propagate and resolve them selves? What do you suggest? – user27815 Aug 21 '16 at 08:53
  • @user27815: In this particular case it is sufficient to guarantee that a solution exists, as with: `call_residue_vars(G, XVars), \+ \+ labeling([], XVars)`. – false Aug 21 '16 at 11:33