Find the shortest representation of a number in Modular SNUSP Background

Many esoteric programming languages don't have numbers built in at literals, so you have to calculate them at runtime; and in many of these cases, the number representation can be quite interesting. We've already had a challenge about representing numbers for Underload. This challenge is about representing numbers in Modular SNUSP. (Note that you don't need to learn SNUSP in order to complete this challenge – all the information you need is in the specification – but you might find the background interesting.)

The task

For the purpose of this challenge, a Modular SNUSP number is a string formed out of the characters @, +, and =, except that the last character is a #, and that the penultimate character must be + or = (it cannot be @). For example, valid numbers include @+#, ==#, and @@+@=#; examples of invalid numbers include +=, @@#, and +?+#.

The value of a Modular SNUSP number is calculated recursively as follows:


# has a value of 0 (this is the base case).
If the number has the form =x, for any string x, its value is equal to the value of x.
If the number has the form +x, for any string x, its value is equal to the value of x, plus 1.
If the number has the form @cx, for any single character c and any string x, its value is equal to the value of x, plus the value of cx.


For this challenge, you must write a program that takes a nonnegative integer as input, and outputs a string that's the shortest possible Modular SNUSP number that has a value equal to the input.

Clarifications


It's entirely possible that there will be more than one string with the same value, and in particular, for some integers there will be a tie for the shortest Modular SNUSP number with that value. In such a case, you may output any of the numbers involved wit the tie.
There's no restriction on the algorithm you use to find the number; for example, brute-forcing strings and evaluating them is a legal tactic, but so is doing something cleverer to reduce the search space.
As usual on PPCG, your submission may be either a full program or a function (pick whichever is more concise in your language).
This isn't a problem about handling input and output formats, so you can use any reasonable means to input a nonnegative integer and output a string. There's a full guide on meta, but the most commonly used legal methods include function arguments/returns, command line arguments, and standard input/standard output.


Test cases

Here are the shortest representations of the first few numbers:


0: #
1: +#
2: ++#
3: +++# or @++#
4: ++++# or +@++# or @=++#
5: @+++# or @@++#
6: +@+++# or +@@++# or @=+++# or @=@++# or @@=++#
7: @++++# or @+@++#
8: @@+++# or @@@++#
9: +@@+++# or +@@@++# or @+++++# or @++@++# or @+@=++# or @@=+++# or @@=@++#
10: @=@+++# or @=@@++# or @@@=++# (this is a fairly important test case to check, as all the possible answers include =)
11: @+@+++# or @+@@++# or @@++++# or @@+@++#
12: +@+@+++# or +@+@@++# or +@@++++# or +@@+@++# or @=+@+++# or @=+@@++# or @=@=+++# or @=@=@++# or @=@@=++# or @@=++++# or @@=+@++# or @@=@=++#
13: @@@+++# or @@@@++#
14: +@@@+++# or +@@@@++# or @=@++++# or @=@+@++# or @@+++++# or @@++@++# or @@+@=++#
15: @+@++++# or @+@+@++# or @@=@+++# or @@=@@++# or @@@=+++# or @@@=@++#


As a larger test case, the output from input 40 should be @@@=@@+++#, @@@=@@@++#, @@@@=@+++#, or @@@@=@@++#.

Victory condition

As a code-golf challenge, the winner is the shortest entry, measured in bytes.
Oracle SQL 11.2, 341 262 bytes



WITH e AS(SELECT DECODE(LEVEL,1,'=',2,'@','+')e FROM DUAL CONNECT BY LEVEL&lt;4),n(s,v,p,c,i)AS(SELECT'#',0,0,e,1 FROM e UNION ALL SELECT c||s,DECODE(c,'+',1,'@',p,0)+v,v,e,i+1 FROM n,e WHERE i&lt;11)CYCLE s SET y TO 1 DEFAULT 0 SELECT s FROM n WHERE:1=v AND rownum=1;


Old version

WITH e AS(SELECT DECODE(LEVEL,1,'=',2,'@','+')e FROM DUAL CONNECT BY LEVEL&lt;4),n(s,v,p,c) AS(SELECT'#',0,0,e FROM e UNION ALL SELECT s||c,CASE c WHEN'+'THEN 1 WHEN'='THEN 0 WHEN'@'THEN p ELSE 0 END+v,v,e FROM n,e WHERE LENGTH(s)&lt;10)CYCLE s SET y TO 1 DEFAULT 0 SELECT MIN(REVERSE(s))KEEP(DENSE_RANK FIRST ORDER BY LENGTH(s))FROM n WHERE v=:1;


:1 the number to represent in Modular SNUSP

Un-golfed :

WITH e AS (SELECT DECODE(LEVEL,1,'=',2,'@','+')e FROM DUAL CONNECT BY LEVEL&lt;4),  
n(s,v,p,c,i) AS                   
(
  SELECT '#',0,0,e,1 FROM e
  UNION ALL
  SELECT s||c
       , DECODE(c,'+',1,'@',p,0)+v 
       , v
       , e
       , i+1
  FROM n,e
  WHERE i&lt;11
) CYCLE s SET y TO 1 DEFAULT 0
SELECT s FROM n WHERE:1=v AND rownum=1;


First create a view with 3 lines, one for each symbol used to represent numbers, minus # which is only used at the end of the string :

SELECT DECODE(LEVEL,1,'=',2,'@','+')e FROM DUAL CONNECT BY LEVEL&lt;4;    


Then the recursive view n generates every string possible with those 3 symbols, concatenates them to # and evaluates them.

The parameters are :

s : the Modular SNUSP representation of the number being evaluated
  v : the decimal value of s computed by the previous iteration
  p : v computed by the i-2 iteration
  c : the next symbol to concatenate to s
  i : the length of s, only needed to get rid of two LENGTH() for golfing purpose

DECODE(c,'+',1,'@',p,0)+v 


If the last symbol is + then add 1 
If it is @ add the value of the i-2 iteration
Else the symbol is either # or =. v is initialised with 0 in the init part of the recursive view, so the new v is equal to the previous v in either case.

WHERE i&lt;11


Every string possible with the 3 symbols is computed, this part insure that the request does not run until the big crunch.

CYCLE s SET y TO 1 DEFAULT 0


Since there is no rule to the construction of the strings, duplicates are bound to arise. Being in a recursive view Oracle interprets those duplicates as cycles and throw an error if the case is not explicitly taken care of.

SELECT s FROM n WHERE:1=v AND rownum=1;


Returns the first Modular SNUSP representation that evaluate to the decimal number entered as parameter :1

In my tests that first line is always one of the shortest representations.

In the case your database would not act in the same way, then that last clause should be replaced with 

SELECT MIN(s)KEEP(DENSE_RANK FIRST ORDER BY i)FROM n WHERE:1=v