Given a number method checks if its special by recursion

user_13068538 0
Viewed 389

method name:

public static boolean isSpecial (int n)

given a number check if its special this is how special defined:

Start with the natural numbers; at the k-th sieving step, remove every (k+1)-st term of the sequence remaining after the (k-1)-st sieving step; iterate.

1, 3, 7, 13, 19, 27, 39, 49, 63, 79, 91, 109, 133, 147, 181, 207, 223, 253, 289, 307, 349, 387, 399, 459, 481, 529, 567, 613, 649, 709, 763, 807, 843, 927, 949, 1009, 1093, 1111, 1189, 1261, 1321, 1359, 1471, 1483, 1579, 1693, 1719, 1807, 1899, 1933, 2023

this is needs to be done by recursion this what i did:

public static boolean isSpecial (int n) {
 
 if((n % 5 != 0) && (n % 2 != 0))
return true;
return(isSpecial(n-1));
    
}

i dont know how to do it by recursion,from what ive read the number is never divisible by 2 or 5,so should i check if every previous number is not divided 2 and 5?

recursion java
1 Answers

We are removing numbers from the list based only on their positions, and completely ignore their values. It just happens to be so that on the first step a number on position n has value n. So, it's useful to think only about the position of a number in the list, and not its actual value.

Ok, assume that we have made k - 1 steps of a sieving process and now we want to determine if a number which is currently located at position n will be removed from the list on the next, k'th step. On the k'th step we'll remove from the list all numbers, whose positions are multiples of (k + 1). Obviously there are 3 possibilities here:

  • n < k + 1.
    In this case the number will survive, and also it's obvious that it will survive all future steps of the removing process, because from now on we'll be removing from the list only numbers at positions larger than n. So, in this case we are sure that number n is special.

  • n is some multiple of k + 1.
    In this case the number will be removed from the list on the current step, so it's not special.

  • Otherwise the number n is larger than k + 1, but is not a multiple of k + 1.
    Then the number will survive on the current step. However, we'll scratch from the list n/(k + 1) numbers in front of it. We need to round the result of the division down. For example, if n=7, and k=2, we remove every 3rd number from the list. Then 7/3 = 2 numbers (at positions 3 and 6) will be removed in front of our number at position 7. So, in this case the position of our number in the list shifts down by n/(k + 1) and we move to the next iteration.

This algorithm can be expressed with a help of an additional method which takes two parameters - the step k, and the current position of a number in the list:

public static boolean isSpecial(int n)
{
    return isSpecialOnStep(1, n);
}

private static boolean isSpecialOnStep(int k, int n) 
{
    if (k + 1 > n)
        return true;
    if (n % (k + 1) == 0)
        return false;
    return isSpecialOnStep(k + 1, n - n / (k + 1));
}
user_129521130
Related