Find the number of integers x in range (1,N) for which x and x+1 have same number of divisors

0 0 10 minutes read

Given an integer N. The task is to find the number of integers 1 < x < N, for which x and x + 1 have the same number of positive divisors.

Examples:

Input: N = 3
Output: 1
Divisors(1) = 1
Divisors(2) = 1 and 2
Divisors(3) = 1 and 3
Only valid x is 2.

Input: N = 15
Output: 2

Approach: Find the number of divisors of all numbers below N and store them in an array. And count the number of integers x such that x and x + 1 have the same number of positive divisors by running a loop.

Below is the implementation of the above approach:

C++

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
#define N 100005
 
// To store number of divisors and
// Prefix sum of such numbers
int d[N], pre[N];
 
// Function to find the number of integers
// 1 < x < N for which x and x + 1 have
// the same number of positive divisors
void Positive_Divisors()
{
    // Count the number of divisors
    for (int i = 1; i < N; i++) {
 
        // Run a loop upto sqrt(i)
        for (int j = 1; j * j <= i; j++) {
 
            // If j is divisor of i
            if (i % j == 0) {
 
                // If it is perfect square
                if (j * j == i)
                    d[i]++;
                else
                    d[i] += 2;
            }
        }
    }
 
    int ans = 0;
 
    // x and x+1 have same number of
    // positive divisors
    for (int i = 2; i < N; i++) {
        if (d[i] == d[i - 1])
            ans++;
        pre[i] = ans;
    }
}
 
// Driver code
int main()
{
    // Function call
    Positive_Divisors();
 
    int n = 15;
 
    // Required answer
    cout << pre[n] << endl;
 
    return 0;
}

Java

// Java implementation of the approach
class GFG
{
     
static int N =100005;
 
// To store number of divisors and
// Prefix sum of such numbers
static int d[] = new int[N], pre[] = new int[N];
 
// Function to find the number of integers
// 1 < x < N for which x and x + 1 have
// the same number of positive divisors
static void Positive_Divisors()
{
    // Count the number of divisors
    for (int i = 1; i < N; i++)
    {
 
        // Run a loop upto sqrt(i)
        for (int j = 1; j * j <= i; j++) 
        {
 
            // If j is divisor of i
            if (i % j == 0)
            {
 
                // If it is perfect square
                if (j * j == i)
                    d[i]++;
                else
                    d[i] += 2;
            }
        }
    }
 
    int ans = 0;
 
    // x and x+1 have same number of
    // positive divisors
    for (int i = 2; i < N; i++)
    {
        if (d[i] == d[i - 1])
            ans++;
        pre[i] = ans;
    }
}
 
// Driver code
public static void main(String[] args)
{
    // Function call
    Positive_Divisors();
 
    int n = 15;
 
    // Required answer
    System.out.println(pre[n]);
}
}
 
/* This code contributed by PrinciRaj1992 */

Python3

# Python3 implementation of the above approach 
from math import sqrt;
 
N = 100005
 
# To store number of divisors and 
# Prefix sum of such numbers 
d = [0] * N
pre = [0] * N
 
# Function to find the number of integers 
# 1 < x < N for which x and x + 1 have 
# the same number of positive divisors 
def Positive_Divisors() :
     
    # Count the number of divisors 
    for i in range(N) :
 
        # Run a loop upto sqrt(i) 
        for j in range(1, int(sqrt(i)) + 1) :
 
            # If j is divisor of i 
            if (i % j == 0) :
 
                # If it is perfect square 
                if (j * j == i) :
                    d[i] += 1
                else :
                    d[i] += 2
 
    ans = 0
 
    # x and x+1 have same number of 
    # positive divisors 
    for i in range(2, N) : 
        if (d[i] == d[i - 1]) :
            ans += 1
        pre[i] = ans
     
# Driver code 
if __name__ == "__main__" : 
 
    # Function call 
    Positive_Divisors()
 
    n = 15
 
    # Required answer 
    print(pre[n]) 
 
# This code is contributed by Ryuga

C#

// C# implementation of the approach
using System;
 
