Very Nice Friedman Numbers

Question

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 * and / simultaneously, left associatively. Finally, parenthesize + and - 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

+^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.

Related.

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.

Examples:

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.

Answer 1

Perl, 345 334 318 293 263 245B

$_='$_=$i=pop;$c=y///c-1;sub f{say if$c&&$i==eval pop=~s/\^/**/gr}A$m)$1$4"})};f"("x$c.$m}globOx$c.$i;A$1$4($m"})};f$m.")"x$c}glob$i.Ox$c;map{f$_}glob joinO,/./g';s!O!"{+,-,*,/,^}"!g;s!A!'map{m{(\d)((?R)|(\d)(?{$m=$3}))(.)(?{$m="'!ge;s!d!D!;eval

Call with perl -M5.10.0 scratch.pl 736

---

Results

The first few results that I found are:

^+343
736^+
7+3^6
^+/3125
^+^3125
/^+-11664
/^--11664
1-1+6^6/4
/^++14641
^^++14641
1+5^6/1-8
1+5^6^1-8
1+5^6-2-2
1+5^6-2^2
1+5^6+2-4
1+5^6+4^2
-^+^16377
-^-+16377
/^+^16384
/^-+16384

---

Explanation

Fully ungolfed

I tried to repeat myself as much as possible to make the later golfing easier.

#!perl
use 5.10.0;

$_ = $input = pop;

# y///c counts characters in $_
$count = y///c - 1;

sub f {
    say if $count && $input == eval pop =~ s/\^/**/gr
}

# PREFIX
map {
    m{                            # Parses *^+1234
        (\D)                      # $1 = first symbol
        (
            (?R)                  # RECURSE
        |
            (\d)(?{               # $3 = first digit
                $match=$3
            })
        )
        (.)(?{                    # $4 = last digit
            $match="$match)$1$4"
        })
    }x;
    f "(" x $count . $match
}
    # glob expands '{0,1}{0,1}' into 00,01,10,11
    glob "{+,-,*,/,^}" x $count . $input;

# POSTFIX
map {
    m{(\d)((?R)|(\d)(?{$match=$3}))(.)(?{$match="$1$4($match"})};
    f $match. ")" x $count
}
    glob $input . "{+,-,*,/,^}" x $count;

# INFIX
# /./g splits $_ into characters
map { f $_} glob join "{+,-,*,/,^}", /./g

How it's golfed

• Remove whitespace & comments and replace all vars with 1-character version
• Wrap program in $_=q! ... !;eval
• Extract strings and substitute them in afterwards.

This gives something like this, from which you can remove the line breaks for the result:

