4

If a sequence is generated like so:

  1. start with the odd numbers
    $1,3,5,7,...$
  2. start at $n=1$
  3. take the next number $n$ from the sequence. So at the start of the first pass:
    sequence is $1,3,5,7,...$ and $n = 3$
  4. remove every $n\mathrm{th}$ number from the list.
  5. repeat from 3.

so the sequence would look like this after each of the first few passes:

$1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, ...$

$1, 3, 7, 9, 13, 15, 19, 21, 25, 27, 31, ...$

$1, 3, 7, 9, 13, 15, 21, 25, 27, 31, ...$

$1, 3, 7, 9, 13, 15, 21, 25, 31, ...$

The final sequence would be the sequence created after this process is gone through infinitely many times.

How could I define a relationship to get the $n\mathrm{th}$ term of the sequence, e.g.

$u_n =\ ...$

minseong
  • 1,293

1 Answers1

5

These are called the lucky numbers. The only difference between your algorithm and wikipedia's is that wikipedia starts with all numbers, removes the even ones (because the first $n = 2$), and then they get to exactly where you start.

You can also look them up on the OEIS. As for a formula, I don't think there's a good one. The elimination process seems to be way too erratic and unpredictable in the long run. Also, since the process is so close to the sieve of Eratosthenes, a concrete formula (and proof thereof) might also give general insight into the primes, and we know that that is difficult (see the Riemann hypothesis and the twin primes conjecture, for instance).

Arthur
  • 199,419