Le compte est bon

et Gonnord aussi

Boite à outils

> selectionne:=proc(l,s)
local res,i;
res:=NULL:
for i to nops(s) do if s[i]=1 then res:=res,l[i] fi od;
RETURN([res])
end:

> mon_convert:=(x,n)->[op(convert(x,base,2)),0$n][1..n];

> mon_convert(5,8);

> somme:=proc(e1,e2)
local i,j,v,res;
res:=NULL;
for i to nops(e1) do for j to nops(e2) do
res:=res,e1[i]+e2[j] od od:
RETURN({res});
end:

> produit:=proc(e1,e2)
local i,j,v,res;
res:=NULL:
for i to nops(e1) do for j to nops(e2) do
res:=res,e1[i]*e2[j] od od:
RETURN({res})
end:

> division:=proc(e1,e2)
local i,j,res,v;
res:=NULL:
for i to nops(e1) do for j to nops(e2) do
v:=e1[i]/e2[j]:
if type(v,integer) then res:=res,v fi od od:
RETURN({res})
end:

> soustraction:=proc(e1,e2)
global resultat;
local i,j,v,res;
res:=NULL;
for i to nops(e1) do for j to nops(e2) do
v:=e1[i]-e2[j]:
if v>0 then res:=res,v fi od od:
RETURN({res})
end:

Programme final (et finaud)

> le_cpte_est_bon:=proc(l)
global cpt;
local p1,pp1,pp2,res,N,e1,e2;
cpt:=cpt+1:N:=nops(l):res:={}:
if N=1 then RETURN({l[1]}) fi;
for p1 to 2^(N-1)-1 do
pp1:=mon_convert(p1,N);pp2:=mon_convert(2^N-1-p1,N);
e1:=le_cpte_est_bon(selectionne(l,pp1)):
e2:=le_cpte_est_bon(selectionne(l,pp2)):
res:=res union e1 union e2 union somme(e1,e2) union produit(e1,e2) union soustraction(e1,e2) union division(e1,e2) union soustraction(e2,e1) union division(e2,e1)
od;
RETURN(res)
end:

Essais

> le_cpte_est_bon([3]);

> le_cpte_est_bon([2,5,5,5,9]);

> le_cpte_est_bon([2,6]);

> le_cpte_est_bon([2,5,5,5,9]);

Version alternative

Pour s'échauffer

> garcia:=proc(l)
local res,i,j,ll;
res:={op(l)}:if nops(l)=1 then RETURN({l[1]}) fi:
for i from 2 to nops(l) do for j to i-1 do
ll:=[l[i]+l[j],op(l[1..j-1]),op(l[j+1..i-1]),op(l[i+1..nops(l)])]:
res:=res union garcia(ll):
od od: RETURN(res) end:

> garcia([10,15]);

> garcia([1,2,3,1515]);

> garcia2:=proc(l)
local res,i,j,ll;
res:={op(l)}:if nops(l)=1 then RETURN({l[1]}) fi:
for i from 2 to nops(l) do for j to i-1 do
ll:=[l[i]+l[j],op(l[1..j-1]),op(l[j+1..i-1]),op(l[i+1..nops(l)])]:
res:=res union garcia2(ll):
ll:=[l[i]*l[j],op(l[1..j-1]),op(l[j+1..i-1]),op(l[i+1..nops(l)])]:
res:=res union garcia2(ll):
od od: RETURN(res) end:

> garcia2([1,2,1515]);

Le programme

> ultimate_garcia:=proc(l)
local res,i,j,ll;
global cpt;
cpt:=cpt+1;
res:={op(l)}:if nops(l)=1 then RETURN({l[1]}) fi:
for i from 2 to nops(l) do for j to i-1 do
ll:=[l[i]+l[j],op(l[1..j-1]),op(l[j+1..i-1]),op(l[i+1..nops(l)])]:
res:=res union ultimate_garcia(ll):
ll:=[l[i]*l[j],op(l[1..j-1]),op(l[j+1..i-1]),op(l[i+1..nops(l)])]:
res:=res union ultimate_garcia(ll):
if l[i] mod l[j]=0 then ll:=[l[i]/l[j],op(l[1..j-1]),op(l[j+1..i-1]),op(l[i+1..nops(l)])]:
res:=res union ultimate_garcia(ll) fi:
if l[j] mod l[i]=0 then ll:=[l[j]/l[i],op(l[1..j-1]),op(l[j+1..i-1]),op(l[i+1..nops(l)])]:
res:=res union ultimate_garcia(ll) fi:
if l[i]>l[j]
then ll:=[l[i]-l[j],op(l[1..j-1]),op(l[j+1..i-1]),op(l[i+1..nops(l)])]:
res:=res union ultimate_garcia(ll)
elif l[j]>l[i] then ll:=[l[j]-l[i],op(l[1..j-1]),op(l[j+1..i-1]),op(l[i+1..nops(l)])]:
res:=res union ultimate_garcia(ll) fi:
od od: RETURN(res) end:

