Get the Lucky Number

Question

A lucky number is a number of a sequence generated by a sieve algorithm: if a number in the positive integers series survives to the sieve filtering algorithm, it's lucky and survives, otherwise it disappears from the sequence.

First you must obtain an array of numbers, from 1 to the needed size. First number is 1 and it survives: next to him there is number 2, that becomes the sieve's filter: every second number in the list (counting from 1) has to be filtered (as to say every even number). After this step, the next number to survive after 1 is 3: eliminate every third number in the list (counting from 1). After this step, the next number to survive after 3 is 7: eliminate every seventh number in the list. Repeat the steps incrementing the filter condition at every step (as to say that the sieve filter of a new step is equal to the first number greater than the previous step last lucky number) until there are no numbers to eliminate in the list. See the example below for a given size = 25 and nth = 5.

Step 1: Generate a list from 1 to size.

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25

Step 2: First sieve filter is 2: every second number from the start has to be eliminated.

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25

Step 3: Sieve filter is now 3: every third number from the start has to be eliminated.

1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25 Step 4: Sieve filter is now 7: every seventh number from the start has to be eliminated.

1, 3, 7, 9, 13, 15, 19, 21, 25

Step 5: Sieve filter is now 9: every ninth number has to be eliminated, but our list now contains only 8 numbers and so the algorithm ends. The nth number of the sequence is 13.

In the animation below, you can see the progressive sieving process for a list of 120 numbers: purple filling is for eliminated numbers, red is for lucky ones.

Here is my solution, (which doesn't work), I cannot seem to get every nth number in the array...

Yes I know my code returns 1, I'm just printing stuff at the moment, to try and debug what is wrong with my code.

public static List<Integer> generateLucky(int[] A, int steps)
    {
        List<Integer> lst = new ArrayList<>();
        for(int i = 0; i < A.length; i++)
        {
            if(i % steps == 0)
            {
                lst.add(A[i]);
            }
        }
        return lst;
    }
    public static int getLuckyNumber(int size, int nth) 
    {
        List<Integer> nums = new ArrayList<>();
        for(int i = 1; i <= size; i++)
        {
            nums.add(i);
        }
        int steps = 1;
        int[] A = nums.stream().mapToInt(j->j).toArray();
        for(int i = 0; i < A.length; i++)
        {
            List<Integer> lst = generateLucky(Arrays.copyOfRange(A, 0, A.length), steps);
            System.out.println(lst);
            A = lst.stream().mapToInt(j->j).toArray();
            steps = A[1];

        }
        return 1;
    }

Answer 1

First run, before debugging:

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25]
[1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25]
[1, 7, 13, 19, 25] <-- doesn't look good. It's suppose to retain [1, 3, 7, 9, 13,.. 
[1]
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index 1 out of bounds for length 1

I removed the line that caused the error: steps = A[1];.
Then added:

• int stepindex = 1;
• logic to handle stepping. Seems that part was missing.
  • make sure that the stepindex is smaller than the total length of the array.
  • also check the current value in the array (of stepindex) to see if it's smaller or the same as the previous steps. If it is, increase the stepindex (by one) and redo the checks.
  • if the new steps is greater than the length of the array, there's nothing more to remove, so break.
• changed the statement that decides what numbers to keep

I didn't change the code to only use arrays or lists, as I tried to keep it as close to your original code.

Now it prints:

steps = 2
stepindex = 1
A = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25]
steps = 3
stepindex = 1
A = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25]
steps = 7
stepindex = 2
A = [1, 3, 7, 9, 13, 15, 19, 21, 25]
steps = 9
stepindex = 3
A = [1, 3, 7, 9, 13, 15, 21, 25]
  getLuckyNumber(25,5): nth = 13
------------
steps = 2
stepindex = 1
A = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25]
steps = 3
stepindex = 1
A = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25]
steps = 7
stepindex = 2
A = [1, 3, 7, 9, 13, 15, 19, 21, 25]
steps = 9
stepindex = 3
A = [1, 3, 7, 9, 13, 15, 21, 25]
  getLuckyNumber(25,5000): nth = -2147483648

Your modified code:

import java.util.List;
import java.util.ArrayList;
import java.util.Arrays;

public class StackOverflowTest {
  public static void main(String[] args){
    System.out.println("  getLuckyNumber(25,5): nth = " + getLuckyNumber(25,5));
    System.out.println("------------");
    System.out.println("  getLuckyNumber(25,5000): nth = " + getLuckyNumber(25,5000));
  }

