Является ли натуральное число последовательным?

Для проверки того, может ли натуральное число быть представлено суммой последовательных натуральных чисел (например, 1+2+3+4=10, 5+6+7=18) никаких сумм рядов вычислять не нужно, для двоичных чисел достаточно проверки их битовых свойств. Конечно, следует помнить об INT_MAX, то есть, об ограниченности диапазона представления целых чисел в компьютере. Кроме того, самих чисел суммы мы при таком подходе не увидим.

Всё основано на том, что сумма любых двух последовательных чисел нечётна, при этом, одно из них чётно, а другое нет :) Ну и 2n = 2*2n-1, конечно.

Проверить с выводом самих чисел можно вот здесь в онлайн-сервисе, а ниже - листинг на консольном C++:

#include <iostream>
#include <climits>
using namespace std;

bool checkForSum(long long int n) {
 return ((n&(n-1)) && n);
}

int main() {
 long long int n = 5UL;
 cout << endl << n << ": " << checkForSum(n); //1
 n = 12345678UL+12345679UL+12345680UL;
 cout << endl << n << ": " << checkForSum(n); //1
 n=8192;
 cout << endl << n << ": " << checkForSum(n); //0
 cin.get();
 return 0;
}

05.04.2018, 14:20 [2000 просмотров]