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 --&gt; all digits are involved, but 1 &amp; 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&gt;=0, m&gt;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.
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'&gt;x&gt;'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&gt;='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'&gt;x&gt;'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&gt;='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'&gt;x&gt;'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&gt;='1':]if E(e)==i}
print len(A)
for v in A:print v,A[v].replace("Fraction","")