Series with largest GCD and sum equals to n

Last Updated : 12 Feb, 2025

Given an integer n, print m increasing numbers such that the sum of m numbers is equal to n and the GCD of m numbers is maximum among all series possible. If no series is possible then print “-1”.

Examples :

Input : n = 24, m = 3
Output : 4 8 12
Explanation : (4, 8, 12) has gcd = 4 which is the maximum possible with given constraints. Note that (3, 6, 15) is not an answer, although it is a series of m numbers which sum equals to n, but gcd = 3.

Input : n = 6, m = 4
Output : -1
Explanation: It is not possible as the least GCD sequence will be 1+2+3+4 which is greater than n, hence print -1.

The most common observation is that the GCD of the series will always be a divisor of n. The maximum gcd possible (say b) will be n/sum, where sum is the sum of 1+2+..m.
If b turns out to be 0, then the sum of 1+2+3..+k exceeds n which is invalid, hence output “-1”.
Traverse to find out all the divisors possible, a loop till sqrt(n). If the current divisor is i, the best possible way to take the series will be to consider i, 2*i, 3*i, …(m-1)*i, and their sum is s which is equal to i * (m*(m-1))/2 . The last number will be n-s. Along with i being the divisor, n/i will be the other divisor so check for that also.
Take maximum of possible divisor possible (say r) which should be less than or equals to b and print the sequence as r, 2*r, … (m-1)*r, n—s.
If no such divisors are found simply output “-1”.

C++

// CPP program to find the series with largest
// GCD and sum equals to n
#include <bits/stdc++.h>
using namespace std;

// function to generate and print the sequence
void print_sequence(int n, int k)
{
    // stores the maximum gcd that can be
    // possible of sequence.
    int b = n / (k * (k + 1) / 2);

    // if maximum gcd comes out to be
    // zero then not possible
    if (b == 0) {
        cout << -1 << endl;

    } else {

        // the smallest gcd possible is 1
        int r = 1;

        // traverse the array to find out 
        // the max gcd possible
        for (int x = 1; x * x <= n; x++) {

            // checks if the number is 
            // divisible or not
            if (n % x != 0)
                continue;

            // checks if x is smaller than 
            // the max gcd possible and x 
            // is greater than the resultant 
            // gcd till now, then r=x
            if (x <= b && x > r)
                r = x;

            // checks if n/x is smaller than 
            // the max gcd possible and n/x 
            // is greater than the resultant 
            // gcd till now, then r=x
            if (n / x <= b && n / x > r)
                r = n / x;
        }

        // traverses and prints d, 2d, 3d,
        // ..., (k-1)·d,
        for (int i = 1; i < k; i++)
            cout << r * i << " ";

        // computes the last element of
        // the sequence n-s.
        int res = n - (r * (k * (k - 1) / 2));

        // prints the last element
        cout << res << endl;
    }
}

// driver program to test the above function
int main()
{
    int n = 24;
    int k = 4;
    print_sequence(n, k);

    n = 24, k = 5;
    print_sequence(n, k);

    n = 6, k = 4;
    print_sequence(n, k);
}

Java

// Java program to find the series with 
// largest GCD and sum equals to n
import java.io.*;

