### Maybe we're saving the wrong thing

Maybe we should keep the lists of combinations around instead of the base values; that would get us out of the

The problem is that the bitmap moves us back to O(n), where n is the number of digits, rather than a fixed amount of work (because there's a fixed upper bound on the number of nonzero digits). We could roll our own bit fields, and stuff up to three

I'll have to think about that some more. In the meantime, I restructured the code a little bit to make the code that generates Ys more clearly parallel to the code that just counts them. The counting code:

The generating code:

Yeah, I guess that shows I'm seriously at the point of diminishing returns.

**divMod**business, though OTOH it means hanging on to those lists; as it stands, I bet that they're being garbage collected.The problem is that the bitmap moves us back to O(n), where n is the number of digits, rather than a fixed amount of work (because there's a fixed upper bound on the number of nonzero digits). We could roll our own bit fields, and stuff up to three

**bitsIn (n `div` 2)**values into an**Int**or an**Integer**(actually, Haskell has**Int8**,**Int16**,**Int32**, and**Int64**types to choose from; 21 bits a shot would allow for up to two million digits, times two for both halves of the palindrome--that's a lot bigger than the second official data set needs), but that seems kind of cheesy.I'll have to think about that some more. In the meantime, I restructured the code a little bit to make the code that generates Ys more clearly parallel to the code that just counts them. The counting code:

**numNDigitYs :: Int -> Int**

numNDigitYs 1 = 3

numNDigitYs n = numTwoTwos n + numOneTwos n + numNoTwos n

where numTwoTwos n = if even n then 1 else 2

numOneTwos n = if even n then 0 else n `div` 2

numNoTwos n = if even n then s else 2 * s

where h = n `div` 2 - 1

s = sum [h `choose` i | i <- [0..min h 3]]numNDigitYs 1 = 3

numNDigitYs n = numTwoTwos n + numOneTwos n + numNoTwos n

where numTwoTwos n = if even n then 1 else 2

numOneTwos n = if even n then 0 else n `div` 2

numNoTwos n = if even n then s else 2 * s

where h = n `div` 2 - 1

s = sum [h `choose` i | i <- [0..min h 3]]

The generating code:

**nDigitYs :: Int -> [Integer]**

nDigitYs 1 = [1,2,3]

nDigitYs n = sort (noTwos n ++ oneTwos n ++ twoTwos n)

where twoTwos n

| even n = [twoTwosNoOnes]

| otherwise = [twoTwosNoOnes,

twoTwosNoOnes + tenToThe (n `div` 2)]

where twoTwosNoOnes = 2 * tenToThe (n - 1) + 2

oneTwos n

| even n = []

| otherwise = map (+ 2 * tenToThe halfN)

(justOnes n (min 1 (halfN - 1)))nDigitYs 1 = [1,2,3]

nDigitYs n = sort (noTwos n ++ oneTwos n ++ twoTwos n)

where twoTwos n

| even n = [twoTwosNoOnes]

| otherwise = [twoTwosNoOnes,

twoTwosNoOnes + tenToThe (n `div` 2)]

where twoTwosNoOnes = 2 * tenToThe (n - 1) + 2

oneTwos n

| even n = []

| otherwise = map (+ 2 * tenToThe halfN)

(justOnes n (min 1 (halfN - 1)))

**where halfN = n `div` 2**

noTwos n

| even n = base

| otherwise = concat [[p, p + tenToThe halfN] | p <- base]

where halfN = n `div` 2

base = justOnes n (min 3 (halfN - 1))noTwos n

| even n = base

| otherwise = concat [[p, p + tenToThe halfN] | p <- base]

where halfN = n `div` 2

base = justOnes n (min 3 (halfN - 1))

Yeah, I guess that shows I'm seriously at the point of diminishing returns.

## Comments