9
\$\begingroup\$

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.

\$\endgroup\$
  • 2
    \$\begingroup\$ Can you add some example Friedman numbers and explain how / works? For instance what is 1/3? \$\endgroup\$ – JPvdMerwe Jul 19 '12 at 7:10
  • \$\begingroup\$ 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 \$\endgroup\$ – elssar Jul 19 '12 at 7:11
  • \$\begingroup\$ Do you allow unary minus? e.g -5? \$\endgroup\$ – JPvdMerwe Jul 19 '12 at 7:41
  • \$\begingroup\$ @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 \$\endgroup\$ – elssar Jul 19 '12 at 8:08
  • 1
    \$\begingroup\$ You haven't answered JPvdMerwe's question about division. Must it be exact? Can intermediate results be non-integral? \$\endgroup\$ – Peter Taylor Jul 19 '12 at 11:11
3
\$\begingroup\$

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
\$\endgroup\$
  • 1
    \$\begingroup\$ 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 \$\endgroup\$ – Cristian Lupascu Jul 20 '12 at 10:21
  • \$\begingroup\$ @w0lf Thank you! I think I've fixed it. \$\endgroup\$ – defhlt Jul 20 '12 at 12:38
  • \$\begingroup\$ Yes, it works great now. \$\endgroup\$ – Cristian Lupascu Jul 20 '12 at 13:10
  • \$\begingroup\$ @w0lf added a lot of characters to format output as required \$\endgroup\$ – defhlt Jul 20 '12 at 13:12
  • \$\begingroup\$ you can gain 2 chars by replacing '+-*/'.chars.to_a+['','**'] with ["+","-","*","/","","**"] \$\endgroup\$ – Cristian Lupascu Jul 20 '12 at 13:42
4
\$\begingroup\$

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","")
\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – beary605 Jul 19 '12 at 15:16
  • \$\begingroup\$ @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! :) \$\endgroup\$ – JPvdMerwe Jul 19 '12 at 17:56
  • \$\begingroup\$ huh... except:0 smart.. very smart. I'll remember \$\endgroup\$ – Ev_genus Jul 19 '12 at 21:38
  • \$\begingroup\$ Please include some illustrative output. \$\endgroup\$ – DavidC Jul 20 '12 at 11:13
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – JPvdMerwe Jul 22 '12 at 16:52
3
\$\begingroup\$

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
\$\endgroup\$
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – JPvdMerwe Jul 20 '12 at 7:55
  • \$\begingroup\$ Fair. Fixed all, +7 characters \$\endgroup\$ – Ev_genus Jul 20 '12 at 10:41
  • \$\begingroup\$ You can replace the last line by for j in r:print(r[j],j) to save 7 chars. \$\endgroup\$ – JPvdMerwe Jul 20 '12 at 11:20
1
\$\begingroup\$

Mathematica 456 416 402 404 400 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}] &, 
 d[[1]], Thread@{o, Rest@d}];
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:

friedman output

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.