Search on the blog

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 Set

beattySequence :: Double -> Set.Set Int
beattySequence x = foldr Set.insert Set.empty . map (floor . (*x)) $ [1..100]

main = do
let phi = (1+sqrt(5)) / 2

a = beattySequence phi
b = beattySequence $ phi^2

print $ Set.union a b
print $ Set.intersection a b
From these two sequence, integer set can be generated mutually exclusive and collectively exhaustive.

0 件のコメント:

コメントを投稿