Maybe it only requires asking the LLM to be creative when designing the algorithm. The parent poster spent some time thinking about it, obviously--he didn't generate it accurately "on the fly," either. But he's able to direct his own attention.
I don't see why the LLM couldn't come up with this logic, if prompted to think about a clever algorithm that was highly specific to this problem.
Are you asking it to not write down an algorithm that is general? They are doing a pretty good job on mathematical proofs.
I still don't understand why you wouldn't let its full reasoning abilities by letting it write down code or even another agent. We should be testing towards the result not the methods.
It is worth noting that even ChatGPT-o1 doesn't seem capable of finding this code optimization, despite having access to a Python interpreter.
> Write an efficient program that given a number, find the integer n that satisfies the above constraints
Goal: Find n where sum of integers from 1 to n-1 is ≤ 30
This is a triangular number problem: (n-1)(n)/2 ≤ 30
... code elided ...
> Ok, now make an find_n_for_sum(s=30)
def find_n_for_sum(s: int) -> int: return int((-(-1) + (1 + 8s)*0.5) / 2)
# Tests assert sum(range(1, find_n_for_sum(30))) <= 30 assert sum(range(1, find_n_for_sum(30) + 1)) > 30
So probably time to update your expectations