(Serendipity) A positive integer is said to be serendipitous if it survives the follow- ing ordeal: Step 1: S1 = Z+ Step 2: Remove every 2nd number from S1, and call this set S2. Step 3: Remove every 3rd number from S2, and call this set S3, ... ... Step i: Remove every ith number from Si-1, and call this set Si, .... .... Say that S is the set of positive integers that remain after the ordeal is over. Then S is the set of all serendipitious numbers; in fact, S = {1, 3, 7, 13, 19, .....}.

Your mission, should you choose to accept it, is to nd all serendipitous numbers smaller than n. Consider the following two (ideas for) algorithms.

A1: Use a boolean array of length n and make repeated passes over the array, removing numbers until it completes a pass without any removals.

A2: Maintain a linked list of numbers still thought to be serendipitious; at each pass shrink the list as needed, halting when a pass is completed with no removals. Analyze the runtime of A1 and A2. Suggestion: first write pseudocode (in English and readable by a human) for each algorithm.

I saw a solution, but I don't know how it works and how to calculate the runtime. Can anybody help me? Thanks!

A1 /l Use a boolean array of n elements to represent list of numbers. // b is an array b[1], b[2. , b[n], where each b[2] 2 true, false for 1