# Generate Friedman numbers

A Friedman number is a number that can be expressed by applying basic mathematical operations(^,/,*,+,-) to all it's digits. The operations need not be applied to each individual digit, but all the digits must be involved. That is, 121= 11^2 --> all digits are involved, but 1 & 1 have been clubbed together to make 11.

Use of parenthesis is allowed, but the trivial solution `x= (x)` is not a valid solution. Also not valid, `x= +x`.

Examples

• 25= 5^2
• 121= 11^2
• 343= (3+4)^3
• 2048 = (8^4)/2+0

Write a program that will take positive two integers and print the number of Friedman numbers in that range(inclusive), and the numbers with the expressions in subsequent lines.

Input -

``````n m    | n, m integers, n>=0, m>n
``````

Output -

``````count    | number of Friedman numbers in the given range
fn1 exp1 | Friedman number, expression
fn2 exp2
fn3 exp3
.
.
.
``````

Shortest code posted by Sunday 29th July 00:00 Hrs GMT will be the winner.

-
Can you add some example Friedman numbers and explain how `/` works? For instance what is `1/3`? – JPvdMerwe Jul 19 '12 at 7:10
The number is expressed by applying the operations to all it's digits. i.e 25 = 5^2, 126= 6*21, 343= (3+4)^3 and so on – elssar Jul 19 '12 at 7:11
Do you allow unary minus? e.g `-5`? – JPvdMerwe Jul 19 '12 at 7:41
@JPvdMerwe check the input specification, you wouldn't need to do that, but if you want to, knock yourself out. Though unary plus is not allowed. i.e +5 is not a valid solution – elssar Jul 19 '12 at 8:08
You haven't answered JPvdMerwe's question about division. Must it be exact? Can intermediate results be non-integral? – Peter Taylor Jul 19 '12 at 11:11

# Ruby, 456 438 408 390 370 349 344 334 [fixed]

``````g={}
f=->a,b{a.permutation(b).to_a.uniq.flatten.each_slice b}
F,T=\$*
([F.to_i,10].max..T.to_i).map{|c|f[a="#{c}".split(''),v=a.size].map{|m|f[[?+,?-,?*,?/,'','**'],v-1].map{|w|(d=(s=m.zip(w)*'').size)==v&&next
0.upto(d){|y|y.upto(d+1){|u|begin(r=eval t="#{s}".insert(y,?().insert(u,?)))==c&&g[r]=t
rescue Exception
end}}}}}
p g.size,g
``````

Output:

``````% ruby ./friedman-numbers.rb 1 300
9
{25=>"(5)**2", 121=>"(11)**2", 125=>"5**(2+1)", 126=>"(6)*21", 127=>"(2)**7-1", 128=>"2**(8-1)", 153=>"(3)*51", 216=>"6**(1+2)", 289=>"(9+8)**2"}
``````

Also it works relatively fast for larger numbers:

``````% time ruby friedman-numbers.rb 3863 3864
1
{3864=>"(6**4-8)*3"}
ruby friedman-numbers.rb 3863 3864  14.05s user 0.17s system 99% cpu 14.224 total
``````
-
I ran it with the input `5 40` and got the result: `[11, "11**1", 21, "21**1", 31, "31**1", 41, "41**1"]`. No sign of `25` in there and I think the right solution (for example for `21`) is `2*1`, not `21**1` – w0lf Jul 20 '12 at 10:21
@w0lf Thank you! I think I've fixed it. – Artem Ice Jul 20 '12 at 12:38
Yes, it works great now. – w0lf Jul 20 '12 at 13:10
@w0lf added a lot of characters to format output as required – Artem Ice Jul 20 '12 at 13:12
you can gain 2 chars by replacing `'+-*/'.chars.to_a+['','**']` with `["+","-","*","/","","**"]` – w0lf Jul 20 '12 at 13:42

### Python 2.7 - 380 378 372 371 367 363 357 354 352 348 336 chars

Just a simple brute force search.

``````from itertools import*
s=lambda x:[x]['1'>x>'0':]+['(%s%s%s)'%f for i in range(1,len(x))for f in product(s(x[:i]),'*/-+^',s(x[i:]))]
def E(e):
try:return eval(e.replace("^","**"))
except:0
A={i:e for i in range(input(),input()+1)for x in permutations(`i`)for e in s("".join(x))[x>='1':]if E(e)==i}
print len(A)
for v in A:print v,A[v]
``````

### Example run:

``````1
300
9
128 (2^(8-1))
289 ((9+8)^2)
216 (6^(1+2))
121 (11^2)
153 (3*51)
25 (5^2)
125 (5^(2+1))
126 (6*21)
127 ((2^7)-1)
``````

### Explanation:

`s(x)` is a function that takes a string containing a sequence of digits and returns all expressions using those digits in that order.

