Prolog： 使用 clp(FD) 计算 OEIS A031877 ( "nontrivial reversal numbers" )

Question

浏览令人敬畏的在线整数序列百科全书(cf.en.wikipedia.org)时，我偶然发现了以下整数序列:

A031877:非平凡反转数(其反转数的整数倍)，不包括回文数和10的倍数。

通过重用我为回答相关问题"在Prolog中更快地实现口头算术"而写的一些代码，我可以毫不费力地写下一个解决方案——感谢clpfd!

:- use_module(library(clpfd)).

定义核心关系 a031877_ndigits_/3digits_number/2(前面定义的):

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.

核心关系是确定性的， 在任何时候都普遍终止N_digit为具体整数。查看N_digit的前100个值!

?- 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

让我们运行一些查询!

<>之前? - a031877_ndigits_(87912000000087912, 17日_)。如预期的那样成功;假的。? - a031877_ndigits_ (87912000000 87912, 17日_)。假的。%如预期的那样失败之前

接下来，让我们找到一些非平凡的反转数，它们恰好包含四位小数:

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

OK !让我们测量证明上述查询的通用终止所需的运行时间!

?- 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

现在，太长了!

我怎么做才能加快速度?使用不同的和/或其他约束?甚至是多余的?或者识别并消除那些减少搜索空间大小的对称性?那么不同的clp(*)域(b,q,r,set)呢?或者不同的一致性/传播技术?或者更确切地说，Prolog风格的协同?

有想法吗?我都要!

Answer 1

So far…没有答案:(

我得出以下结论…

为labeling/2使用不同的变量如何?

<>之前a031877_ndigits新 _ (Z_big N_digits,/* <年代> [K Z_small Z_big] */ [K | D_big] ): -k#> 1;长度(D_big N_digits),反向(D_small D_big),digits_number (D_big Z_big),digits_number (D_small Z_small),Z_big #= Z_small * K。之前

让我们测量一些运行时间!

?- 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.

更好!但是我们能走得更远吗?

?- 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.

当然还有很多改进的空间!

Answer 2

我们可以通过将数论性质转换成约束语言来更好地处理 !

所有条款均为87…12 = 4*21…78或98…2 .

我们在a031877_ndigitsNEW_/3的基础上实现了a031877_ndigitsNEWER_/3，并直接将上述属性添加为两个有限域约束:

<>之前a031877_ndigitsNEWER_ (Z_big N_digits [K | D_big]): -， ， % (new)长度(D_big N_digits), D_big ins (0 . . 2) /(7 . . 9) , % ( 新)反向(D_small D_big),digits_number (D_big Z_big),digits_number (D_small Z_small),Z_big #= Z_small * K。之前

让我们重新运行之前使用的基准测试!

?- 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.

总结:对于这三个查询，我们一致地观察到所需的搜索量显著减少。只要考虑一下推理计数减少了多少:1.45M -> 73k, 5M -> 179k, 15.1M -> 348k。

我们能做得更好吗(同时保留代码的声明性)?我不知道，我想是的。