lcm_sum.cpp File Reference

An algorithm to calculate the sum of LCM: \(\mathrm{LCM}(1,n) + \mathrm{LCM}(2,n) + \ldots + \mathrm{LCM}(n,n)\). More...

#include <cassert>
#include <cstdint>
#include <iostream>
#include <vector>

Include dependency graph for lcm_sum.cpp:

Go to the source code of this file.

Namespaces
namespace	math
	for assert

Functions
uint64_t	math::lcmSum (const uint16_t &num)
static void	test ()
int	main ()
	Main function.

Detailed Description

An algorithm to calculate the sum of LCM: \(\mathrm{LCM}(1,n) + \mathrm{LCM}(2,n) + \ldots + \mathrm{LCM}(n,n)\).

An algorithm to calculate the sum of LCM: \(\mathrm{LCM}(1,n) + \mathrm{LCM}(2,n) + \ldots + \mathrm{LCM}(n,n)\) where \(\mathrm{LCM}(i,n)\) denotes the Least Common Multiple of the integers i and n. For n greater than or equal to 1. The value of the sum is calculated by formula:

\[ \sum\mathrm{LCM}(i, n) = \frac{1}{2} \left[\left(\sum (d * \mathrm{ETF}(d)) + 1\right) * n\right] \]

where \mathrm{ETF}(i) represents Euler totient function of i.

Author

Chesta Mittal

Definition in file lcm_sum.cpp.

Function Documentation

main()

int main

(

void

)

Main function.

Returns

0 on exit

Definition at line 97 of file lcm_sum.cpp.

           {
    test();  // execute the tests
    return 0;
}

test()

static void test ( )

static

Function for testing lcmSum function. test cases and assert statement.

Returns

void

Definition at line 66 of file lcm_sum.cpp.

                   {
    uint64_t n = 2;
    uint64_t test_1 = math::lcmSum(n);
    assert(test_1 == 4);
    std::cout << "Passed Test 1!" << std::endl;
 
    n = 5;
    uint64_t test_2 = math::lcmSum(n);
    assert(test_2 == 55);
    std::cout << "Passed Test 2!" << std::endl;
 
    n = 10;
    uint64_t test_3 = math::lcmSum(n);
    assert(test_3 == 320);
    std::cout << "Passed Test 3!" << std::endl;
 
    n = 11;
    uint64_t test_4 = math::lcmSum(n);
    assert(test_4 == 616);
    std::cout << "Passed Test 4!" << std::endl;
 
    n = 15;
    uint64_t test_5 = math::lcmSum(n);
    assert(test_5 == 1110);
    std::cout << "Passed Test 5!" << std::endl;
}