  public static List<Integer> generateLucky(int[] A, int steps) {
    List<Integer> lst = new ArrayList<>();
    System.out.println("A = " + Arrays.toString(A));   // debug statement
    for (int i = 0; i < A.length; i++) {
//        if (i % steps == 0) { // not working.. it's only adding the numbers that should be removed
        // decide what numbers to keep
        if ((i+1) % steps != 0) { // arrays are zero-indexed
//            System.out.println("A[" + i + "] = " + A[i]); // intermediate debug statement
            lst.add(A[i]);
        }
    }
    return lst;
  }

  public static int getLuckyNumber(int size, int nth) {
    List<Integer> nums = new ArrayList<>();
    for (int i = 1; i <= size; i++) {
        nums.add(i);
    }

    int steps = 1;
    int stepindex = 1;
    int[] A = nums.stream().mapToInt(j->j).toArray();
    for(int i = 0; i < A.length; i++) {

      // logic to handle stepping:
      while (stepindex < (A.length - 1) && A[stepindex] <= steps) {stepindex++;}
      steps = A[stepindex];
      System.out.println("steps = " + steps);         // debug statement
      System.out.println("stepindex = " + stepindex); // debug statement
      if (steps >= (A.length)) {break;}

      List<Integer> lst = generateLucky(Arrays.copyOfRange(A, 0, A.length), steps);
//      System.out.println(lst);
      A = lst.stream().mapToInt(j->j).toArray();
//      steps = A[1]; // this is the source of the Runtime Error.. 
    }
    System.out.println("A = " + Arrays.toString(A));   // debug statement

    if (nth < A.length) {
      return A[nth-1];
    } else {
      return Integer.MIN_VALUE; // just something to return if nth is too big
    }
  }
}

Answer 2

I'm answering this question in order to explain my reasoning process.

Here's the output from a test run of the code I wrote.

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25
listFilter: 2
1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25
listFilter: 3
1, 3, 7, 9, 13, 15, 19, 21, 25
listFilter: 7
1, 3, 7, 9, 13, 15, 21, 25
13

The input to this test run was the size of 25 and the nth of 5.

When I wrote the code, I wrote it in steps. I checked each step to make sure the output was what I expected.

First, I generated the initial List. That worked fine.

Next, I generated the first filtered List, the one filtered by 2. I didn't code anything else until the first filtered list printed out correctly.

Next, I generated the second filtered List, the one filtered by 3. Again, I didn't code anything else until the second filtered list printed out correctly.

Next, I generated the third filtered List, the one filtered by 7.

At this point, I had enough code and experience to see how I could generalize the method I called proceessSieve.

Finally, printing intermediate outputs helps you to debug the code you've just written. Every other statement in your code should be System.out.print or println.

Here's the code I wrote. I don't think giving you the code is going to help you learn in the long run. Note the debugging statements embedded in the code.

import java.util.ArrayList;
import java.util.List;

public class LuckyNumber {

    public static void main(String[] args) {
        LuckyNumber luckyNumber = new LuckyNumber();
        System.out.println(luckyNumber.getLuckyNumber(25, 5));
    }

    private static boolean DEBUG = true;

    public int getLuckyNumber(int size, int index) {
        List<Integer> numberList = createOriginalList(size);
        if (DEBUG) { 
            printList(numberList);
        }
        numberList = processSieve(numberList);
        return numberList.get(index - 1);
    }

    private List<Integer> createOriginalList(int size) {
        List<Integer> numberList = new ArrayList<>(size);
        for (int i = 0; i < size; i++) {
            numberList.add(i + 1);
        }
        return numberList;
    }

    private List<Integer> processSieve(List<Integer> numberList) {
        int listIndex = 1;
        int count = 0;
        int listFilter = numberList.get(listIndex);
        while (listFilter <= numberList.size()) {
            if (DEBUG) {
                System.out.println("listFilter: " + listFilter);
            }
            numberList = filterList(numberList, listFilter);
            if (DEBUG) {
                printList(numberList);
            }
            if (count > 0) {
                listIndex++;
            }
            count++;
            listFilter = numberList.get(listIndex);
        }
        return numberList;
    }

    private List<Integer> filterList(List<Integer> list, int listFilter) {
        List<Integer> filterList = new ArrayList<>();
        for (int i = 0; i < list.size(); i++) {
            if ((i + 1) % listFilter == 0) {
                continue;
            } else {
                filterList.add(list.get(i));
            }
        }
        return filterList;
    }

    private void printList(List<Integer> list) {
        for(int i = 0; i < list.size(); i++) {
            System.out.print(list.get(i));
            if (i < (list.size() - 1)) {
                System.out.print(", ");
            }
        }
        System.out.println();
    }

}