回文数通项公式

chyanog

回文数一般人都不陌生，有关算法也不少。刚才在本论坛搜索，发现大都是关于回文素数的帖子。 我在暑假注意到原来回文数（目前只考虑十进制的）还可以有递归算法的，甚至可以写出通项公式。 由于三位的具有代表性又简单，以此为例：

2. f[n_] := If[n <= 1, 101, If[n <= 10, f[n - 1] + 10, f[n - 10] + 101]]

复制代码

这个式子能否继续化简还不确定。在网上也没有找到相关资料，估计可以归结为求解高阶差分方程，由于非数学背景，这方面我还没有接触过，不知道大家有多少研究。

chyanog

真冷清，看来大家觉得这题没意思啦

wayne

2# chyanog 那个递归算法只能说仅仅适用于1000以下，四位数及以上就不正确了。

wayne

1# chyanog 通项公式是怎么得来的

chyanog

谢谢wayne的关注！

chyanog

我上面仅以三位为例,下面附上三位到六位的：

2. f3[n_] :=
3. If[n <= 1, 101, If[n <= 10, f3[n - 1] + 10, f3[n - 10] + 101]]
5. f4[n_] :=
6. If[n <= 1, 1001, If[n <= 10, f4[n - 1] + 110, f4[n - 10] + 1001]]
8. f5[n_] :=
9. If[n <= 1, 10001,
10. If[n <= 10, f5[n - 1] + 100,
11. If[n <= 100, f5[n - 10] + 1010, f5[n - 100] + 10001]]]
13. f6[n_] :=
14. If[n <= 1, 100001,
15. If[n <= 10, f6[n - 1] + 1100,
16. If[n <= 100, f6[n - 10] + 10010, f6[n - 100] + 100001]]]

复制代码

chyanog

三位回文数：

2. #include <stdio.h>
3. #include <math.h>
4. #define Pi 2*asin(1.0)
5. double p3(double n)
6. {
7. return (9045 + 1010*n - 5*cos(Pi*n) -
8. 5*(1 + sqrt(5))*(cos((Pi*(2 - 9*n))/5.) + cos((Pi*(2 + n))/5.)) -
9. 5*(-1 + sqrt(5))*(cos((Pi*(1 - 7*n))/5.) +
10. cos((Pi*(1 + 3*n))/5.)) -
11. sqrt(50 - 10*sqrt(5))*(sin((2*Pi*(1 - 2*n))/5.) +
12. sin((2*Pi*(1 + 3*n))/5.)) -
13. sqrt(50 + 10*sqrt(5))*(sin((Pi*(1 - 2*n))/5.) +
14. sin((Pi*(1 + 8*n))/5.)))/100. ;
15. }
16. int main()
17. {
18. for(int i=1;i<=90;i++)
19. printf("%d\t",(int)p3(i));
20. return 0;
21. }

复制代码

四位回文数：

2. #include <stdio.h>
3. #include <math.h>
4. #define Pi 2*asin(1.0)
5. double p4(double n)
6. {
7. return (11*(8595 + 910*n + 45*(1 + sqrt(5))*cos(((2 - 9*n)*Pi)/5.) + 100*cos((4*n*Pi)/5.) + 45*cos(n*Pi) - 55*cos((6*n*Pi)/5.) +
8. 45*(1 + sqrt(5))*cos(((2 + n)*Pi)/5.) + 45*(-1 + sqrt(5))*cos((Pi - 7*n*Pi)/5.) + 45*(-1 + sqrt(5))*cos((Pi + 3*n*Pi)/5.) -
9. 25*sqrt(10 - 2*sqrt(5))*sin((4*n*Pi)/5.) + sqrt(50 - 10*sqrt(5))*
10. (20*sin((2*(1 - 3*n)*Pi)/5.) - 11*sin((2*(1 - 2*n)*Pi)/5.) + 5*sin((4*n*Pi)/5.)) + 29*sqrt(5*(5 - 2*sqrt(5)))*sin((6*n*Pi)/5.) -
11. sqrt(10*(5 + sqrt(5)))*(20*sin((2*(1 - 4*n)*Pi)/5.) + 20*sin((2*(-1 + n)*Pi)/5.) + 20*sin((2*n*Pi)/5.) - 20*sin((8*n*Pi)/5.) +
12. 20*sin((2*(1 + n)*Pi)/5.) - 20*sin((Pi - 8*n*Pi)/5.) + 11*sin((Pi - 2*n*Pi)/5.) -
13. 20*(sin((Pi + 2*n*Pi)/5.) + sin((2*(Pi + 4*n*Pi))/5.)) + 11*sin((Pi + 8*n*Pi)/5.))))/100.;
14. }
15. int main()
16. {
17. for(int i=1;i<=90;i++)
18. printf("%d\t",(int)p4(i));
19. return 0;
20. }

复制代码

chyanog

4# wayne 估计你也能猜出来是用Mathematica算出来的，

wayne

8# chyanog n位回文数本质上就是n/2个数字的自由排列问题， 用递归相对来说还是低效了点。

chyanog

9# wayne 数字的自由排列问题，不怎么了解， 。递归一般都比较低效，那么高效的方法应该是直接构造了吧：譬如

2. Table[i, {i,0,9}]
3. Table[11 i, {i, 9}]
4. Flatten@Table[101 i + 10 j, {i, 9}, {j, 0, 9}]
5. Flatten@Table[1001 i + 110 j, {i, 9}, {j, 0, 9}]
6. ... ...

复制代码