class GFG {

// function to generate and print the sequence
static void print_sequence(int n, int k)
{
    // stores the maximum gcd that can be
    // possible of sequence.
    int b = n / (k * (k + 1) / 2);

    // if maximum gcd comes out to be
    // zero then not possible
    if (b == 0) {
        System.out.println("-1");

    } else {

        // the smallest gcd possible is 1
        int r = 1;

        // traverse the array to find out 
        // the max gcd possible
        for (int x = 1; x * x <= n; x++) {

            // checks if the number is 
            // divisible or not
            if (n % x != 0)
                continue;

            // checks if x is smaller than 
            // the max gcd possible and x 
            // is greater than the resultant 
            // gcd till now, then r=x
            if (x <= b && x > r)
                r = x;

            // checks if n/x is smaller than 
            // the max gcd possible and n/x 
            // is greater than the resultant 
            // gcd till now, then r=x
            if (n / x <= b && n / x > r)
                r = n / x;
        }

        // traverses and prints d, 2d, 3d,..., (k-1)
        for (int i = 1; i < k; i++)
            System.out.print(r * i + " ");

        // computes the last element of
        // the sequence n-s.
        int res = n - (r * (k * (k - 1) / 2));

        // prints the last element
        System.out.println(res);
    }
}

// driver program to test the above function
public static void main(String[] args)
{
    int n = 24;
    int k = 4;
    print_sequence(n, k);

    n = 24; k = 5;
    print_sequence(n, k);

    n = 6; k = 4;
    print_sequence(n, k);
}
}

// This code is contributed by Prerna Saini

Python

# Python3 code to find the series 
# with largest GCD and sum equals to n

def print_sequence(n, k):
    
    # stores the maximum gcd that
    # can be possible of sequence.
    
    b = int(n / (k * (k + 1) / 2));
    

    # if maximum gcd comes out to be
    # zero then not possible
    
    if b == 0:
        print ("-1")

    else:
        # the smallest gcd possible is 1
        r = 1;

        # traverse the array to find out 
        # the max gcd possible
        x = 1
        
        while x ** 2 <= n:
            
            # checks if the number is 
            # divisible or not
            if n % x != 0:
            
                # x = x + 1
                continue;
                
            
            # checks if x is smaller than 
            # the max gcd possible and x 
            # is greater than the resultant 
            # gcd till now, then r=x
            elif x <= b and x > r:
                r = x
                # x = x + 1

            # checks if n/x is smaller than 
            # the max gcd possible and n/x 
            # is greater than the resultant 
            # gcd till now, then r=x
            elif n / x <= b and n / x > r :
                r = n / x
                # x = x + 1
                
            x = x + 1
        

    # traverses and prints d, 2d, 3d,
    # ..., (k-1)·d,
        i = 1
        while i < k :
            print (r * i, end = " ")
            i = i + 1
            
        last_term = n - (r * (k * (k - 1) / 2))
        print (last_term)
        
        
            
        
# main driver
print_sequence(24,4) 
print_sequence(24,5)
print_sequence(6,4)

# This code is contributed by Saloni Gupta

// C# program to find the series with 
// largest GCD and sum equals to n
using System;

class GFG {

// function to generate and
// print the sequence
static void print_sequence(int n, int k)
{
    
    // stores the maximum gcd that can be
    // possible of sequence.
    int b = n / (k * (k + 1) / 2);

    // if maximum gcd comes out to be
    // zero then not possible
    if (b == 0)
    {
        Console.Write("-1");

    }
    else 
    {

        // the smallest gcd possible is 1
        int r = 1;

        // traverse the array to find out 
        // the max gcd possible
        for (int x = 1; x * x <= n; x++)
        {

            // checks if the number is 
            // divisible or not
            if (n % x != 0)
                continue;

            // checks if x is smaller than 
            // the max gcd possible and x 
            // is greater than the resultant 
            // gcd till now, then r=x
            if (x <= b && x > r)
                r = x;

            // checks if n/x is smaller than 
            // the max gcd possible and n/x 
            // is greater than the resultant 
            // gcd till now, then r=x
            if (n / x <= b && n / x > r)
                r = n / x;
        }

        // traverses and prints d, 2d,
        // 3d,..., (k-1)
        for (int i = 1; i < k; i++)
        Console.Write(r * i + " ");

        // computes the last element of
        // the sequence n-s.
        int res = n - (r * (k * 
                  (k - 1) / 2));

        // prints the last element
        Console.WriteLine(res);
    }
}

// Driver Code
public static void Main()
{
    int n = 24;
    int k = 4;
    print_sequence(n, k);

    n = 24; k = 5;
    print_sequence(n, k);

    n = 6; k = 4;
    print_sequence(n, k);
}
}

