5

Browsing through the awesome On-Line Encyclopedia of Integer Sequences (cf. en.wikipedia.org), I stumbled upon the following integer sequence:

A031877: Nontrivial reversal numbers (numbers which are integer multiples of their reversals), excluding palindromic numbers and multiples of 10.

By re-using some code I wrote for my answer to the related question "Faster implementation of verbal arithmetic in Prolog" I could write down a solution quite effortlessly—thanks to !

:- use_module(library(clpfd)).

We define the core relation a031877_ndigits_/3 based on digits_number/2 (defined earlier):

a031877_ndigits_(Z_big,N_digits,[K,Z_small,Z_big]) :-
   K #> 1,
   length(D_big,N_digits),
   reverse(D_small,D_big),
   digits_number(D_big,Z_big),
   digits_number(D_small,Z_small),
   Z_big #= Z_small * K.

The core relation is deterministic and terminates universally whenever N_digit is a concrete integer. See for yourself for the first 100 values of N_digit!

?- time((N in 0..99,indomain(N),a031877_ndigits_(Z,N,Zs),false)).
% 3,888,222 inferences, 0.563 CPU in 0.563 seconds (100% CPU, 6903708 Lips)
false

Let's run some queries!

?- a031877_ndigits_(87912000000087912,17,_).
  true                                % succeeds, as expected
; false.

?- a031877_ndigits_(87912000000987912,17,_).
false.                                % fails, as expected

Next, let's find some non-trivial reversal numbers comprising exactly four decimal-digits:

?- a031877_ndigits_(Z,4,Zs), labeling([],Zs).
  Z = 8712, Zs = [4,2178,8712]
; Z = 9801, Zs = [9,1089,9801]
; false.

OK! Let's measure the runtime needed to prove universal termination of above query!

?- time((a031877_ndigits_(Z,4,Zs),labeling([],Zs),false)).
% 11,611,502 inferences, 3.642 CPU in 3.641 seconds (100% CPU, 3188193 Lips)
false.                                % terminates universally

Now, that's way too long!

What can I do to speed things up? Use different and/or other constraints? Maybe even redundant ones? Or maybe identify and eliminate symmetries which slash the search space size? What about different clp(*) domains (b,q,r,set)? Or different consistency/propagation techniques? Or rather Prolog style coroutining?

Got ideas? I want them all! Thanks in advance.

Community
  • 1
  • 1
repeat
  • 18,496
  • 4
  • 54
  • 166

2 Answers2

1

So far ... no answers:(

I came up with the following...

How about using different variables for labeling/2?

a031877_ndigitsNEW_(Z_big,N_digits,/* [K,Z_small,Z_big] */
                                      [K|D_big]) :-
   K #> 1,
   length(D_big,N_digits),
   reverse(D_small,D_big),
   digits_number(D_big,Z_big),
   digits_number(D_small,Z_small),
   Z_big #= Z_small * K.

Let's measure some runtimes!

?- time((a031877_ndigits_(Z,4,Zs),labeling([ff],Zs),false)).
% 14,849,250 inferences, 4.545 CPU in 4.543 seconds (100% CPU, 3267070 Lips)
false.

?- time((a031877_ndigitsNEW_(Z,4,Zs),labeling([ff],Zs),false)).
%    464,917 inferences, 0.052 CPU in 0.052 seconds (100% CPU, 8962485 Lips)
false.

Better! But can we go further? 

?- time((a031877_ndigitsNEW_(Z,5,Zs),labeling([ff],Zs),false)).
%  1,455,670 inferences, 0.174 CPU in 0.174 seconds (100% CPU, 8347374 Lips)
false.

?- time((a031877_ndigitsNEW_(Z,6,Zs),labeling([ff],Zs),false)).
%  5,020,125 inferences, 0.614 CPU in 0.613 seconds (100% CPU, 8181572 Lips)
false.

?- time((a031877_ndigitsNEW_(Z,7,Zs),labeling([ff],Zs),false)).
% 15,169,630 inferences, 1.752 CPU in 1.751 seconds (100% CPU, 8657015 Lips)
false.

There is still lots of room for improvement, for sure! There must be...

repeat
  • 18,496
  • 4
  • 54
  • 166
1

We can do better by translating number-theoretic properties into the language of constraints!

All terms are of the form 87...12 = 4*21...78 or 98...01 = 9*10...89.

We implement a031877_ndigitsNEWER_/3 based on a031877_ndigitsNEW_/3 and directly add above property as two finite-domain constraints:

a031877_ndigitsNEWER_(Z_big,N_digits,[K|D_big]) :-
   K in {4}\/{9},                        % (new)
   length(D_big,N_digits),
   D_big ins (0..2)\/(7..9),             % (new)
   reverse(D_small,D_big),
   digits_number(D_big,Z_big),
   digits_number(D_small,Z_small),
   Z_big #= Z_small * K.

Let's re-run the benchmarks we used before!

?- time((a031877_ndigitsNEWER_(Z,5,Zs),labeling([ff],Zs),false)).
% 73,011 inferences, 0.006 CPU in 0.006 seconds (100% CPU, 11602554 Lips)
false.

?- time((a031877_ndigitsNEWER_(Z,6,Zs),labeling([ff],Zs),false)).
% 179,424 inferences, 0.028 CPU in 0.028 seconds (100% CPU, 6399871 Lips)
false.

?- time((a031877_ndigitsNEWER_(Z,7,Zs),labeling([ff],Zs),false)).
% 348,525 inferences, 0.037 CPU in 0.037 seconds (100% CPU, 9490920 Lips)
false.

Summary: For the three queries, we consistently observed a significant reduction of search required. Just consider how much the inference counts shrank: 1.45M -> 73k, 5M -> 179k, 15.1M -> 348k.

Can we do even better (while preserving declarativity of the code)? I don't know, I guess so...

repeat
  • 18,496
  • 4
  • 54
  • 166