Encuentra cuatro números consecutivos que suman el número dado

Question

Supongamos que hay un número determinado que deberíamos probar si es producto de cuatro números consecutivos.

Así que si y es nuestro número dado que debe probar si y = x(x+1)(x+2)(x+3) para cualquier arbitraria x?

¿Cómo diseñar un algoritmo para este problema?

lo he hecho así:

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

A partir de

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

en cuenta que los coeficientes se ven casi simétrica, pero no hay 1 al final.

Así que supongamos que

y = z^2 - 1 

es decir,

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

Hay coeficientes de todas las potencias de x hasta 4, y los de x^4 y x^0 son 1, por lo que necesitamos para encontrar el coeficiente de x^1, que llamamos a:

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

comparando coeficiente de x^1, x^2, o x^3 da a = 3

(las ecuaciones anteriores no requieren que cualquiera de X, y o Z es un número entero, pero posiblemente perder raíces complejas o negativas en las que no estamos interesados)

fin de poder solucionar una ecuación cuadrática para x:

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

da

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

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

que será un número entero si sqrt(y+1) es un cuadrado perfecto z, y (5+4z) es también un cuadrado perfecto (si z es un número entero, 5-4z es impar, por lo que su raíz cuadrada, si es un número entero, también es impar y x será un número entero).

Así que pruebe si z = sqrt(y+1) es un número entero, luego pruebe si 5+4z es un cuadrado perfecto.

Answer 2

Editar: leer la pregunta sin ella, sino por lo que vale la pena (una forma rápida de comprobar si no es un producto de cuatro enteros consecutivos):

Cualquier producto de cuatro enteros consecutivos es equal to one less que perfect square.

Answer 3

Comenzaría obteniendo la cuarta raíz de 'y'. Esto le daría una aproximación para el factor más pequeño de y (es decir, 'x') que podría usar. Use esto como la base de un algoritmo de factorización estándar.

Answer 4

Para muchos números podemos ver fácilmente si podrían encajar un cierto X o no:

• Y debe ser divisible por 3, ya que al menos uno de los números consecutivos debe ser divisible por 3
• Y debe ser divisible por 4, ya que al menos uno de los números consecutivos debe ser divisible por 4

Así Y debe ser al menos divisible por 12 (3 * 4). Esto significa que puede tirar fácilmente el 92% de todos los números.

Dado que el valor de Y contendrá al menos la 4ª potencia de X, puede comenzar tomando la raíz 4ª (o cómo se llama esto en inglés) de Y, y luego redondeando esto a una valor entero, llamándolo X y calcular el resultado de X (X + 1) (X + 2) (X + 3).

El resultado probablemente será mayor (porque omitimos los otros factores como X a la potencia de 3, X a la potencia de 2, ...).

Resta ahora 1 de X y realiza los mismos cálculos.

Mientras el resultado es mayor que Y, repetir esto hasta que el resultado es inferior, o usted obtuvo exactamente Y.

Answer 5

Su ecuación se puede simplificar como

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

Usted puede comenzar desde x = 1 y vaya hacia arriba para verificar. Podemos observar un límite superior muy fácil de calcular: la cuarta raíz de y (o la raíz cuadrada de la raíz cuadrada de y). Es decir, cuando alcanzas ese número, puedes parar. Esto es una suerte para ti, porque afortunadamente para nosotros, las raíces del 4to son muy muy muy muy pequeño.

Para números de hasta 10,000, esto es bastante fácil de verificar, porque vas a verificar como máximo diez enteros. Si su número es menor de 500, solo deberá verificar cuatro enteros como máximo.

En 1,000,000+, tendrá que comenzar a verificar 31 y más números, por lo que podría empezar a ser menos trivial.

---

límites superior e inferior

Después de un cuidadoso refinamiento debido a Wolfram Alpha, dos cosas han concluido:

1. A más refinado límite superior de y^0,25-1,2
2. A límite inferior definido de y^0.25 - 1.5

tan ...

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 

Nótese que en este caso, hay un máximo de dos números para ser revisado por cualquier dada y.

editar: después de refinar x solo a los enteros, parece que solo hay un número para verificar, en todos los casos, a medida que su rango se reduce a un número. ¡Guay! (gracias a Brian)

Answer 6

Cuente la cuarta raíz de y, redondee hacia abajo y llámelo a. a(a-1)(a-2)(a-3) es mucho menos que y. Cuente la cuarta raíz de y, ciérrela y llámela b. b(b+1)(b+2)(b+3) es mucho más que y. Ahora tiene tres números posibles para comenzar: a-2, a-1 y a (nota a = b o a = b-1). Por lo tanto, debería ser suficiente para verificar (a-2)(a-1)a(a+1), (a-1)a(a+1)(a+2) y a(a+1)(a+2)(a+3).

Answer 7

Solo necesita probar floor(y**(0.25)-1). Cuando y se acerca al infinito, x se aproxima a y**0.25-1.5 (desde abajo).

Hasta cierto punto, esto es bastante intuitivo. x*(x+1)*(x+2)*(x+3) es un producto de cuatro números cuyo promedio es igual a x+1.5. Cuando x es alto, 1.5 parece pequeño.

Answer 8

La respuesta es muy simple.
Para el número dado y si y + 1 no es cuadrado perfecto, y no es producto de cuatro números consecutivos. Si y + 1 es cuadrado perfecto, y es producto de cuatro números consecutivos si y solo si sqrt (5 + 4 * sqrt (y + 1)) es entero.

Answer 9

Como han dicho otros, comience con la cuarta raíz de y (llamémosla z).

Fuera de la secuencia x, x + 1, ... x + 3, sabemos que algunos valores deben ser menores que z, y algunos deben ser mayores que z (ya que no todos pueden ser iguales a z)

Por lo tanto, sabemos que

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

Eso le da un rango muy pequeño de los números para tratar de x.