Znajdź cztery kolejne liczby, które sumują się pod podanym numerem

Question

Załóżmy, że jest podana liczba, którą powinniśmy sprawdzić, jeśli jest ona wynikiem czterech kolejnych liczb?

Więc jeśli y jest naszą podaną liczbą, powinniśmy przetestować, czy y = x(x+1)(x+2)(x+3) dla dowolnego arbitrażowego x?

Jak zaprojektować algorytm dla tego problemu?

Zrobiłem to tak:

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

Począwszy

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

zauważyć, że współczynniki wyglądają niemal symetryczny, ale nie ma 1 na końcu.

Więc załóżmy, że

y = z^2 - 1 

tj

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

Istnieje współczynniki wszystkich sił x do 4, a te x^4, a x^0 to 1, więc trzeba znaleźć współczynnik x^1, co nazywamy a:

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

porównanie współczynnik x^1 x^2, lub x^3 przedstawia a = 3

(powyższe równanie nie wymaga, żeby każdy z x, Y lub z jest liczbą całkowitą, ale może stracić złożone lub negatywne korzenie, którymi nie jesteśmy zainteresowani)

więc możemy rozwiązać kwadratowego dla x:

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

daje

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

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

który będzie liczbą całkowitą, jeśli sqrt(y+1) jest idealny kwadrat z i (5+4z) jest również idealny kwadrat (jeśli z jest liczba całkowita, 5-4z jest nieparzysta, więc pierwiastek kwadratowy, jeśli jest liczbą całkowitą, jest również nieparzysty, a x będzie liczbą całkowitą).

Sprawdź więc, czy z = sqrt(y+1) jest liczbą całkowitą, a następnie sprawdź, czy 5+4z jest idealnym kwadratem.

Answer 2

Edit: przeczytać pytanie źle, ale za to, co warto (szybki sposób sprawdzić, czy nie jest to produkt z czterech kolejnych liczb całkowitych):

Dowolny produkt z czterech następujących po sobie liczb całkowitych to equal to one less niż perfect square.

Answer 3

Zacznę od uzyskania czwartego katalogu głównego z "y". To da ci przybliżenie najmniejszego współczynnika y (tj. "X"), którego możesz użyć. Użyj tego jako podstawy standardowego algorytmu rozkładu.

Answer 4

Dla wielu numerów możemy łatwo sprawdzić, czy mogą one pasować pewien X czy nie:

• Y musi być podzielna przez 3, ponieważ co najmniej jedna z kolejnych numerów musi być podzielna przez 3
• Y musi być podzielna przez 4, ponieważ co najmniej jeden z kolejnych numerów muszą być podzielna przez 4

Tak więc musi być co najmniej o 12 podzielna (3 * 4). Oznacza to, że można łatwo wyrzucić około 92% wszystkich numerów.

Ponieważ wartość Y będzie zawierała co najmniej 4 moc X, możesz zacząć od zrobienia czwartego rdzenia (lub jak to nazwać po angielsku) Y, a następnie zaokrąglić to do wartość całkowita, wywołanie go X i obliczenie wyniku X (X + 1) (X + 2) (X + 3).

Wynik będzie prawdopodobnie wyższy (ponieważ pominięto pozostałe czynniki, takie jak X, do potęgi 3, X do potęgi 2, ...).

Teraz odejmij 1 od X i wykonaj te same obliczenia.

Dopóki wynik jest wyższy niż Y, powtórzyć to, aż wynik jest niższy, albo dokładnie uzyskane Y.

Answer 5

równanie można uprościć

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

Można zacząć od x = 1 i przejdź do góry, aby sprawdzić. Możemy zauważyć bardzo łatwe do obliczenia górne ograniczenie: czwarty pierwiastek y (lub pierwiastek kwadratowy pierwiastka kwadratowego z y). Oznacza to, że po osiągnięciu tego poziomu możesz przestać. To dla ciebie szczęście, ponieważ na szczęście dla nas 4 korzenie to bardzo, bardzo, bardzo, bardzo, bardzo,.

Dla liczb do 10 000 jest to dość łatwe do sprawdzenia, ponieważ sprawdzasz co najwyżej dziesięć liczb całkowitych. Jeśli Twój numer jest mniejszy niż 500, musisz tylko sprawdzić cztery liczby całkowite co najwyżej.

Przy 1.000.000+, będziesz musiał zacząć sprawdzać 31 i więcej liczb, więc może zacząć być mniej trywialny.

---

kresy dolny i górny

Po pewnym ostrożnym wyrafinowanie powodu Wolfram Alpha dwie rzeczy zostały zawarta:

1. Bardziej wyrafinowane górna granica y^0,25 - 1,2
2. określona dolna granica y^0,25 - 1,5

czyli ...

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 

Należy zauważyć, że w tym przypadku istnieje maksymalnie dwa numerami być sprawdzone dla danego y.

edytuj: po doprecyzowaniu x tylko do liczb całkowitych, okazuje się, że jest tylko jedna liczba do sprawdzenia, we wszystkich przypadkach, ponieważ zakres zmniejsza się do jednej liczby. Chłodny! (Dzięki Brian)

Answer 6

Policzyć czwarty pierwiastek z y, zaokrąglić w dół i nazywają to a. a(a-1)(a-2)(a-3) jest znacznie mniejszy niż y. Policz czwarty pierwiastek z y, zaokrąglij go i nazwij go: b. b(b+1)(b+2)(b+3) to znacznie więcej niż y. Teraz masz trzy możliwe numery zaczynające się od: a-2, a-1 i a (uwaga a = b lub a = b-1). Więc powinno wystarczyć sprawdzenie (a-2)(a-1)a(a+1), (a-1)a(a+1)(a+2) i a(a+1)(a+2)(a+3).

Answer 7

Wystarczy przetestować floor(y**(0.25)-1). Gdy y zbliżasz się do nieskończoności, x zbliża się do y**0.25-1.5 (od dołu).

W pewnym stopniu jest to raczej intuicyjne. x*(x+1)*(x+2)*(x+3) jest produktem czterech liczb, których średnia jest równa x+1.5. Kiedy x jest wysokie, 1.5 wygląda na małe.

Answer 8

Odpowiedź jest bardzo prosta.
Dla podanej liczby y, jeśli y + 1 nie jest idealnym kwadratem, wówczas y nie jest iloczynem czterech kolejnych liczb. Jeśli y + 1 jest idealnym kwadratem, wówczas y jest iloczynem czterech kolejnych liczb wtedy i tylko wtedy, gdy sqrt (5 + 4 * sqrt (y + 1)) jest liczbą całkowitą.

Answer 9

Jak powiedzieli inni, zacznij od czwartego pierwiastka z y (nazwijmy go z).

Z sekwencji x, x + 1, ... x + 3, wiemy, że niektóre wartości muszą być mniejsze niż z, a niektóre muszą być większe niż z (ponieważ nie wszystkie mogą być równe z).

Tak, wiemy, że

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

To daje bardzo mały zakres numerów spróbować dla x.