2
$\begingroup$

I am trying to prove the result for a problem which I am unable to do so! The answer is simply $\frac{N}{2}$ when N is even and $\frac{N}{2}+1$ when $N$ is odd. But I do not see why?? Can you give me a formal proof? And a line of thinking for such problems?

The Sieve of Alice, formally defined by the following procedure, which determines the Sieve of Alice up to a given limit $N$.

  1. Create a list of consecutive integers from $N$ to $2$ $\left(N, N-1, N-2,\cdots, 3, 2\right)$. All of those $N-1$ numbers are initially unmarked.

  2. Initially, let $P = N$, and leave this number unmarked.

  3. Mark all the proper divisors of $P$ (i.e. $P$ remains unmarked).

  4. Find the largest unmarked number from $2$ to $P – 1$, and now let $P$ equal this number.

  5. If there were no more unmarked numbers in the list, stop. Otherwise, repeat from step 3.

Unfortunately, Alice has not found an useful application for it's Sieve. But she still wants to know, for a given limit $N$, how many integers will remain unmarked?

$\endgroup$
3
  • $\begingroup$ You should look for a pattern in the specific numbers that are left unmarked (or marked). $\endgroup$
    – Erick Wong
    Jul 17 '15 at 16:25
  • $\begingroup$ Hint. The best line of thinking is to compute some small examples. Work this out by hand for $N=12$ and $N=15$ and you'll see which half of the numbers remain. That should be a clue for a formal proof. (I'm pretty sure someone will jump in with a full solution before you have time to do this.) $\endgroup$ Jul 17 '15 at 16:26
  • $\begingroup$ Pattern wise what I thought was if N is a prime then I cannot mark any number!! And I have to move to P-1 i.e is a recurrence ! But I couldn't think of any method for composite numbers.. And yeah thanks for the way I will try it always! $\endgroup$ Jul 17 '15 at 16:35
1
$\begingroup$

$a$ is unmarked if and only if $a>\frac{n}{2}$.

Proof: suppose $a$ has a multiple in interval $[2,n]$. consider the largest multiple of $a$ in the interval $[2,n]$, this number must also be unmarked, but if it is unmarked then $P$ took its value at some point in time, when this happened we marked $a$. On the other hand it is clear the numbers larger than $\frac{n}{2}$ where never marked because $P$ never took the value of a multiple of that number.

Therefore there if $n=2k+1$ the $k+1$ numbers $k+1,k+2\dots 2k+1$ are unmarked and if $n=2k$ the $k$ numbers $k+1,k+2\dots 2k$. So $\lceil \frac{n}{2} \rceil$

$\endgroup$
1
  • 3
    $\begingroup$ Someone with a smiling cat avatar answered a question about the Sieve of Alice? Curiouser and curiouser ... $\endgroup$
    – Blue
    Jul 17 '15 at 16:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.