End of Summer Prolog Riddle (Ascending Regular Numbers)

[burs...@gmail.com]

Task: Write a Prolog predicate regnum/1, that
enumerates regular numbers(*) of the for 2^i*5^j
in ascending order by backtracking.

?- regnum(X).
X = 1
X = 2
X = 4
X = 5
X = 8
X = 10
Etc..

Allowed tools? Dunno whether sort/2 helps,
backtracking should never end. CLP(FD)
would be allowed as well.

(*)
https://oeis.org/A003592

[Julio P. Di Egidio]

On 02/09/2017 02:19, burs...@gmail.com wrote:
>
> Task: Write a Prolog predicate regnum/1, that
> enumerates regular numbers(*) of the for 2^i*5^j
> in ascending order by backtracking.

> (*) https://oeis.org/A003592

>
> ?- regnum(X).
> X = 1
> X = 2
> X = 4
> X = 5
> X = 8
> X = 10
> Etc..
>
> Allowed tools? Dunno whether sort/2 helps,
> backtracking should never end. CLP(FD)
> would be allowed as well.

Backtracking on finite domains always ends! BTW, it's an interesting
little mathematical problem: I think there is a solution that does not
need factoring the numbers...

Julio

[burs...@gmail.com]

Yes the regular numbers of the form 2^i*5^j
are infinitely many. This doesn't mean that
CLP(FD) might not be useful.

Here is an example without CLP(FD) of enumerating
something infinite in Prolog:

Welcome to SWI-Prolog (threaded, 64 bits, version 7.5.8)
SWI-Prolog comes with ABSOLUTELY NO WARRANTY. This is free software.

?- [user].
nat(0).
nat(X) :- nat(Y), X is Y+1.
^D

?- nat(X).
X = 0 ;

X = 1 ;
X = 2 ;

X = 3 ;
Etc..

Here is an example with CLP(FD) of enumerating
something infinite in Prolog:

Welcome to SWI-Prolog (threaded, 64 bits, version 7.5.8)
SWI-Prolog comes with ABSOLUTELY NO WARRANTY. This is free software.

?- use_module(library(clpfd)).

?- [user].
nat(0).
nat(X) :- X #= Y+1, nat(Y).
^D

?- nat(X).
X = 0 ;

X = 1 ;
X = 2 ;

X = 3 ;
Etc...

Note the possibility of different goal ordering with
CLP(FD). Disclaimer: I do not endorse this style. But
I don't want to exclude CLP(FD) solutions.

[burs...@gmail.com]

Both solutions (of enumerating N) without or with
CLP(FD) use O(n) space, the without CLP(FD) solution
because it is not tail recursive, and the with CLP(FD)
solution, because constraints have to be pushed on the

constraint stack. So execution wise there is anyway
practically not much gain I guess by using CLP(FD).
On the other hand, we might not exclude the possibility
that CLP(FD) might help in some way or the other.

[Michael Ben Yosef]

Well, since you suggested sort/2, here is a simple, inefficient solution using it:

regnum(X) :-
regnum([1], X).

regnum([X|_], X).
regnum([X|Xs], Y) :-
X2 is 2*X,
X5 is 5*X,
sort([X2,X5|Xs], Ys),
regnum(Ys, Y).

[burs...@gmail.com]

Very nice!

[Ulrich Neumerkel]

burs...@gmail.com writes:
> nat(0).
> nat(X) :- X #= Y+1, nat(Y).
> ^D

For integers, your definition terminates never. That is, the only
situation where this terminates are cases like `nat(non_integer)`
where a type error is produced.

Consider to add the redundant constraint X #>= 1.

Even better would be to avoid the expensive creation of so many
constraints, a single AV suffices in this case.

[burs...@gmail.com]

The requirement of regnum/1 was only to enumerate
the positive part of regular numbers, not to
check whether something is a regular number.

I guess Michael Ben Yosef, which doeesnt use
CLP(FD), does also not terminate for the
call pattern regnum(+Integer),

and only works sensible for regnum(-Integer).
Which is fine concerning this riddle. For
a call pattern regnum(+Integer),

you would proceeed completely different,
not enumerate all numbers before N, but
directly attack factoring of N:

regnum(N) :- integer(N), !,
regnum_fastpath(N).
regnum(N) :-
/* Michael Ben Yosef path */

regnum_fastpath(1) :- !.
regnum_fastpath(N) :- N mod 2 =:= 0, !,
M is N//2, regnum_fastpath(M).
regnum_fastpath(N) :- N mod 5 =:= 0, !,
M is N//5, regnum_fastpath(M).