By popular request: The most obvious way to find dual binary-ternary palindromes is to try each N, see if it's a binary palindrome, and if so see if it's also a ternary palindrome. But this is very inefficient, since the vast majority of numbers are neither. A much better approach is to turn successive integers into the left half of a binary palindrome, then test them to see if they're also ternary palindromes. All binary palindromes must be odd (since otherwise the first digit, like the last, would be 0), and likewise all ternary palindromes must not be divisible by 3. So all dual palindromes must not be divisible by either 2 or 3. For a binary palindrome to not be divisible by 3, it must be of odd length. For a ternary palindrome to not be divisible by 2, it must be of odd length and have 1 as a middle digit. (Proofs on request.) So ternary palindromes are scarcer, so it's even more efficient to turn successive integers into the left half of a ternary palindrome and test each of them to see if they're also a binary palindrome. (I'm using "half" loosely, since the middle digit is constant.) It's more efficient yet to skip ranges of integers which, when represented as odd-length ternary palindromes with 1 as a middle digit, would be represented by even-length binary numbers, since those numbers would either not be binary palindromes or would be divisible by 3, hence can't be dual binary-ternary palindromes. That's how my first program worked. It found the first five solutions in less than a second, the sixth after a few hours, and the seventh and last then known solution after about two weeks. Each block of numbers to be tested started where both binary and ternary representations of the number started being of odd length and stopped where this ceased to be the case. There's no pattern to these overlaps, since powers of 2 and powers of 3 are not commensurate, i.e. no positive integer power of 2 is equal to an integer power of 3. Old-timers may be amused that to clarify how these overlaps fit together, I used a slide rule. Of course I precomputed the start and stop points. It then occurred to me that these blocks can be divided into parts where the binary numbers begin with 10 and parts where they begin with 11. The former numbers must of course end with 01 and the latter with 11, since they're to be palindromes. So instead of generating every ternary palindrome of the appropriate length with 1 as a middle digit, I could skip the half of them whose digits adjacent to the middle digit would give the wrong remainder when the palindrome was divided by 4. For binary numbers beginning with 10, hence ending with 01, that remainder must be 1, and for binary numbers beginning with 11, hence ending with 11, that remainder must be 3. This would almost double the speed of the program. But why stop there? Have four blocks for each odd binary length, for binary numbers beginning with 100, 101, 110, and 111, then only generate ternary palindromes whose 8-remainder is correct in the first place. This would almost double the speed of the program yet again. (Of course for the average binary length, about half of those blocks wouldn't even be used, since the ternary representations would be of even length about half the time.) But why stop there either? I could keep doing this until I run out of memory, making the program faster and faster. I had thought of all this by December 14th when I challenged Alan Grimes, a younger programmer who considered both my programming skills and my computer hardware to be obsolete, to a race to find the 8th dual binary-ternary palindrome, he with his faster and more modern computers, and I with my "obsolete" programming skills. Much to my surprise and annoyance, he won, discovering an 8th solution just two days later, which was before I even started writing my program. His solution, 2004595370006815987563563, has 25 decimal digits, 51 ternary digits (trits), and 81 binary digits (bits). His program was based on my description of my first program, which I had posted on alt.math.recreational, but was even simpler than my first program, as it didn't skip over ranges with even-length binary palindromes. I'll use rediscovering Alan's number as an example of how my program works. I split the numbers that have some fixed odd number of bits, in this case 81, into 2^15 (32768) equal blocks, each of which begins with 1 followed by a unique 15 bits. In this case only the first 25609 of those blocks are used, since the last 7159 would map into ternary numbers with 52 trits, which can't be odd numbers if they're palindromes. The block which contains Alan's number begins 1101010000111110xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx and ends with 1101010000111111xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx with yet-to-be-determined digits replaced with "x". Converting those binary numbers to ternary (with the "x"s all turned to "0"s in the first (start) case and "1"s in the second (stop) case) gets me 221010112010200xxxxxxxxxx1xxxxxxxxxx002010211010122 through 221010112100211xxxxxxxxxx1xxxxxxxxxx112001211010122 with yet-to-be-determined digits once again replaced with "x"s. (In the "stop" case, I round the ternary number up, not down, hence it begins 221010112100211, not 221010112100210.) So instead of testing 1.4 million ternary palindromes to search for binary palindromes in this range, I only have to test 247: 221010112010200xxxxxxxxxx1xxxxxxxxxx002010211010122 through 221010112110210xxxxxxxxxx1xxxxxxxxxx012011211010122 (Alan's solution is 221010112100202xxxxxxxxxx1xxxxxxxxxx202001211010122 but we don't know that yet.) But wait, what goes in place of the "x"s? If I have to try all possible ten-digit ternary numbers, I haven't gained anything. Fortunately, I don't have to do anything of the kind. I know what the 65536-remainder of the number must be. All numbers in this block begin with with 1101010000111110 in binary so they must all end with 0111110000101011, which is 31787. So I just have to arrange for the ternary palindrome to have the same remainder when divided by 65536. How do I do that? First I calculate and store the remainders of the successive powers of 3 when they're divided by 65536. They start 1, 3, 9, 27, 81, 243, 729, 2187, 6561, 19683, 59049, 46075, 7153, 21459. This series repeats after 16384 terms, but I only calculate and store the first 123 of them. I do this only once for the whole program. It takes a small fraction of a second. Next I calculate the 65536-remainder of the following 16 ternary numbers (leading 0s retained for clarity): 100000000000000000000000000000000000000000000000001 010000000000000000000000000000000000000000000000010 001000000000000000000000000000000000000000000000100 000100000000000000000000000000000000000000000001000 000010000000000000000000000000000000000000000010000 000001000000000000000000000000000000000000000100000 000000100000000000000000000000000000000000001000000 000000010000000000000000000000000000000000010000000 000000001000000000000000000000000000000000100000000 000000000100000000000000000000000000000001000000000 000000000010000000000000000000000000000010000000000 000000000001000000000000000000000000000100000000000 000000000000100000000000000000000000001000000000000 000000000000010000000000000000000000010000000000000 000000000000001000000000000000000000100000000000000 000000000000000100000000000000000001000000000000000 000000000000000010000000000000000010000000000000000 000000000000000001000000000000000100000000000000000 000000000000000000100000000000001000000000000000000 000000000000000000010000000000010000000000000000000 000000000000000000001000000000100000000000000000000 000000000000000000000100000001000000000000000000000 000000000000000000000010000010000000000000000000000 000000000000000000000001000100000000000000000000000 000000000000000000000000101000000000000000000000000 These numbers, the sum of the 0th and 50th term of the previous series, followed by the sum of the 1st and the 49th, the 2nd and 48th, ... the 24th and 26th, all modulo 65536, are 58314, 41286, 13770, 4614, 1610, 22598, 30026, 33798, 17098, 1350, 52938, 44038, 6474, 43078, 49738, 35334, 2506, 16710, 53194, 7686, 37962, 53318, 30538, 26630, and 14538. I then store twice those numbers (mod 65536) to represent the remainders of: 200000000000000000000000000000000000000000000000002 020000000000000000000000000000000000000000000000020 002000000000000000000000000000000000000000000000200 000200000000000000000000000000000000000000000002000 000020000000000000000000000000000000000000000020000 000002000000000000000000000000000000000000000200000 000000200000000000000000000000000000000000002000000 000000020000000000000000000000000000000000020000000 000000002000000000000000000000000000000000200000000 000000000200000000000000000000000000000002000000000 000000000020000000000000000000000000000020000000000 000000000002000000000000000000000000000200000000000 000000000000200000000000000000000000002000000000000 000000000000020000000000000000000000020000000000000 000000000000002000000000000000000000200000000000000 000000000000000200000000000000000002000000000000000 000000000000000020000000000000000020000000000000000 000000000000000002000000000000000200000000000000000 000000000000000000200000000000002000000000000000000 000000000000000000020000000000020000000000000000000 000000000000000000002000000000200000000000000000000 000000000000000000000200000002000000000000000000000 000000000000000000000020000020000000000000000000000 000000000000000000000002000200000000000000000000000 000000000000000000000000202000000000000000000000000 Those numbers are 51092, 17036, 27540, 9228, 3220, 45196, 60052, 2060, 34196, 2700, 40340, 22540, 12948, 20620, 33940, 5132, 5012, 33420, 40852, 15372, 10388, 41100, 61076, 53260, and 29076. Of course I already have the remainder for 3^25: 000000000000000000000000010000000000000000000000000 It's 10915. Note that I calculate and store these 33 numbers just once for all length-51 ternary palindromes. Again, this only takes a tiny fraction of a second. And it takes negligible memory to store them. To find the remainder for a given ternary palindrome, I then just add them together as appropriate. That's just 17 additions. Or rather 16, since I start my sum, not with 0, but with 10915, the remainder for 3^25. For instance to find the 65536-remainder for Alan's 221010112100202xxxxxxxxxx1xxxxxxxxxx202001211010122 with the "x"s set to 0 I add the remainders for 000000000000000000000000010000000000000000000000000 10915 200000000000000000000000000000000000000000000000002 51092 020000000000000000000000000000000000000000000000020 17036 001000000000000000000000000000000000000000000000100 13770 000000000000000000000000000000000000000000000000000 0 000010000000000000000000000000000000000000000010000 1610 000000000000000000000000000000000000000000000000000 0 000000100000000000000000000000000000000000001000000 30026 000000010000000000000000000000000000000000010000000 33798 000000002000000000000000000000000000000000200000000 34196 000000000100000000000000000000000000000001000000000 1350 000000000000000000000000000000000000000000000000000 0 000000000000000000000000000000000000000000000000000 0 000000000000200000000000000000000000002000000000000 12948 000000000000000000000000000000000000000000000000000 0 000000000000002000000000000000000000200000000000000 33940 The sum (mod 65536) is 44073. Recall that the target remainder for the ternary palindrome is 31787. So we need the digits in the "x"s to -- if they stood alone and all other digits were 0 -- have a remainder of 31787 minus 44073, which equals (mod 65536) 53250. How do we know what to set the "x"s to to get it to come out right? Simple. We try all 3^10 (59049) possible combinations of ternary digits. But wouldn't that be just as slow as Alan's method? No, because I do this just once for all 51-trit numbers, and save the results in a table. Here's the relevant section of that table: 53244: 0001102022 0122200010 1011221000 1110201200 2111212222 53246: 2110212000 53248: 53250: 0002001202 0021200022 53252: 0000122102 1002012002 53254: 0021101211 2221222112 53256: 1021112011 There are two solutions for 53250. There can be anywhere from 0 to 6 solutions. The average number of solutions is about 1.8 (3^10/2^9). By "solution" I mean the remainder comes out right, not that it necessarily generates a dual palindrome. We try both. The second one works, i.e. generates a binary number that's a palindrome. 221010112100202xxxxxxxxxx1xxxxxxxxxx202001211010122 0021200022 2200021200 equals 110101000011111010101010100101111011110111011110111101001010101010111110000101011 which is a palindrome. There is of course no guarantee that one of the solutions on the appropriate row of the table will generate a binary palindrome. In the vast majority of cases none of the solutions will work. On the other hand, it's unlikely but not impossible that more than one of them will do so. (Well, very likely it *is* impossible, but I'm not going to take the time to try to prove it.) But if there is a binary palindrome, it has to correspond to one of the table entries on the correct row. This method is guaranteed not to miss any. This table comprises the vast majority of the memory usage of my program. It has 32768 rows (remainders here can only be even, so there aren't 65536 rows), each with 6 columns, each with 10 ternary digits, for a total of just under 2 megabytes. If this was too much, I could redo it with pointers and save about 2/3 of that space. Yes, I store the ternary numbers in this table in ternary, so I don't have to keep converting the same numbers. And with one digit per array element so I don't have to keep unpacking the same numbers. If I coded this program in the obvious way, the CPU time would be dominated by ternary to binary conversions. So I avoid doing them. Instead, I created a table of powers of 3 in binary, just once for the whole program, then added them together in pairs, just once for each length of ternary numbers. For instance for 51-trit numbers I have 3^50 + 3^0, 3^49 + 3^1, ... 3^24 + 3^26. I also store twice these numbers, to correspond to 2...2 in ternary. Then I just add together, in binary, the appropriate subset of them for each ternary palindrome. For Alan's number they're the binary numbers for: 000000000000000000000000010000000000000000000000000 200000000000000000000000000000000000000000000000002 020000000000000000000000000000000000000000000000020 001000000000000000000000000000000000000000000000100 000010000000000000000000000000000000000000000010000 000000100000000000000000000000000000000000001000000 ... etc. Binary addition is of course very fast, even though instead of using the computer's native binary I'm using arrays with one digit per element of the array. I do this for binary, ternary, and decimal. This way I never have to worry about overrunning the computer's word length, nor do I waste time repeatedly packing and unpacking digits. If the program has found a dual palindrome, only then does it take the time to covert the number to base 10, to display on the screen or save to a file. One more way in which I sped things up: In the above I kept talking about taking the 65536-remainder of various numbers. I actually never did this. Instead I stored the relevant numbers in unsigned 16-bit integers (uint16_t), which automatically did that for me, taking literally no time at all, and making the program both faster and less cluttered. It's ironic that Alan sped things up by switching from 32-bit integers to 64-bit integers, and that I sped things up enormously more by (in part) switching from 32-bit integers to 16-bit integers. Further speedups are possible by using larger tables, trading memory for time. When my program found the ninth dual palindrome, 8022581057533823761829436662099, on January 7th, I was already in the process of rewriting it to use 20-bit tables rather than 16-bit, in conjunction with 12-trit rather than 10-trit numbers. But I wisely kept the old program running, and it found the above number before I finished rewriting. (And it's *still* running. I'll terminate it after it rolls over to 105-bit numbers, which I expect will happen on the 12th or 13th.) Also, for each of those 12-trit numbers, my planned upgraded program would have stored the binary equivalent. For instance for my newly discovered palindrome, which is 21000020210011222122 220212010000 1 000010212022 22122211001202000012 in ternary, the relevant 12-trit number would be 220212010000, so 220212010000 1 000102120220 00000000000000000000 would be converted to binary and stored along with the other table. (Spaces added for clarity.) Similarly with all 531440 other 12-trit numbers, of course. This would be done just once for each trit-length of the number being tested (in this case 65). This would speed up the binary addition. I could speed it up even more by creating similar tables for other chunks of trits. So to convert my ternary palindrome, 21000020 210011222122 220212010000 1 000010212022 221222110012 02000012 to binary, I'd just look up in the tables the pre-computed binaries for 21000020 000000000000 000000000000 0 000000000000 000000000000 02000012 210011222122 000000000000 0 000000000000 221222110012 00000000 220212010000 1 000010212022 000000000000 00000000 Then I'd just add these three binary numbers and check the result to see if it's a binary palindrome. Again, the ternary-to-binary conversion and checking the result to see if it's a palindrome is where the program spends most of its time, so this is where speedups are most critical. Of course it should go without saying that when I check a binary number to see if it's a palindrome, I quit as soon as I find the first non-matching pair of bits, rather than wasting time checking all the other pairs of bits. The vast majority of candidate binary numbers are *not* palindromes. All my programs were written in C (as were Alan's), but I could have written them in any language. I made no use of recursion, dynamic memory allocation, or pointers. I didn't even use floating point numbers or 64-bit integers. I did use multidimensional arrays. (Why, yes, I did used to be a Fortran programmer. How could you tell?) (Well, okay, my numerical integration program used floating point, but my program for finding dual palindromes did not.) Most of these ideas could easily be generalized to find dual palindromes in other pairs of bases. Or, even more easily, to find dual palindromes in binary and *balanced* ternary. (I suspect that the statistics on those are the same as on binary and standard ternary. But certainly balanced ternary palindromes look prettier, if written, as usual, with the single characters +, 0, and - for digits, since those characters are themselves symmetrical.) To summarize, what I do or recommend is: * Precompute as much as you have room to store, just once for for each trit length. Where possible (e.g. powers of 3 in binary) just once for the whole program. * Skip ranges where there can't be solutions. * Avoid packing and unpacking numbers, and having to worry about overrunning word lengths. Instead, I always use one digit per array element. * Don't bother to ever convert anything to decimal except successful palindromes. * Start the program with numbers as small as possible (2^35 if you're using 16-bit remainders) to make sure it finds all known dual palindromes and doesn't "find" any bogus ones. * Check any new dual palindromes it finds, using a completely different program, to make absolutely certain they aren't bogus. --- [ I'm looking for an IT job in the DC area. So is Alan, and so are many other experienced programmers I know. Employers simply aren't hiring. Not even the ones who complain to Congress that they can't find anyone to hire. ]