Posso verificare se il numero dato può essere la somma di qualsiasi progressione aritmetica che abbia n termini in esso?

Question

E 'possibile per un dato numero s solo verificare che ci sia una possibile progressione aritmetica con n termini e la somma di questi termini n risultati in s.

dove l'elemento di partenza e la differenza di AP non devono essere zero.

per esempio:

s = 24 & n = 4

sì, è possibile, dove AP è 3 5 7 9.

Nota: Voglio solo controllare se è possibile o no Non c'è bisogno di trovare la matrice attuale. 0 < n < 10^9 s < 10^18.

Il mio tentativo:

sappiamo che somma di un AP è pari a s = n (primo + scorso)/2;

quindi prima + ultimo = 2 * s/n;

2 * s/n deve essere un numero intero.

sappiamo anche che last = first + (n-1) diff;

quindi la mia espressione diventa 2 * prima + (n-1) diff = 2 * s/n;

primo = (2 * s/n - (n-1) diff)/2; e dovrebbe essere un numero intero per un particolare valore di diff.

questo è il mio approccio al fare questo, ma la sua complessità temporale è troppo grande per coprire 10^18.

Per favore aiuto. :)

Answer 1

Caso 1: a e d sono numeri reali

Uso s per la somma, n per il numero di termini, un per il primo mandato e d per la differenza tra i termini, si ottiene il risultato

2 * s/n = 2 * a + (n - 1) * d

Questo ti dà un grado di libertà. Così si può vedere che è sempre possibile scegliere un set di infinita di un e d valori che soddisfa questo risultato.

Caso 2: a e d sono numeri interi

si può vedere dal mio risultato che se a e d sono costretti a essere interi, allora la decomposizione è possibile solo se il lato sinistro della questa equazione è anche un numero intero; ovvero 2 * s è un multiplo di n. (Nel tuo caso, 2 * s è 48 che è un multiplo di 4. Quindi sì, esiste un integrale a e d in questo caso).

Answer 2

Penso che questo non sia possibile in ogni caso, ma se è possibile fornire alcuni più dati, allora può. perché ci sono più possibilità della stessa somma di AP. così nel caso in cui si darà qualche suggerimento è possibile

Answer 3

Sia a essere il termine iniziale della progressione e d sua differenza comune. Si vuole risolvere il linear diophantine equation

n * a + (n*(n-1)/2) * d = s 

La soluzione esisterà se e solo se s è un multiplo di gcd(n, n*(n-1)/2).

Se n è dispari, gcd(n, n*(n-1)/2) = n * gcd(1, (n-1)/2) = n.

Se n è pari, gcd(n, n*(n-1)/2) = (n/2) * gcd(2, n-1) = n/2.

In ogni caso, la soluzione esiste se e solo se 2 * s è un multiplo di n.