A Friedman Number is a positive integer that is equal to a non-trivial expression which uses its own digits in combination with the operations +, -, *, /, ^, parentheses and concatenation.
A Nice Friedman Number is a positive integer that is equal to a non-trivial expression which uses its own digits in combination with the same operations, with the digits in their original order.
A Very Nice Friedman Number (VNFN), which I am inventing here, is a Nice Friedman Number which can be written without the less pretty (in my opinion) parts of such an expression. Parentheses, concatenation and unary negation are disallowed.
For this challenge, there are three possible ways of writing an expression without parentheses.
Prefix: This is equivalent to left-associativity. This type of expression is written with all operators to the left of the digits. Each operator applies to the following two expressions. For instance:
*+*1234 = *(+(*(1,2),3),4) = (((1*2)+3)*4) = 20
A VNFN which can be written this way is 343:
^+343 = ^(+(3,4),3) = ((3+4)^3) = 343
Postfix: This is equivalent to right-associativity. It is just like prefix notation, except that the operation go to the right of the digits. Each operator applies to the two previous expressions. For instance:
1234*+* = (1,(2,(3,4)*)+)* = (1*(2+(3*4))) = 14
A VNFN which can be written this way is 15655:
15655^+** = (1,(5,(6,(5,5)^)+)*)* = (1*(5*(6+(5^5)))) = 15655
Infix: Infix notation uses the standard order of operations for the five operations. For the purposes of the challenge, that order of operations will be defined as follows: Parenthesize
^ first, right associatively. Then, parenthesize
/ simultaneously, left associatively. Finally, parenthesize
- simultaneously, left associatively.
1-2-3 = (1-2)-3 = -4 2/3*2 = (2/3)*2 = 4/3 2^2^3 = 2^(2^3) = 256 1^2*3+4 = (1^2)*3+4 = 7
A VNFN which can be written this way is 11664:
1*1*6^6/4 = (((1*1)*(6^6))/4) = 11664
Challenge: Given a positive integer, if it can be expressed as a non-trivial expression of its own digits in either prefix, infix or postfix notation, output that expression. If not, output nothing.
Clarifications: If multiple representations are possible, you may output any non-empty subset of them. For instance, 736 is a VNFN:
+^736 = 736 7+3^6 = 736
7+3^6 or both would all be acceptable outputs.
A "Trivial" expression means one that does not use any operators. This only is relevant for one digit numbers, and means that one digit numbers cannot be VNFNs. This is inherited from the definition of a Friedman Number.
Answers should run in seconds or minutes on inputs under a million.
IO: Standard IO rules. Full program, function, verb or similar. STDIN, command line, function argument or similar. For outputing "Nothing", the empty string, a blank line,
null or similar, and an empty collection are all fine. Output may be a string delimited with a character that cannot be in a representation, or may be a collection of strings.
127 None 343 ^+343 736 736^+ 7+3^6 2502 None 15655 15655^+** 11664 1*1*6^6/4 1^1*6^6/4 5 None
Scoring: This is code golf. Fewest bytes wins.
Also, if you find one, please give a new Very Nice Friedman Number in your answer.