# Sum of first N natural numbers which are not powers of K

Given two integers and , the task is to find the sum of all the numbers within the range **[1, n]** excluding the numbers which are positive powers of **k** i.e. the numbers **k, k ^{2}, k^{3} and so on**.

**Examples:**

Input:n = 10, k = 3Output:43

1 + 2 + 4 + 5 + 6 + 7 + 8 + 10 = 43

3 and 9 are excluded as they are powers of 3Input:n = 11, k = 2Output:52

Attention reader! Don’t stop learning now. Get hold of all the important mathematical concepts for competitive programming with the

Essential Maths for CP Courseat a student-friendly price. To complete your preparation from learning a language to DS Algo and many more, please referComplete Interview Preparation Course.

**Approach:**

- Store the sum of first natural numbers in a variable i.e.
**sum = (n * (n + 1)) / 2**. - Now for every positive power of which is less than , subtract it from the .
- Print the value of the variable in the end.

Below is the implementation of the above approach:

## C++

`// C++ program to find the sum of` `// first n natural numbers which are` `// not positive powers of k` `#include <bits/stdc++.h>` `using` `namespace` `std;` `// Function to return the sum of` `// first n natural numbers which are` `// not positive powers of k` `int` `find_sum(` `int` `n, ` `int` `k)` `{` ` ` `// sum of first n natural numbers` ` ` `int` `total_sum = (n * (n + 1)) / 2;` ` ` `int` `power = k;` ` ` `while` `(power <= n) {` ` ` `// subtract all positive powers` ` ` `// of k which are less than n` ` ` `total_sum -= power;` ` ` `// next power of k` ` ` `power *= k;` ` ` `}` ` ` `return` `total_sum;` `}` `// Driver code` `int` `main()` `{` ` ` `int` `n = 11, k = 2;` ` ` `cout << find_sum(n, k);` ` ` `return` `0;` `}` |

## Java

`// Java program to find the sum of` `// first n natural numbers which are` `// not positive powers of k` `import` `java.io.*;` `class` `GFG {` ` ` `// Function to return the sum of` `// first n natural numbers which are` `// not positive powers of k` `static` `int` `find_sum(` `int` `n, ` `int` `k)` `{` ` ` `// sum of first n natural numbers` ` ` `int` `total_sum = (n * (n + ` `1` `)) / ` `2` `;` ` ` `int` `power = k;` ` ` `while` `(power <= n) {` ` ` `// subtract all positive powers` ` ` `// of k which are less than n` ` ` `total_sum -= power;` ` ` `// next power of k` ` ` `power *= k;` ` ` `}` ` ` `return` `total_sum;` `}` `// Driver code` ` ` `public` `static` `void` `main (String[] args) {` ` ` `int` `n = ` `11` `, k = ` `2` `;` ` ` `System.out.println(find_sum(n, k));` ` ` `}` `}` `// This code is contributed by inder_verma..` |

## Python3

`# Python 3 program to find the sum of` `# first n natural numbers which are` `# not positive powers of k` `# Function to return the sum of` `# first n natural numbers which are` `# not positive powers of k` `def` `find_sum(n, k):` ` ` `# sum of first n natural numbers` ` ` `total_sum ` `=` `(n ` `*` `(n ` `+` `1` `)) ` `/` `/` `2` ` ` `power ` `=` `k` ` ` `while` `power <` `=` `n:` ` ` `# subtract all positive powers` ` ` `# of k which are less than n` ` ` `total_sum ` `-` `=` `power` ` ` `# next power of k` ` ` `power ` `*` `=` `k` ` ` `return` `total_sum` `# Driver code` `n ` `=` `11` `; k ` `=` `2` `print` `(find_sum(n, k))` `# This code is contributed` `# by Shrikant13` |

## C#

`// C# program to find the sum of` `// first n natural numbers which are` `// not positive powers of k` `using` `System;` `class` `GFG {` `// Function to return the sum of` `// first n natural numbers which are` `// not positive powers of k` `static` `int` `find_sum(` `int` `n, ` `int` `k)` `{` ` ` `// sum of first n natural numbers` ` ` `int` `total_sum = (n * (n + 1)) / 2;` ` ` `int` `power = k;` ` ` `while` `(power <= n) {` ` ` `// subtract all positive powers` ` ` `// of k which are less than n` ` ` `total_sum -= power;` ` ` `// next power of k` ` ` `power *= k;` ` ` `}` ` ` `return` `total_sum;` `}` `// Driver code` ` ` `public` `static` `void` `Main () {` ` ` `int` `n = 11, k = 2;` ` ` `Console.WriteLine(find_sum(n, k));` ` ` `}` `}` `// This code is contributed by inder_verma..` |

## PHP

`<?php` `// PHP program to find the sum of` `// first n natural numbers which are` `// not positive powers of k` `// Function to return the sum of` `// first n natural numbers which are` `// not positive powers of k` `function` `find_sum(` `$n` `, ` `$k` `)` `{` ` ` `// sum of first n natural numbers` ` ` `$total_sum` `= (` `$n` `* (` `$n` `+ 1)) / 2;` ` ` `$power` `= ` `$k` `;` ` ` `while` `(` `$power` `<= ` `$n` `)` ` ` `{` ` ` `// subtract all positive powers` ` ` `// of k which are less than n` ` ` `$total_sum` `-= ` `$power` `;` ` ` `// next power of k` ` ` `$power` `*= ` `$k` `;` ` ` `}` ` ` `return` `$total_sum` `;` `}` `// Driver code` `$n` `= 11; ` `$k` `= 2;` `echo` `find_sum(` `$n` `, ` `$k` `);` `// This code is contributed by inder_verma..` `?>` |

## Javascript

`<script>` `// Javascript program to find the sum of` `// first n natural numbers which are` `// not positive powers of k` `// Function to return the sum of` `// first n natural numbers which are` `// not positive powers of k` `function` `find_sum(n, k)` `{` ` ` `// sum of first n natural numbers` ` ` `let total_sum = (n * (n + 1)) / 2;` ` ` `let power = k;` ` ` `while` `(power <= n) {` ` ` `// subtract all positive powers` ` ` `// of k which are less than n` ` ` `total_sum -= power;` ` ` `// next power of k` ` ` `power *= k;` ` ` `}` ` ` `return` `total_sum;` `}` `// Driver code` ` ` `let n = 11, k = 2;` ` ` `document.write(find_sum(n, k));` ` ` `// This code is contributed by Mayank Tyagi` `</script>` |

**Output:**

52