Alcuin's sequence expansion: O(1)

Alcuin's sequence [See: https://en.wikipedia.org/wiki/Alcuin%27s_sequence] is a series expansion of the polynomial below, where the nth coefficient corresponds to the nth answer, that is, the maximum amount of unique integer triangles with perimeter n.

The algorithmic implementation of this is simply a formula. The Online Encyclopaedia of Integer Sequences (OEIS) provides many formulas that achieve this, the simplest of which is:

• round(n^2 / 48) (Even)
• round((n+3)^2 / 48) (Odd)

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

This evidently has a constant time complexity, given that the only functions required are modulo 2, integer squared and round, each of which are constant time (under certain definitions).

Implementation

Expanded:

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

1-Liner:

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

Or even:

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

Extra

No imports are needed.

As the OP questioned, why do we divide by 48? While I can't answer that explicitly, let's get an intuitive understanding. We are squaring numbers, so it is evidently going to expand greatly. By the time we get to 5, that would give 64 (8^2). So, there must be a constant (albeit a reciprocal) to restrict the growth of the parabola, thus the / 48.

When we graph the OP's method, it gives an alternating parabola. This explains why there is a back-and-forth with the +3 and +0.

This is an intuitive O(n) algorithm I came up with:

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(b-c)//2 + 1
  print(ans)

main()

I find the upper bound and lower bound for b and c and count the values in that range.

I thought of a completely different way to do it:

1. We take the smallest side and call it a. It can never be more than n/3, otherwise a different side would be the smallest.

2. We try to figure out what is the next smallest side (b):

   1. We see what's left after reducing our a.
   2. We divide it by 2 in order to find the middle where we'll start advancing from
   3. We'll see how far we can get before the difference between the lengths is a (or the difference from the middle is a/2) as that's the minimum b side length that is possible and satisfies a+b>c. Basically, the second smallest side is a/2 less than the middle.
   4. The smallest side is the maximum between our calculation or a, in caseb==a. b can never be lower than a as it violates our first rule that a is the smallest.

3. We figure out the difference from the middle and the smallest side. That's how many possible solutions we have for the other 2 sides.

4. Add everything together for every a and that's our solution.

The floor, ceil and % are fixes for when a is odd, the middle is .5, or +1 in case b+c is even, cause b==c is then possible.

Code:

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 = n-a
    middle_number = length_left/2
    
    # Shortest potential side b where the distance between b and c is smaller than a (c-b < 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)

Or in an ugly one-liner:

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