$_='
    $_=$i=pop;
    $c=y///c-1;
    sub f{say if$c&&$i==eval pop=~s/\^/**/gr}
    A$m)$1$4"})};f"("x$c.$m}globOx$c.$i;
    A$1$4($m"})};f$m.")"x$c}glob$i.Ox$c;
    map{f$_}glob joinO,/./g
';
s!O!"{+,-,*,/,^}"!g;
s!A!'map{m{(\d)((?R)|(\d)(?{$m=$3}))(.)(?{$m="'!ge;
s!d!D!;
eval

Answer 2

Ruby 2.1.5 only - 213 220 238 + 9 = 247

Not sure how Ruby beats Perl, but here you go...

Run this with a -rtimeout flag (and either -W0 or send your stderr elsewhere).

To make this slightly more robust, replace send([].methods[81],z-1) with repeated_permutation(z-1) and score an extra character (so, 248).

g=$*[0].split //
exit if 2>z=g.size
d=->a,s{$><<a*''&&exit if$*[0].to_i==timeout(2){eval"#{(s*'').gsub(?^,'**')}"}rescue p}
l,r=[?(]*z,[?)]*z
%w{* / + - ^}.send([].methods[81],z-1){|o|d[m=g.zip(o),m]
d[g+o,l.zip(m)+r]
d[o+g,l+g.zip(r,o)]}

Basically, go through all permutations of operators and try infix, postfix, and prefix in that order. The d method uses eval on the second parameter to perform the calculations, catching any DivideByZero or Overflow exceptions.

You need to send stderr to /dev/null, though, or else eval will sometimes print warnings like (eval):1: warning: in a**b, b may be too big.

While I came up with this ungolfing, I found a way to save three chars!

Ungolfed (outdated but similar principles):

input = $*[0]
digits = input.split //
num_digits = digits.size
exit if 2 > num_digits # one-digit numbers should fail

def print_if_eval print_array, eval_array
  # concatenate the array and replace ^ with **
  eval_string = (eval_array * '').gsub(?^, '**') 
  val = eval(eval_string)
  if input.to_i == val
    $><<print_array*''
    exit
  end
rescue
  # this catches any DivideByZero or Overflow errors in eval.
end
# technically, this should be * (num_digits - 1), but as long as we 
# have AT LEAST (num_digits - 1) copies of the operators, this works
operators = %w{* / + - ^} * num_digits
left_parens = ['('] * num_digits
right_parens = [')'] * num_digits
operators.permutation(num_digits-1) { |op_set|
  # infix
  # just uses the native order of operations, so just zip it all together
  # 1+2-3*4/5^6
  print_if_eval(digits.zip(op_set),
                digits.zip(op_set))

  # postfix
  # leftparen-digit-operator, repeat; then add right_parens
  # (1+(2-(3*(4/(5^(6))))))
  # 
  print_if_eval(digits+op_set,
                (left_parens.zip(digits, op_set) + right_parens))

  # prefix
  # leftparens; then add digit-rightparen-operator, repeat
  # ((((((1)+2)-3)*4)/5)^6)
  print_if_eval(op_set+digits,
                left_parens + digits.zip(right_parens, op_set))
}

Changelog

247 made this work for larger numbers instead of timing out.

220 shaved off three chars by declaring paren arrays, and fixed a bug where one-digit numbers were considered VNFNs

213 initial commit

Answer 3

MATLAB (435 b)

n=input('');b=str2num(fliplr(num2str(n)));l=floor(log(b)/log(10));a=unique(nchoosek(repmat('*+-/^', 1,5), l), 'rows');for k=1:numel(a(:,1)),for j=0:2,c=strcat((j>1)*ones(l)*'(',mod(b,10)+48);for i=1:l,c=strcat(c,a(k,i),(j<1)*'(',mod(floor(b/10^i),10)+48,(j>1)*')'); end,c=strcat(c,(j<1)*ones(l)*')');if eval(c(1,:))==n,fprintf('%s%s%s%s\n',c(1,1:(j==1)*numel(c(1,:))),fliplr(a(k,1:(j>1)*l)),(j~=1)*num2str(n),a(k,1:(j<1)*l));end,end,end

---

try it here

http://octave-online.net/

Answer 4

Python 2, 303 bytes

Try it online

from itertools import*
n=input()
l=len(n)-1
E=eval
for c in product('+-*/^',repeat=l):
 L=lambda x,y:x.join(map(y.join,zip(n,c+('',)))).replace('^','**')
 C=''.join(c)
 try:
    if`E(L('',''))`==n:print L('','')
    if`E('('*-~l+L('',')'))`==n:print C[::-1]+n
    if`E(L('(','')+')'*l)`==n:print n+C
 except:pass

Infix output will contain ** instead of ^. If this is not allowed, .replace('**','^') will occure and add another 18 bytes

Explanation:

# get all possible combinations of operators (with repetitions)
product('+-*/^',repeat=l)  

# create string from input and operators like
# if passed '(' and '' will return (a+(b+(c
# if passed '' and ')' will return a)+b)+c)
# if passed '' and '' will return a+b+c
lambda x,y:x.join(map(y.join,zip(n,c+('',)))).replace('^','**')

# evaluate infix
E(L('',''))
# evaluate prefix
E('('*-~l+L('',')')) 
# evaluate postfix
E(L('(','')+')'*l)
# all evals need to be inside try-except to handle possible 0 division

# prefix output is need to be swapped (which IMO is not needed)
n:print C[::-1]+n