class GFG
{
     
static int N =100005;
 
// To store number of divisors and
// Prefix sum of such numbers
static int []d = new int[N]; 
static int []pre = new int[N];
 
// Function to find the number of integers
// 1 < x < N for which x and x + 1 have
// the same number of positive divisors
static void Positive_Divisors()
{
    // Count the number of divisors
    for (int i = 1; i < N; i++)
    {
 
        // Run a loop upto sqrt(i)
        for (int j = 1; j * j <= i; j++) 
        {
 
            // If j is divisor of i
            if (i % j == 0)
            {
 
                // If it is perfect square
                if (j * j == i)
                    d[i]++;
                else
                    d[i] += 2;
            }
        }
    }
 
    int ans = 0;
 
    // x and x+1 have same number of
    // positive divisors
    for (int i = 2; i < N; i++)
    {
        if (d[i] == d[i - 1])
            ans++;
        pre[i] = ans;
    }
}
 
// Driver code
public static void Main(String[] args)
{
    // Function call
    Positive_Divisors();
 
    int n = 15;
 
    // Required answer
    Console.WriteLine(pre[n]);
}
}
 
// This code has been contributed by 29AjayKumar

Javascript

<script>
 
// Javascript implementation of the approach
const N = 100005;
 
// To store number of divisors and
// Prefix sum of such numbers
let d = new Array(N).fill(0);
let pre = new Array(N).fill(0);
 
// Function to find the number of integers
// 1 < x < N for which x and x + 1 have
// the same number of positive divisors
function Positive_Divisors()
{
     
    // Count the number of divisors
    for(let i = 1; i < N; i++)
    {
 
        // Run a loop upto sqrt(i)
        for(let j = 1; j * j <= i; j++)
        {
             
            // If j is divisor of i
            if (i % j == 0)
            {
                 
                // If it is perfect square
                if (j * j == i)
                    d[i]++;
                else
                    d[i] += 2;
            }
        }
    }
 
    let ans = 0;
 
    // x and x+1 have same number of
    // positive divisors
    for(let i = 2; i < N; i++)
    {
        if (d[i] == d[i - 1])
            ans++;
             
        pre[i] = ans;
    }
}
 
// Driver code
 
// Function call
Positive_Divisors();
let n = 15;
 
// Required answer
document.write(pre[n]); 
 
// This code is contributed by souravmahato348
 
</script>

PHP

<?php 
 
// PHP implementation of the approach
 
$N = 100005;
 
// To store number of divisors and
// Prefix sum of such numbers
$d = array_fill(0,$N,NULL);
$pre = array_fill(0,$N,NULL);
 
// Function to find the number of integers
// 1 < x < N for which x and x + 1 have
// the same number of positive divisors
function Positive_Divisors()
{
    global $N,$d,$pre;
    // Count the number of divisors
    for ($i = 1; $i < $N; $i++) {
 
        // Run a loop upto sqrt(i)
        for ($j = 1; $j * $j <= $i; $j++) {
 
            // If j is divisor of i
            if ($i % $j == 0) {
 
                // If it is perfect square
                if ($j * $j == $i)
                    $d[$i]++;
                else
                    $d[$i] += 2;
            }
        }
    }
 
    $ans = 0;
 
    // x and x+1 have same number of
    // positive divisors
    for ($i = 2; $i < $N; $i++) {
        if ($d[$i] == $d[$i - 1])
            $ans++;
        $pre[$i] = $ans;
    }
}
 
// Driver code
 
    // Function call
    Positive_Divisors();
 
    $n = 15;
 
    // Required answer
    echo $pre[$n] ;
 
    return 0;
     
// This code is contributed by ChitraNayal
?>

Output

Time complexity: O(N^3/2)

Auxiliary Space: O(N)

Approach 2:

One approach to finding the number of integers 1 < x < N for which x and x + 1 have the same number of positive divisors is to use a prime factorization method. This involves finding the prime factors of each number and using the formula for the number of divisors of a number based on its prime factorization.

Here is the step-by-step algorithm for implementing the approach:

Define a function Positive_Divisors() to calculate the number of positive divisors for each integer in the range [2, N).
In the function Positive_Divisors(), initialize an array d of size N to store the number of divisors for each integer in the range [2, N).
Iterate over each integer i in the range [2, N) using a loop.
For each integer i, calculate its prime factorization and compute the number of divisors using the formula for the number of divisors of a positive integer. Store the result in d[i].
Initialize a variable ans to 0 to store the final answer.
Iterate over each integer i in the range [2, N) using another loop.
For each integer i, check if d[i] == d[i – 1], If this condition is true, then increment ans by 1.
Initialize an array pre of size N to store the prefix sum of the answer.
For each integer i in the range [2, N), set pre[i] = ans.
In the main() function, call the function Positive_Divisors().
Print the value of pre[n], where n is a given integer.

C++

#include <bits/stdc++.h>
using namespace std;
#define N 100005
 
// To store number of divisors and
// Prefix sum of such numbers
int d[N], pre[N];
 