// This code is contributed by Nitin Mittal.

JavaScript

<script>

// Javascript program to find the 
// series with largest GCD 
// and sum equals to n

// function to generate and
// print the sequence
function print_sequence(n, k)
{
    // stores the maximum gcd that 
    // can be possible of sequence.
    let b = parseInt(n / (k * (k + 1) / 2));

    // if maximum gcd comes out to be
    // zero then not possible
    if (b == 0) 
    {
        document.write(-1);
    } 
    else 
    {

        // the smallest gcd possible is 1
        let r = 1;

        // traverse the array to find out 
        // the max gcd possible
        for (let x = 1; x * x <= n; x++) 
        {

            // checks if the number is 
            // divisible or not
            if (n % x != 0)
                continue;

            // checks if x is smaller than 
            // the max gcd possible and x 
            // is greater than the resultant 
            // gcd till now, then r=x
            if (x <= b && x > r)
                r = x;

            // checks if n/x is smaller than 
            // the max gcd possible and n/x 
            // is greater than the resultant 
            // gcd till now, then r=x
            if (n / x <= b && n / x > r)
                r = n / x;
        }

        // traverses and prints d, 2d, 3d,
        // ..., (k-1)·d,
        for (let i = 1; i < k; i++)
            document.write(r * i + " ");

        // computes the last element of
        // the sequence n-s.
        let res = n - (r * (k * (k - 1) / 2));

        // prints the last element
        document.write(res + "<br>");
    }
}

// Driver Code
let n = 24;
let k = 4;
print_sequence(n, k);

n = 24; 
k = 5;
print_sequence(n, k);

n = 6; 
k = 4;
print_sequence(n, k);

// This code is contributed by _saurabh_jaiswal.

</script>

PHP

<?php
// PHP program to find the 
// series with largest GCD 
// and sum equals to n

// function to generate and
// print the sequence
function print_sequence($n, $k)
{
    // stores the maximum gcd that 
    // can be possible of sequence.
    $b = (int)($n / ($k * ($k + 1) / 2));

    // if maximum gcd comes out to be
    // zero then not possible
    if ($b == 0) 
    {
        echo(-1);
    } 
    else 
    {

        // the smallest gcd possible is 1
        $r = 1;

        // traverse the array to find out 
        // the max gcd possible
        for ($x = 1; $x * $x <= $n; $x++) 
        {

            // checks if the number is 
            // divisible or not
            if ($n % $x != 0)
                continue;

            // checks if x is smaller than 
            // the max gcd possible and x 
            // is greater than the resultant 
            // gcd till now, then r=x
            if ($x <= $b && $x > $r)
                $r = $x;

            // checks if n/x is smaller than 
            // the max gcd possible and n/x 
            // is greater than the resultant 
            // gcd till now, then r=x
            if ($n / $x <= $b && $n / $x > $r)
                $r = $n / $x;
        }

        // traverses and prints d, 2d, 3d,
        // ..., (k-1)·d,
        for ($i = 1; $i < $k; $i++)
            echo($r * $i . " ");

        // computes the last element of
        // the sequence n-s.
        $res = $n - ($r * ($k * ($k - 1) / 2));

        // prints the last element
        echo($res . "\n");
    }
}

// Driver Code
$n = 24;
$k = 4;
print_sequence($n, $k);

$n = 24; $k = 5;
print_sequence($n, $k);

$n = 6; $k = 4;
print_sequence($n, $k);

// This code is contributed by Ajit.
?>

Output :

2 4 6 12
1 2 3 4 14
-1

Time complexity: O( sqrt (n) )
Auxiliary Space: O(1)

Program to find GCD of floating point numbers

GeeksforGeeks

Improve

Article Tags :

Practice Tags :

Series with largest GCD and sum equals to n

Similar Reads

Problems on GCD

Thank You!

What kind of Experience do you want to share?