Найдите четыре последовательных числа, которые суммируются с данным числом

Question

Предположим, есть определенное число, которое мы должны проверить, если оно является произведением четырех последовательных чисел?

Так, если y является нашим данным числом, мы должны проверить, если y = x(x+1)(x+2)(x+3) для любого произвольного x?

Как разработать алгоритм для этой проблемы?

Я сделал это так:

import java.util.*;

public class Product 
{
    public static int product(int i)
    {
         return i * (i+1) * (i+2) * (i+3);
    }

    public static void main(String[] args) 
    {
        Scanner scnr = new Scanner(System.in);
        int x = scnr.nextInt();
        for (int i = 0; i < x/2; i++)
        {
            if (product(i) == x)
            {
                System.out.println("number is product of 4 consecutive numbers");
                break;
            }
        }
    }
}

Answer 1

Начиная с

y = x(x+1)(x+2)(x+3) = x^4 + 6x^3 + 11x^2 + 6x

Обратите внимание, что коэффициенты выглядят почти симметрично, но в конце нет 1.

Итак, предположим, что

y = z^2 - 1

т.е.

z^2 = x^4 + 6x^3 + 11x^2 + 6x + 1 

Существуют коэффициенты всех степеней от x до 4, а также коэффициентов от x ^ 4 и x ^ 0равны 1, поэтому нам нужно найти коэффициент x ^ 1, который мы называем a:

z = (x^2 + ax + 1)^2 = x^4 + 2ax^3 + (2+a^2)x^2 + 2ax + 1

Сравнение коэффициентов x ^ 1, x ^ 2 или x ^ 3 дает a = 3

(приведенные выше уравнения не требуют, чтобы любое из x, y или z было целым числом, но, возможно, потеряет сложные или отрицательные корни, которые нам не интересны)

, поэтому мы можем решитьквадратичное значение для x:

x^2 + 3x + 1 - sqrt(y+1) = 0

дает

x = -3 +/- sqrt(9 - 4 * (1-sqrt(y+1))) 
    ---------------------------------
                2

  = -3 +/- sqrt(5 + 4 sqrt(y+1)) 
    ----------------------------
                2

, которое будет целым числом, если sqrt(y+1) - идеальный квадрат z, а (5+4z) - также идеальныйквадрат (если z является целым числом, 5-4z является нечетным, поэтому его квадратный корень, если целое число, также является нечетным, а x будет целым числом).

Проверьте, является ли z = sqrt(y+1)целое число, затем проверьте, является ли 5+4z идеальным квадратом.

Answer 2

Вам нужно только проверить floor(y**(0.25)-1).Когда y приближается к бесконечности, x приближается к y**0.25-1.5 (снизу).

В некоторой степени это довольно интуитивно понятно.x*(x+1)*(x+2)*(x+3) - это произведение четырех чисел, среднее значение которых равно x+1.5.Когда х высокий, 1,5 выглядит маленьким.

Answer 3

Для многих чисел мы можем легко увидеть, могут ли они соответствовать определенному X или нет:

• Y должно делиться на 3, так как хотя бы одно из последовательных чисел должно делиться на 3
• Y должно делиться на 4, поскольку хотя бы одно из последовательных чисел должно делиться на 4

Таким образом, Y должно делиться как минимум на 12 (3 * 4).Это означает, что вы можете легко выбросить около 92% всех чисел.

Поскольку значение Y будет содержать по крайней мере 4-ую степень X, вы можете начать с получения 4-го корня (иликак вы называете это по-английски) Y, затем округляет это до целочисленного значения, называет его X и вычисляет результат X (X + 1) (X + 2) (X + 3).

Результат, вероятно, будет выше (поскольку мы опускаем другие факторы, такие как X, в степень 3, X в степень 2, ...).

Теперь вычтите 1 из X и выполните те же вычисления.

Пока результат выше, чем Y, повторяйте его, пока результат не станет ниже, или пока вы точно не получите Y.

Answer 4

Посчитайте четвертый корень из y, округлите его и назовите a. a(a-1)(a-2)(a-3) намного меньше, чем y. Посчитайте четвертый корень из y, округлите его и назовите b. b(b+1)(b+2)(b+3) намного больше, чем y. Теперь у вас есть три возможных номера для начала: a-2, a-1 и a (примечание a = b или a = b-1). Так что должно быть достаточно проверить (a-2)(a-1)a(a+1), (a-1)a(a+1)(a+2) и a(a+1)(a+2)(a+3).

Answer 5

Редактировать : прочитайте вопрос неправильно, но для чего он стоит (быстрый способ проверить, не является ли он произведением четырех последовательных целых чисел):

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

Answer 6

Я бы начал с получения четвертого корня из 'y'.Это дало бы вам приближение для наименьшего фактора y (то есть 'x'), который вы могли бы использовать.Используйте это как основу стандартного алгоритма факторизации.

Answer 7

Ответ очень прост.
Для заданного числа y, если y + 1 не является идеальным квадратом, то y не является произведением четырех последовательных чисел.Если y + 1 - идеальный квадрат, то y - произведение четырех последовательных чисел тогда и только тогда, когда sqrt (5 + 4 * sqrt (y + 1)) - целое число.

Answer 8

Ваше уравнение может быть упрощено как

y = x^4 + 6*x^3 + 11*x^2 + 6x

Вы можете начать с x = 1 и идти вверх, чтобы проверить.Мы можем отметить очень простую для вычисления верхнюю границу: 4-й корень из y (или квадратный корень из квадратного корня из y).То есть, когда вы достигнете этого числа, вы можете остановиться.Это вам повезло, потому что, к счастью для нас, 4-е корни очень, очень, очень, очень маленькие .

Для чисел до 10 000 это довольно легко проверить, потому что вы собираетесьпроверить не более десяти целых чисел.Если ваш номер меньше 500, вам нужно будет проверить не более четырех целых чисел.

При 1 000 000+ вам придется начать проверять 31 и более номеров, так что он может начать становиться менее тривиальным.

---

Верхняя и нижняя границы

После некоторого тщательного уточнения из-за Wolfram Alpha были сделаны две вещи:

1. Более точная верхняя граница y ^ 0,25 - 1,2
2. Определенная нижняя граница y ^ 0,25 - 1,5

, так что ...

y = num_to_check
k = Math.sqrt(Math.sqrt(y))   # or Math.pow(y,0.25)
lower = int(k-1.5)
upper = int(Math.ceil(k-1.2))
for n in (lower...upper)
  if n * (n+1) * (n+2) * (n+3) == y
    return n
  end
end
return nil

Примечаниечто в этом случае для любого данного редактирования y .

можно проверить максимум из двух чисел: после уточнения x только до целых чисел появляетсяво всех случаях нужно проверить только один номер, поскольку ваш диапазон уменьшается до одного номера.Здорово!(спасибо Брайану)

Answer 9

Как уже говорили другие, начните с 4-го корня y (назовем его z).

Из последовательности x, x + 1, ... x + 3 мы знаем, что некоторые значения должны быть меньше z, а некоторые должны быть больше z (поскольку все они не могут быть равны z) .

Итак, мы знаем, что

x <= ceiling(z)
x+3 >= floor(z)

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