Comments from David Wilson, Mar 16 2005: My newly-submitted A104444 purports to give numbers that are not the difference of two palindromes. You asked how I could be sure that a given number was not the difference of two large palindromes. Here is my reasoning, there are empirical parts, but I think it all could be proved rigorously if necessary. Let p(n) be the nth palindrome, e.g, p(0) = 0, p(1) = 1, ..., that is p(n) = A002113(n). Let q(n) = p(n+1)-p(n) be the difference between two adjacent palindromes. We can show that Theorem 1: d(n) = p(n+1)-p(n) must be either 2, of the form 10^k (k >= 0), or of the form 11*10^k (k >= 0). This is, d(n) is in the sequence 1, 2, 10, 11, 100, 1100, 1000, 1100, 10000, 11000, ... recently submitted as A104459. Define s(d) = 10^((d-1)/2) if d is odd 11*10^((d-2)/2) if d is even. The first few values are d s(d) 1 1 2 11 3 10 4 110 5 100 6 1100 7 1000 8 11000 9 10000 etc. s(d) is the "characteristic difference" of d-digit palindromes, that is two adjacent d-digit palindromes usually differ by s(d). Specifically, we can show that=20 Theorem 2: Let p(n) have d >= 2 digits. If n !== 8 (mod 10), q(n) = p(n+1)-p(n) = s(d). In other words, the difference q(n) between the two adjacent d-digit palindromes p(n) and p(n+1) will be s(d) except for every tenth difference (when n == 8 (mod 10)) which will be some other element of A104459. ------------------------------------------------------------ Let z >= 0. Suppose we wish to determine whether z is the difference to two palindromes. Let dmin = 2*floor(log10(z)+1) = 2*(number of digits of z). dmin is the least value such that d >= dmin implies s(d) > z. Let p(n) be a palindrome of d >= dmin digits. d >= dmin implies s(d) > z and s(d+1) > z. Also, p(n+1) is a palindrome of either d or d+1 digits. Now either n !== 8 (mod 10) or n+1 != 8 (mod 10). If n !== 8 (mod 10), p(n+1)-p(n) = s(d) > z. If n+1 !== 8 (mod 10), p(n+2)-p(n+1) = s(d) > z or p(n+2)-p(n+1) = s(d+1) > z. Either way, we have p(n+2)-p(n) > z. In other words, for any palindrome p(n) of d >= dmin digits, we have p(n+2)-p(n) > z ==> p(n+k)-p(n) > z for k >= 2. This means that if z is the difference of two such palindromes, it is of the form p(n+1)-p(n), that is, the difference of two adjacent palindromes. By theorem 1, z must be in A104459. But if z is in A104459, it is the difference of two palindromes with < dmin digits. The following table shows how: z dmin difference 1 2 1-0 2 2 2-0 10 4 11-1 11 4 11-0 100 6 101-1 110 6 111-1 1000 8 1001-1 1100 8 1111-11 10000 10 10001-1 11000 10 11011-11 100000 12 100001-1 110000 12 110011-11 The pattern is obvious and can be extended to z of any number of digits. So, to tell if z is the difference of two palindromes, it suffices to check if z = p(n+k)-p(n), where p(n) is a palindrome of d < dmin = 2*(number of digits in z) digits. From davidwwilson@comcast.net Wed Apr 20 00:18:11 2005 Here are the elements of A104444 <= 10^4: 1020 1029 1031 1038 1041 1047 1051 1061 1065 1071 1074 1081 1091 1101 1130 1131 1139 1141 1148 1151 1157 1161 1171 1175 1181 1191 1201 1231 1240 1241 1249 1251 1258 1261 1267 1271 1281 1291 1301 1314 1341 1350 1351 1359 1361 1368 1371 1377 1381 1391 1401 1415 1424 1431 1451 1460 1461 1469 1471 1478 1481 1491 1501 1516 1525 1531 1534 1541 1561 1570 1571 1579 1581 1591 1601 1626 1631 1635 1641 1644 1651 1671 1680 1681 1691 1701 1718 1731 1736 1741 1745 1751 1754 1761 1781 1791 1801 1819 1828 1846 1855 1864 1911 1929 1938 1956 1965 1974 2012 2030 2039 2048 2066 2075 2140 2149 2158 2176 2203 2241 2250 2259 2268 2303 2315 2351 2360 2369 2378 2403 2416 2425 2461 2470 2479 2503 2517 2526 2535 2571 2580 2603 2627 2636 2645 2681 2703 2719 2737 2746 2755 2803 2829 2847 2856 2865 2903 2921 2939 2957 2966 2975 3013 3022 3040 3049 3067 3076 3150 3159 3177 3204 3213 3251 3260 3269 3304 3313 3316 3361 3370 3379 3404 3413 3417 3426 3471 3480 3504 3513 3518 3527 3536 3581 3604 3613 3628 3637 3646 3704 3713 3720 3738 3747 3756 3804 3821 3848 3857 3866 3904 3913 3931 3958 3967 3976 4014 4023 4032 4050 4068 4077 4160 4178 4205 4214 4261 4270 4305 4314 4317 4371 4380 4405 4414 4418 4427 4481 4505 4514 4519 4528 4537 4605 4614 4629 4638 4647 4705 4714 4721 4739 4748 4757 4805 4831 4849 4858 4867 4905 4914 4923 4941 4959 4968 4977 5015 5024 5033 5042 5069 5078 5179 5206 5215 5271 5306 5315 5318 5381 5406 5415 5419 5428 5506 5515 5520 5529 5538 5606 5615 5630 5639 5648 5706 5715 5740 5749 5758 5806 5859 5868 5906 5915 5924 5933 5969 5978 6016 6025 6034 6043 6052 6070 6079 6180 6207 6216 6307 6316 6319 6407 6416 6420 6429 6507 6516 6521 6530 6539 6607 6616 6631 6640 6649 6707 6716 6741 6750 6759 6807 6851 6869 6907 6916 6925 6934 6943 6961 6979 7017 7026 7035 7044 7053 7080 7208 7217 7308 7317 7320 7408 7417 7421 7430 7508 7517 7531 7540 7608 7617 7641 7650 7708 7717 7751 7760 7808 7861 7908 7917 7926 7935 7944 7971 8018 8027 8036 8045 8054 8072 8209 8218 8309 8318 8321 8409 8418 8431 8509 8518 8541 8609 8618 8651 8709 8718 8761 8809 8871 8909 8918 8927 8936 8945 8963 8981 9019 9028 9037 9046 9055 9073 9210 9211 9219 9231 9241 9261 9271 9281 9310 9311 9319 9321 9341 9351 9371 9381 9410 9411 9419 9421 9431 9451 9461 9481 9510 9511 9519 9521 9531 9541 9561 9571 9610 9611 9619 9621 9631 9641 9651 9671 9681 9710 9711 9721 9731 9741 9751 9761 9781 9811 9821 9831 9841 9851 9861 9871 9921 9931 9941 9951 9961 9971 9981