## » Beust Sequence Ruminations #

*Paul R. Brown*@ 2008-07-02

Cédric posted a nice puzzle on his blog:

[W]rite a counter function that counts from 1 to max but only returns numbers whose digits don't repeat.

Bob tweeted
about a minimal solution in
terms of execution time, although (like the guy in the cartoon)
I still like my Haskell version of the sequence (up to some details
with use of `Data.Int.Int64`

and typing the enumeration):

f k = [ n | n <- [1..k], (length . show $ n) == (length . nub . show $ n) ]

And the function to compute the maximum gap:

drop_tail k = reverse . (drop k) . reverse by_pairs u = zip (drop 1 u) (drop_tail 1 u) g k = maximum . map (uncurry (-)) . by_pairs . f $ k

This approach, while visually appealing, is unacceptably slow, even
with some of the usual optimizations applied. The fact is that any
solution that is implemented in terms of testing all of the numbers
between `0`

and `k`

will perform orders of
magnitude more poorly than the recursive style that Bob's using. But
how would I know that...?

### Subfactorials, Derangements, and Chooses

A *derangement* is a permutation with no fixed points, e.g.,
`(123)`

is a derangement of the set `{1,2,3}`

,
but `(12)`

is not because it maps `3`

to
`3`

. Like the number of permutations of an
`n`

-element set (`n!`

), the number of
derangements has its own function called the subfactorial and written
`!n`

. MathWorld has a decent write-up,
with the major takeaway for present purposes being that ```
!n ~
n!
```

.

The number of elements in Cédric's set, for a fixed radix
`n`

is the sum from `k=0`

up to `n`

of `!k (n choose k)`

, and that's *much* smaller than
`n`

. (This reminds me of the whole "bad
shuffle" meme
from a long time ago.)^{n}

Just how much less work does the enumeration approach require than the iteration approach? Here's a quick snippet to compute the number of derangements and the corresponding Beust number for a given radix:

fac :: Integer -> Integer fac 0 = 1 fac n = n * (fac (n-1)) choose :: Integer -> Integer -> Integer choose n k = (fac n) `div` ((fac k) * (fac (n-k))) d :: Integer -> Integer d 1 = 0 d 2 = 1 d n = (n-1) * ( d (n-1) + d (n-2) ) b :: Integer -> Integer b n = sum [ (d k) * (n `choose` k) | k <- [ 1..n ] ]

Then, `b`

is _{10}`3628799`

, so a
solution like Bob's should have around a 2500-fold advantage over a
more brute force method. And that advantage gets *huge* in
short order. As reminder of how much bigger `n`

is than ^{n}`n!`

and friends, `26`

is
roughly ^{26}`15,264,691,107`

times larger than
`b`

..._{26}