6.10.05
a number sequence
one of three integer sequences i have come across this summer:
1, 3, 7, 13, 19, 27, 39, 49..
These are the numbers generated by Flavius Josephus's sieve.
Sloane's A000960
Start with the integers
1, 2, 3, 4, 5, 6, 7,.. etc.
Cross out every 2nd number, ie the even numbers, leaving the odd numbers
1, 3, 5, 7, 9, 11, 13...
Go through these from the start and cross out every 3rd number, leaving
1, 3, 7, 9, 13...
Then cross out every 4th number, then every 5th number remaining after the 4th stage, and so on.
The numbers you have left form the sequence.
You will have some left; if you look at the last line of numbers above, 1, 3 and 7 will never be crossed out. They are the first 3 numbers, and we're only going to cross out the 4th, 5th, 6th.. numbers at any later stage. If you look at the next stage, 9 will be crossed out and 13 will become the 4th number. Then 13 will stay forever, since only numbers after the 4th one will be crossed out later.
In practice, you can't write out every integer to start with, since there are infinitely many. Nor can you go through infinitely many times, crossing out the nth number for each n: 2 ,3, 4, 5... But this is normal; we can only calculate and write down finitely many numbers from any infinite sequence.
Suppose you want to find all numbers from the sequence less than 1,000. Write out the numbers up to 1,000. Go through them taking out every 2nd number, every 3rd number... Eventually you will be taking out say, the 50th number, but there will be less than fifty numbers left. When this happens you are done. As explained above, the numbers you still have will remain in the final sequence, no matter how many steps you carry on for.
A 'sieve' is a procedure like this one to construct a set of numbers by repeatedly removing certain sets you don't want. The original sieve was Eristophanes' sieve, which generates the prime numbers. I came across this one when i misunderstood a definition of the 'lucky numbers', which are found using a very similar sieving method (Sloane's A000959).
1, 3, 7, 13, 19, 27, 39, 49..
These are the numbers generated by Flavius Josephus's sieve.
Sloane's A000960
Start with the integers
1, 2, 3, 4, 5, 6, 7,.. etc.
Cross out every 2nd number, ie the even numbers, leaving the odd numbers
1, 3, 5, 7, 9, 11, 13...
Go through these from the start and cross out every 3rd number, leaving
1, 3, 7, 9, 13...
Then cross out every 4th number, then every 5th number remaining after the 4th stage, and so on.
The numbers you have left form the sequence.
You will have some left; if you look at the last line of numbers above, 1, 3 and 7 will never be crossed out. They are the first 3 numbers, and we're only going to cross out the 4th, 5th, 6th.. numbers at any later stage. If you look at the next stage, 9 will be crossed out and 13 will become the 4th number. Then 13 will stay forever, since only numbers after the 4th one will be crossed out later.
In practice, you can't write out every integer to start with, since there are infinitely many. Nor can you go through infinitely many times, crossing out the nth number for each n: 2 ,3, 4, 5... But this is normal; we can only calculate and write down finitely many numbers from any infinite sequence.
Suppose you want to find all numbers from the sequence less than 1,000. Write out the numbers up to 1,000. Go through them taking out every 2nd number, every 3rd number... Eventually you will be taking out say, the 50th number, but there will be less than fifty numbers left. When this happens you are done. As explained above, the numbers you still have will remain in the final sequence, no matter how many steps you carry on for.
A 'sieve' is a procedure like this one to construct a set of numbers by repeatedly removing certain sets you don't want. The original sieve was Eristophanes' sieve, which generates the prime numbers. I came across this one when i misunderstood a definition of the 'lucky numbers', which are found using a very similar sieving method (Sloane's A000959).
# posted by weierstrass @ 18:23 