// Function to find the number of integers
// 1 < x < N for which x and x + 1 have
// the same number of positive divisors
void Positive_Divisors()
{
    // Count the number of divisors
    for (int i = 2; i < N; i++) {
        int num = i;
        int divisors = 1;
        for (int j = 2; j * j <= num; j++) {
            int count = 0;
            while (num % j == 0) {
                count++;
                num /= j;
            }
            divisors *= (count + 1);
        }
        if (num > 1)
            divisors *= 2;
        d[i] = divisors;
    }
 
    int ans = 0;
 
    // x and x+1 have same number of
    // positive divisors
    for (int i = 2; i < N; i++) {
        if (d[i] == d[i - 1])
            ans++;
        pre[i] = ans;
    }
}
 
// Driver code
int main()
{
    // Function call
    Positive_Divisors();
 
    int n = 15;
 
    // Required answer
    cout << pre[n] << endl;
 
    return 0;
}

Java

/*package whatever //do not write package name here */
 
import java.util.Arrays;
 
public class GFG {
    static final int N = 100005;
    // To store number of divisors and
    // Prefix sum of such numbers
    static int[] d = new int[N];
    static int[] pre = new int[N];
 
    // Function to find the number of integers
    // 1 < x < N for which x and x + 1 have
    // the same number of positive divisors
    static void Positive_Divisors()
    {
        // Count the number of divisors
        for (int i = 2; i < N; i++) {
            int num = i;
            int divisors = 1;
            for (int j = 2; j * j <= num; j++) {
                int count = 0;
                while (num % j == 0) {
                    count++;
                    num /= j;
                }
                divisors *= (count + 1);
            }
            if (num > 1)
                divisors *= 2;
            d[i] = divisors;
        }
 
        int ans = 0;
 
        // x and x+1 have same number of
        // positive divisors
        for (int i = 2; i < N; i++) {
            if (d[i] == d[i - 1])
                ans++;
            pre[i] = ans;
        }
    }
 
    // Driver code
    public static void main(String[] args)
    {
        // Function call
        Positive_Divisors();
 
        int n = 15;
 
        // Required answer
        System.out.println(pre[n]);
    }
}
//This code is contributed by aeroabrar_31

Python3

N = 100005
 
# To store number of divisors and
# Prefix sum of such numbers
d = [0] * N
pre = [0] * N
 
# Function to find the number of integers
# 1 < x < N for which x and x + 1 have
# the same number of positive divisors
def Positive_Divisors():
    global N, d, pre
     
    # Count the number of divisors
    for i in range(2, N):
        num = i
        divisors = 1
        j = 2
        while j * j <= num:
            count = 0
            while num % j == 0:
                count += 1
                num //= j
            divisors *= (count + 1)
            j += 1
        if num > 1:
            divisors *= 2
        d[i] = divisors
 
    ans = 0
 
    # x and x+1 have same number of
    # positive divisors
    for i in range(2, N):
        if d[i] == d[i - 1]:
            ans += 1
        pre[i] = ans
 
# Driver code
Positive_Divisors()
 
n = 15
 
# Required answer
print(pre[n])
 
#aeroabrar_31

C#

using System;
 
public class GFG
{
    const int N = 100005;
    // To store the number of divisors and
    // Prefix sum of such numbers
    static int[] d = new int[N];
    static int[] pre = new int[N];
 
    // Function to find the number of integers
    // 1 < x < N for which x and x + 1 have
    // the same number of positive divisors
    static void PositiveDivisors()
    {
        // Count the number of divisors
        for (int i = 2; i < N; i++)
        {
            int num = i;
            int divisors = 1;
            for (int j = 2; j * j <= num; j++)
            {
                int count = 0;
                while (num % j == 0)
                {
                    count++;
                    num /= j;
                }
                divisors *= (count + 1);
            }
            if (num > 1)
                divisors *= 2;
            d[i] = divisors;
        }
 
        int ans = 0;
 
        // x and x+1 have the same number of
        // positive divisors
        for (int i = 2; i < N; i++)
        {
            if (d[i] == d[i - 1])
                ans++;
            pre[i] = ans;
        }
    }
 
    // Driver code
    public static void Main(string[] args)
    {
        // Function call
        PositiveDivisors();
 
        int n = 15;
 
        // Required answer
        Console.WriteLine(pre[n]);
    }
}

Output

Time Complexity: O(N log N)
Auxiliary Space: O(N)

Explaination :
The time complexity of this code is O(N log N) because calculating the prime factorization of each integer in the range [2, N) takes O(log N) time and this operation is performed for each integer in the range [2, N).

The auxiliary space complexity is O(N) because two arrays of size N are used.

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!