Expansión de la secuencia de Alcuino: O(1)

La secuencia de Alcuin [Ver: https://en.wikipedia.org/wiki/Alcuin%27s_sequence] es una expansión en serie del polinomio a continuación, donde el n -ésimo coeficiente corresponde a la n -ésima respuesta, es decir, la cantidad máxima de únicos triángulos enteros con perímetro n .

La implementación algorítmica de esto es simplemente una fórmula. La Enciclopedia en línea de secuencias enteras (OEIS) proporciona muchas fórmulas que logran esto, la más simple de las cuales es:

• round(n^2 / 48) (par)
• round((n+3)^2 / 48) (Impar)

[Ver: https://oeis.org/A005044]

Evidentemente, esto tiene una complejidad de tiempo constante, dado que las únicas funciones requeridas son módulo 2, entero cuadrado y redondo, cada una de las cuales es de tiempo constante (bajo ciertas definiciones).

Implementación

Expandido:

 def triangles(n): if n % 2 == 0: return round(n ** 2 / 48) else: return round((n + 3) ** 2 / 48)

1 línea:

 def triangles(n): return round(n ** 2 / 48) if n%2==0 else round((n + 3) ** 2 / 48)

O incluso:

 def triangles(n): return round((n + 3 * n%2) ** 2 / 48)

Extra

No se necesitan import .

Como cuestionó el OP, ¿por qué dividimos por 48? Si bien no puedo responder eso explícitamente, obtengamos una comprensión intuitiva. Estamos elevando los números al cuadrado, por lo que evidentemente se expandirá mucho. Para cuando lleguemos a 5, eso daría 64 (8 ^ 2). Entonces, debe haber una constante (aunque recíproca) para restringir el crecimiento de la parábola, por lo tanto, el / 48.

Cuando graficamos el método OP, da una parábola alterna. Esto explica por qué hay un ida y vuelta con el +3 y el +0.

Este es un algoritmo O(n) intuitivo que se me ocurrió:

 def main(): n = int(input()) if n < 3: print(0) return ans = n % 2 for a in range(2, n//2+1): diff = n - a if diff // 2 < a: break if diff % 2 == 0: b = diff // 2 else: b = diff // 2 + 1 b = max(b - a // 2, a) c = n - b - a if abs(b - c) >= a: b += 1 c -= 1 ans += abs(bc)//2 + 1 print(ans) main()

Encuentro el límite superior y el límite inferior para b y c y cuento los valores en ese rango.

Pensé en una forma completamente diferente de hacerlo:

1. Tomamos el lado más pequeño a lo llamamos . Nunca puede ser más de n/3 , de lo contrario, un lado diferente sería el más pequeño.

2. Tratamos de averiguar cuál es el siguiente lado más pequeño ( b ):

   1. Vemos lo que queda después de reducir nuestro a .
   2. Lo dividimos por 2 para encontrar el medio desde donde comenzaremos a avanzar
   3. Veremos qué tan lejos podemos llegar antes de que la diferencia entre las longitudes sea a (o la diferencia desde el medio sea a/2 ), ya que esa es la longitud mínima del lado b que es posible y satisface a+b>c . Básicamente, el segundo lado más pequeño es a/2 menos que el medio.
   4. El lado más pequeño es el máximo entre nuestro cálculo o a , en el caso b==a . b nunca puede ser menor que a ya que viola nuestra primera regla de que a es la más pequeña.

3. Calculamos la diferencia entre el lado medio y el más pequeño. Esa es la cantidad de posibles soluciones que tenemos para los otros 2 lados.

4. Sume todo junto para cada a y esa es nuestra solución.

El floor , el ceil y el % son arreglos para cuando a es impar, el medio es .5 o +1 en caso de que b+c sea par, porque entonces b==c es posible.

Código:

 import math n = int(input("Enter a number: ")) total = 0 # a is the shortest side for a in range(1, (n//3)+1): length_left = na middle_number = length_left/2 # Shortest potential side b where the distance between b and c is smaller than a (cb < a) b = middle_number-(math.ceil(a/2)-1)-((length_left % 2)/2) # We calculate how far it is from the middle max_distance_from_middle = middle_number - max(b, a) # Add another 1 if the length is even, in case b==c adding = math.floor(max_distance_from_middle) + (1 if length_left % 2 == 0 else 0) total += adding print(total)

O en una frase fea:

 n = int(input("Enter a number: ")) print(sum(math.floor((na)/2 - max((na)/2 - math.ceil(a/2) + 1 - (((na) % 2)/2), a)) + 1 - ((na) % 2) for a in range(1, (n//3)+1)))