### Of course there's a pattern

I can't believe I didn't see it before. Here's the deal:

The 65536-dollar question, then, is whether it's worthwhile to generate them this way. (And of course, you can generate the ones with one less one per half for 2 * k digits from those with two less ones per half for 2 * k - 2 digits. That doesn't go on forever, to be sure; since the added ones per half is no bigger than three, you're down to the base case of 100...001 pretty quickly. Again, though, is it worth it?)

One thing to consider that might help out: doing

(OK, I admit I've limited some things in my code to

I'll have to think about this some more.

UPDATE: I pulled the counting routines, tweaked them to take and return Integer, and then did

Turns out you have to get past 10^515 before the number of Ys risks going past 2^29 (and hence needing an

- You can get from the base values for 2 * k digits to those for 2 * k + 1 digits as we described earlier.
- You can get from the base values for 2 * k digits to
*some*of those for 2 * k + 2 digits.

*don't*have ones in the gap. The ones that*do*have ones in the gap have, outside the gap, the halves of 2 * k digit palindromes that have one less one per half than the base values for 2 * k digits, because only that way do you get ones left over to fill the gap.The 65536-dollar question, then, is whether it's worthwhile to generate them this way. (And of course, you can generate the ones with one less one per half for 2 * k digits from those with two less ones per half for 2 * k - 2 digits. That doesn't go on forever, to be sure; since the added ones per half is no bigger than three, you're down to the base case of 100...001 pretty quickly. Again, though, is it worth it?)

One thing to consider that might help out: doing

**justOnes**and**noTwos**sorts of things purely in binary and moving back to decimal only at the very end. If we take this route, it would also be worth dealing purely with the upper halves of the no-one Ys until it's time to convert. Consider: dealing with the Ys takes you down from at most 100 decimal digits to at most 50 decimal digits. Dealing with just the upper half takes you down to at most 25 decimal digits. Doing the stuff where the decimal digits are restricted to ones and zeros means you can operate on values with at most 25*bits*until the very end. Save the arbitrary precision for where you need it, right? Even if, like me, you kind of hate setting arbitrary limits, in practice it will mean that your**Integer**s will actually, for purposes of this problem, be small enough that operations on them will be, if they're implemented by a list or array of fixed-size hunks, the fastest kind, because there will only be one hunk to mess with.(OK, I admit I've limited some things in my code to

**Int**rather than**Integer**. OTOH, I think the (29-bit)**Int**values suffice, since there are only something like 51,000 of these palindromes up to a googol, for heaven's sake, I suspect, though I haven't calculated, that there aren't 2^29, or around 512 million of the palindromes, until a pretty darned big upper bound. OK, maybe it's 256 million--signed, right?--but that's still on up there.)I'll have to think about this some more.

UPDATE: I pulled the counting routines, tweaked them to take and return Integer, and then did

**last $ takeWhile (\(x, y) -> y <= 2^29) (zip [1..] nDigitYsPartialSums)**Turns out you have to get past 10^515 before the number of Ys risks going past 2^29 (and hence needing an

**Integer**to count them), and thus the corresponding Xs would be up around 10^1030.
## Comments