Un nombre de Friedman est un nombre qui peut être exprimé en appliquant des opérations mathématiques de base (^, /, *, +, -) à tous ses chiffres. Les opérations n'ont pas besoin d'être appliquées à chaque chiffre individuel, mais tous les chiffres doivent être impliqués. Autrement dit, 121 = 11 ^ 2 -> tous les chiffres sont impliqués, mais 1 et 1 ont été groupés ensemble pour faire 11.

L'utilisation de parenthèses est autorisée, mais la solution triviale x= (x)n'est pas une solution valide. Pas non plus valable, x= +x.

Exemples

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

Écrivez un programme qui prendra deux entiers positifs et imprimera le nombre de nombres de Friedman dans cette plage (inclus), et les nombres avec les expressions dans les lignes suivantes.

Contribution -

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

Production -

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

Le code le plus court publié le dimanche 29 juillet à minuit GMT sera le gagnant.

Rubis, 456 438 408 390 370 349 344 334 [fixe]

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

Production:

% 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"}

De plus, cela fonctionne relativement rapidement pour de plus grands nombres:

% 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

Python 2,7 - 380 378 372 371 367 363 357 354 352 348 336 caractères

Juste une simple recherche de force brute.

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]

Exemple d'exécution:

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)

Explication:

s(x) est une fonction qui prend une chaîne contenant une séquence de chiffres et renvoie toutes les expressions utilisant ces chiffres dans cet ordre.

[x]['1'>x>'0':] évalue à une liste contenant x si x est «0» ou une séquence de chiffres ne commençant pas par «0»; sinon, il évalue à une liste vide. Fondamentalement, cela gère le cas où je joins tous les chiffres ensemble.

['(%s%s%s)'%f for i in range(1,len(x))for f in product(s(x[:i]),'*/-+^',s(x[i:]))] partitionne essentiellement x en deux parties (les deux étant de longueur non nulle), appelle s () sur chaque partie et joint tous les résultats avec un opérateur entre eux, en utilisant product ().

E(e) est fondamentalement un eval sûr. Il renvoie la valeur de e si e est valide et None sinon.

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}

Fondamentalement, ce code essaie tous les nombres de la plage, permute leurs chiffres et teste chaque expression que s () génère pour cette permutation, ignorant la première expression si x ne commence pas par '0', parce que si x ne commence pas par ' 0 'alors la première expression sera simplement x.

Version alternative - 397 caractères

Voici mon code si vous devez utiliser des 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","")

Python3 (436) (434) (443)

C'était difficile. Je peux épargner certains caractères si je rend la sortie plus 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)

Production

n100
m200
6
(2^(8-1)) 128
(3*(51)) 153
((11)^2) 121
(5^(1+2)) 125
(6*(21)) 126
((2^7)-1) 127

Mathematica 456 416 402 404 400 396 caractères

<< 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)

exemple :

v[1,300]//TableForm

Sortie :