`[x]['1'>x>'0':]` evaluates to a list containing x if x is '0' or a sequence of digits not starting with '0'; otherwise, it evaluates to an empty list. Basically this handles the case where I join all the digits together.

`['(%s%s%s)'%f for i in range(1,len(x))for f in product(s(x[:i]),'*/-+^',s(x[i:]))]` basically partitions x into two parts (both being of non-zero length), calls s() on each part and joins all the results together with some operator between them, by using product().

`E(e)` is basically a safe eval. It returns the value of e if e is valid and None otherwise.

``````A={i:e for i in range(input(),input()+1)for x in permutations(`i`)for e in s("".join(x))[x>='1':]if E(e)==i}
``````

Basically this code tries all the numbers in the range, permutes their digits and tests each expression s() generates for that permutation, ignoring the first expression if x doesn't start with '0', because if x doesn't start with '0' then the first expression will just be x.

### Alternate version - 397 chars

Here is my code if you are required to use fractions:

``````from fractions import*
from itertools import*
s=lambda x:["Fraction(%s)"%x]['1'>x>'0':]+['(%s%s%s)'%f for i in range(1,len(x))for f in product(s(x[:i]),'*/-+^',s(x[i:]))]
def E(e):
try:return eval(e.replace("^","**"))
except:0
A={i:e for i in range(input(),input()+1)for x in permutations(`i`)for e in s("".join(x))[x>='1':]if E(e)==i}
print len(A)
for v in A:print v,A[v].replace("Fraction","")
``````
-
I don't think `if len(x)<2` will ever be true in function `s`. Also, you can replace your `format` with `"a[Fraction(%s)%s%s]='(%s%s%s)'"%(x[:i],o,v,x[:i],o,A)` to save 4 characters. – beary605 Jul 19 '12 at 15:16
@beary605: It is true sometimes, when i=len(x)-1, then the next call will get a single char. As for the second point, thanks! :) – JPvdMerwe Jul 19 '12 at 17:56
huh... `except:0` smart.. very smart. I'll remember – Ev_genus Jul 19 '12 at 21:38
Please include some illustrative output. – David Carraher Jul 20 '12 at 11:13
Nope, still running. I have to move my PC now, but I will let it run for a few days and see if it finishes. – JPvdMerwe Jul 22 '12 at 16:52

### Python3 (436)(434) (443)

It was hard. I can spare some characters if I make output more native.

``````from itertools import*
r={};k=product;m=map
q=lambda n,h=1:["("+i+c+j+")"for(i,j),c in k(chain(*[k(*m(q,f))for f in sum(([(x[:q],x[q:])for q in range(1,len(x))]for x in m("".join,permutations(n))),[])]),list("+-*/^")+[""]*h)]if 1<len(n)else[n]*h
a,b=m(int,m(input,"nm"))
for i,j in chain(*[k(q(str(n),0),[n])for n in range(a,b+1)]):
try:exec("if eval(%r)==j:r[j]=i"%i.replace("^","**"))
except:0
print(len(r))
for j,i in r.items():print(i,j)
``````

Output

``````n100
m200
6
(2^(8-1)) 128
(3*(51)) 153
((11)^2) 121
(5^(1+2)) 125
(6*(21)) 126
((2^7)-1) 127
``````
-
So you have a lot of clever tricks; however, I should mention you don't handle 1 to 9 correctly and your input isn't inclusive. You can remove 2 chars though by removing the space after `"("+i+c+j+")"` and replacing `len(n)>1` by `1<len(n)` after which you can remove the space after that expression. – JPvdMerwe Jul 20 '12 at 7:55
Fair. Fixed all, +7 characters – Ev_genus Jul 20 '12 at 10:41
You can replace the last line by `for j in r:print(r[j],j)` to save 7 chars. – JPvdMerwe Jul 20 '12 at 11:20

# Mathematica 456416402404400 396 chars

``````<< Combinatorica`; l = Length; p = Permutations; f = Flatten; c = Cases;
u[d_, o_, s_] :=
Fold[#2[[1]] @@ If[s == 1, {#1, #2[[-1]]}, {#2[[-1]], #1}] &,
q[t_, r_] := {u[t, #, r], u[HoldForm /@ t, #, r]} & /@
p[{Plus, Subtract, Times, Divide, Power}, {l@t - 1}];
v[m_, n_] := (t = Table[Union@
c[f[{#~q~1, #~q~0} & /@
f[p /@ c[
FromDigits /@ # & /@
f[SetPartitions /@ p@IntegerDigits@j, 1], x_ /; l@x > 1],
1], 2], {j, _}], {j, m, n}]~f~1; {l@t}~Join~t)
``````

Example:

``````v[1,300]//TableForm
``````

Output:

-