## 2011年5月24日火曜日

### Beatty sequence making full integer set

Here's the definition of Beatty sequence:

[a], [2*a], [3*a], [4*a],....

where a is an irrational number, and [] is a floor function, which returns the maximum integer less than its input value.
As you can guess, there are tons of types of Beatty sequence out there.

What tickled my fancy was that the following theorem holds:

Two Beatty sequences
[a], [2*a], [3*a], .....
[b], [2*b], [3*b], ....
makes the whole integer set without any overlaps if 1/a + 1/b = 1.
It's like separating numbers into odd and even.

So, of course, you can select these two sequence so that the condition below is met:
1/a + 1/(a^2) = 1.

What do you associate with the preceding equation?? Yes, it's the "golden ratio."
I tried this out today. And it seemed to act like what I expected.
`import qualified Data.Set as SetbeattySequence :: Double -> Set.Set IntbeattySequence x = foldr Set.insert Set.empty . map (floor . (*x)) \$ [1..100]main = dolet phi = (1+sqrt(5)) / 2  a = beattySequence phi  b = beattySequence \$ phi^2print \$ Set.union a bprint \$ Set.intersection a b`
From these two sequence, integer set can be generated mutually exclusive and collectively exhaustive.