Problem 61146. Extract numbers using a decaying sieve

The Sieve of Eratosthenes is one method of determining primes. Starting with 2, one keeps 2 and removes 2x2, 3x2, 4x2, etc. Then the next remaining number is 3, and one keeps 3 and removes 2x3 (already removed), 3x3, 4x3 (already removed), etc. The sieving continues with multiples of 5, 7, 11, etc.
This problem involves a decaying sieve. In the Sieve of Eratosthenes, the gaps between the sieved numbers is constant at each step: if the next remaining number is 5 (say), then the gap is 5 as well, and the numbers removed are 10, 15, 20, 25, etc. In the decaying sieve, the gap decreases by 1 between numbers: if the next remaining number is 4, then the gaps are 3, 2, 1 so that the numbers removed are 7, 9, and 10. Notice that the decaying sieve removes a finite number of elements.
The sieve starts like this:
  1. The first remaining number is 1. Keep 1. Because 1-1 = 0, no numbers are removed.
  2. The next remaining number is 2. Keep 2 and remove 2+1 = 3.
  3. The next remaining number is 4. Keep 4 and remove 4+3 = 7, 4+3+2 = 9, and 4+3+2+1 = 10.
  4. Et cetera
Write a function to apply the decaying sieve to numbers from 1 to the input number.
Solve

Solution Stats

100.0% Correct | 0.0% Incorrect
Last Solution submitted on Jan 03, 2026

Solution Comments

Show comments

Problem Recent Solvers2

Suggested Problems

More from this Author318

Problem Tags

sequence sieve

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!