Может ли заданное число быть записано как сумма двух или более последовательных положительных целых чисел?

Question

Мне нужно написать метод, который принимает в int и возвращает true, если число может быть записано как сумма двух или более последовательных положительных целых чисел и false в противном случае.

boolean IsSumOfConsecutiveInts(int num) 

Я понял, что все нечетные числа (за исключением числа 1) можно записать в виде суммы 2 последовательных натуральных чисел:

return (num > 1 && num % 2 == 1); 

, но это не учитывает числа, которые могут быть записанный как сумма более 2 последовательных положительных целых чисел (например, 6 == 1 + 2 + 3).

Как определить, может ли число быть записано в виде суммы двух или более последовательных положительных целых чисел?

Answer 1

Эти цифры называются Polite Numbers.

И удобно, только цифры, что не вежливы являются степенями 2.

Итак, что дает нам 2 варианта. Мы можем либо определить, что число вежливо, или мы можем определить, что оно не имеет силы 2.

Я сделал оба; последнее проще (и более эффективно).

1. Это определяет, является ли число вежлив:

   boolean IsSumOfConsecutiveInts(int num) 
   { 
       int sumOfFirstIIntegers = 3; 
       for (int i = 2; sumOfFirstIIntegers <= num; i++) 
       { 
        if (i%2 == 0 ? (num%i == i/2) : (num%i == 0)) 
        { 
         return true; 
        } 
        sumOfFirstIIntegers += i + 1; 
       } 
       return false; 
   } 
   

   Это один довольно трудно понять. Мне потребовалось некоторое время, чтобы придумать.

   В основном, i - количество последовательных целых чисел, которые мы проверяем;

   sumOfFirstIIntegers равен сумме первых i целых чисел, так что это означает, что все числа, которые могут быть выражены в виде суммы i последовательных целых чисел больше или равны sumOfFirstIIntegers.

   Последняя часть, которая заслуживает обсуждения, является логическим выражением i%2 == 0 ? (num%i == i/2) : (num%i == 0). Давайте посмотрим на некоторые примеры:

   i all sums of i consecutive positive integers 
   2 3, 5, 7, 9... 
   3 6, 9, 12, 15... 
   4 10, 14, 18, 22... 
   5 15, 20, 25, 30... 
   

   Есть два случая, но в любом случае, мы можем выразить все возможные числа, сумма i последовательных целых чисел довольно просто.

   1. Когда i даже, num должен быть равен (i * n) + (i/2), где n является неотрицательным целым числом. Конечно, это можно записать как num % i == i/2.

   2. Когда i нечетно, num должен быть равен i * n, где n является неотрицательным целым числом. Что дает нам наше второе условие num % i == 0.

   В дополнение к этим условиям, num не может быть меньше, чем сумма первых i положительных целых чисел. Следовательно, наш цикл for: sumOfFirstIIntegers <= num.

2. Это определяет, является ли число не силы 2:

   boolean IsSumOfConsecutiveInts(int num) 
   { 
       return (num & (num - 1)) != 0; 
   } 
   

   This answer делает хорошую работу, объясняя, почему это работает.

Обратите внимание, что оба вышеупомянутых решения имеют одинаковый результат, это просто разные способы мышления о проблеме.