> ultimate_garcia([17,17]);

Essais comparés

> cpt:=0:nops(ultimate_garcia([1,2,1515,101])),cpt;

> cpt:=0:nops(le_cpte_est_bon([1,2,1515,101])),cpt;

> cpt:=0:nops(ultimate_garcia([1])),cpt;cpt:=0:nops(le_cpte_est_bon([1])),cpt;

> cpt:=0:nops(ultimate_garcia([1,2])),cpt;cpt:=0:nops(le_cpte_est_bon([1,2])),cpt;

> cpt:=0:nops(ultimate_garcia([1,2,3])),cpt;cpt:=0:nops(le_cpte_est_bon([1,2,3])),cpt;

> cpt:=0:nops(ultimate_garcia([1,2,3,4])),cpt;cpt:=0:nops(le_cpte_est_bon([1,2,3,4])),cpt;

> cpt:=0:nops(ultimate_garcia([1,3,4])),cpt;cpt:=0:nops(le_cpte_est_bon([1,3,4])),cpt;

> cpt:=0:nops(ultimate_garcia([1,2,3,4,5])),cpt;cpt:=0:nops(le_cpte_est_bon([1,2,3,4,5])),cpt;

> cpt:=0:nops(ultimate_garcia([1,2,3,4,5])),cpt;cpt:=0:nops(le_cpte_est_bon([1,2,3,4,5],0)),cpt;

Warning, computation interrupted

> cpt:=0:nops(le_cpte_est_bon([1,2,3,4,5,6])),cpt;

Complexités

Version Garcia

> c:=n->if n=1 then 1 else n*(n-1)*c(n-1)+1 fi:

Ce calcul ne tient compte que d'une somme et d'un produit. En réalité, il y a parfois des soustractions et des divisions : le coût réel est donc plus important.

> seq(c(k),k=1..10);

> rsolve({ct(1)=1,ct(n)=n*(n-1)*ct(n-1)+1},ct(n));

> equiv:=n->n!*(n-1)!:seq(evalf(c(k)/equiv(k)),k=1..10);

> sum(1/n!/(n-1)!,n=1..infinity);

> evalf(%);

Version Gonnord (plus compliqué... pour une complexité moindre)

> ct:=proc(n) option remember: if n=1 then 1 else 1+add(binomial(n,k)*ct(k),k=1..n-1) fi end:

> seq(ct(n),n=1..10);

Après calcul, la série génératrice phi(z)=sum(ct(n)/n!z^n,n=0..infinity) vaut 1/(2-exp(u))...

> taylor(1/(2-exp(u)),u=0,11);

Un peu de maths : c1(k)=sum(n^k/2^n,n=1..infinity)

> seq(sum(n^k/2^n,n=1..infinity)/2,k=1..10);

> f1:=(n,k)->n^k/2^n:f2:=(n,k)->f1(floor(n),k):

> plot({f1(x,5),f2(x,5)},x=0..15);

Il semblerait que l'intégrale soit équivalente à la somme (un peu en dessus, puis un peu en dessous) ...

> int(f1(n,k),n=0..infinity);

> asympt(%,k);

> expand(%);

Les quatre lignes qui suivent datent d'une feuille Maple version 4... où le calcul de l'intégrale n'était pas réalisé.

> with(student):

Warning, new definition for D

> In:=changevar(n*ln(2)=y,"",y);

> simplify(In);

> assume(k>0):simplify(");

> equiv:=k->k!/ln(2)^(k+1)/2:

> seq(evalf(ct(k)/equiv(k)),k=1..10);

> Digits:=30:seq(evalf(ct(k)/equiv(k)),k=1..30);

Satisfaisant, n'est-il pas ?