vv - Posts - MaplePrimes

Putnam Mathematical Competition 2018...

Posted: vv 11977 Product: Maple

December 08 2018

4 5

Maple can solve the easiest two problems of the Putnam Mathematical Competition 2018. link

Problem A1

Find all ordered pairs (a,b) of positive integers for which 1/a + 1/b = 3/2018

>	eq:= 1/a + 1/b = 3/2018;

(1)

>	isolve(%);

(2)

>	# Unfortunalely Maple fails to find all the solutions; eq must be simplified first!

>	(lhs-rhs)(eq);

(3)

>

numer(%);

(4)

>	s:=isolve(%);

(5)

>	remove(u ->(eval(a,u)<=0 or eval(b,u)<=0),[s]);

(6)

>	# Now it's OK.

Problem B1

Consider the set of vectors P = { < a, b> : 0 ≤ a ≤ 2, 0 ≤ b ≤ 100, a, b in Z}.
Find all v in P such that the set P \ {v} can be partitioned into two sets of equal size and equal sum.

>	n:=100: P:= [seq(seq([a,b],a=0..2), b=0..n)]:

>	k:=nops(P): s:=add(P): numsols:=0:

>

for i to k do
  v:=P[i]; sv:=s-v;
  if irem(sv[1],2)=1 or irem(sv[2],2)=1 then next fi;
  cond:=simplify(add( x[j]*~P[j],j=1..k))-sv/2;
  try
    sol:=[];
    sol:=Optimization:-Minimize
         (0, {x[i]=0, (cond=~0)[], add(x[i],i=1..k)=(k-1)/2 }, assume=binary);
    catch:
  end try:
  if sol<>[] then numsols:=numsols+1;
     print(v='P'[i], select(j -> (eval(x[j],sol[2])=1), {seq(1..k)})) fi;
od:
'numsols'=numsols;

(7)

>

Download putnam2018.mw

Edit.
Maple can be also very useful in solving the difficult problem B6; it can be reduced to compute the (huge) coefficient of x^1842 in the polynomial

g := (1 + x + x^2 + x^3 + x^4 + x^5 + x^9)^2018;

The computation is very fast:

coeff(g, x, 1842): evalf(%);
0.8048091229e1147

A useful exercise for Maple programmers...

Posted: vv 11977 Product: Maple

October 04 2018

2 10

The Maple help contains a nice example of a puzzle solver named alphametic, see ?Iterator,Permute.
The goal is to determine the distinct digits represented by letters which satisfy a given equation. The provided solved example is:

"16540*781 = 12904836 + 12904"
i.e. m=1, a=6, p=5 etc.

It's worth studying the program (written as a module) because it includes a few useful techniques.
I would suggest the following exercise for a Maple (young) programmer.

1. When solving the "classical" puzzle "FORTY+TEN+TEN=SIXTY", instead of the correct answer "29786+850+850=31486", you will see
"2978Y+850+850=3148Y".
Try to find what's going on and correct the code.

2. The solutions given by alphametic include numbers beginning with a zero.
Execute e.g. .
Modify the code to produce only standard numbers.

Great Hall Floor and Maple...

Posted: vv 11977 Product: Maple

September 01 2018

12 5

I have recently visited the Queen's House at Greenwich (see wiki), an important building in British architectural history (17th century).
I was impressed by the Great Hall Floor, whose central geometric decoration seems to be generated by a Maple program :-)

Here is my code for this. I hope you will like it.

restart;
with(plots): with(plottools):
n:=32: m:=3:#    n:=64: m:=7:

a[0], b[0] := exp(-Pi*I/n), exp(Pi*I/n):
c[0]:=b[0]+(a[0]-b[0])/sqrt(2)*exp(I*Pi/4):  
for k to m+1 do  
  c[k]:=a[k-1]+b[k-1]-c[k-1];
  b[k]:=c[k]*(1+exp(2*Pi*I/n))-b[k-1];
  a[k]:=conjugate(b[k])  od:
b[-1]:=c[0]*(1+exp(2*Pi*I/n))-b[0]:
a[-1]:=conjugate(b[-1]):
c[-1]:=a[-1]+b[-1]-c[0]:
seq( map[inplace](evalf@[Re,Im], w), w=[a,b,c] ):
Q:=polygonplot([seq([a[k],c[k],b[k],c[k+1]],k=0..m-1), [c[m],a[m],b[m]], [a[-1],b[-1],c[0]]]):
display(seq(rotate(Q, 2*k*Pi/n, [0,0]),k=0..n-1), disk([0,0],c[m][1]/3), axes=none, size=[800,800], color=black);

A limit from an undergraduate competitio...

Posted: vv 11977 Product: Maple

May 17 2018

1 8

At a recent undegraduate competition the students had to compute the following limit

>	Limit( n * Diff( (exp(x)-1)/x, x$n), n=infinity ) assuming x<>0;

Limit(n*(Diff((exp(x)-1)/x, `$`(x, n))), n = infinity)

(1)

Maple is able to compute the symbolic n-fold derivative and I hoped that the limit will be computed at once.

Unfortunately it is not so easy.
Maybe someone finds a more more straightforward way.

>

restart;

>	f := n * diff( (exp(x)-1)/x, x$n );

n*(-1/x)^n*(-GAMMA(n+1)+GAMMA(n+1, -x))/x

(2)

>	limit(%, n=infinity);

limit(n*(-1/x)^n*(-GAMMA(n+1)+GAMMA(n+1, -x))/x, n = infinity)

(3)

>	simplify(%) assuming x>0;

(4)

So, Maple cannot compute directly the limit.

>	convert(f, Int) assuming n::posint;

-n*(-1/x)^n*(-x)^(n+1)*GAMMA(2+n)*(Int(exp(_t1*x)*_t1^n, _t1 = 0 .. 1))/((n+1)*(Int(_k1^n*exp(-_k1), _k1 = 0 .. infinity))*x)

(5)

>	J:=simplify(%) assuming n::posint;

n*(Int(exp(x*_k1)*_k1^n, _k1 = 0 .. 1))*GAMMA(n+1)/(Int(_k1^n*exp(-_k1), _k1 = 0 .. infinity))

(6)

>	L:=convert(J, Int) assuming n::posint;

n*(Int(exp(x*_k1)*_k1^n, _k1 = 0 .. 1))

(7)

>	L:=subs(_k1=u, L);

n*(Int(exp(x*u)*u^n, u = 0 .. 1))

(8)

Now it should be easy, but Maple needs help.

>	with(IntegrationTools):

>	L1:=Change(L, u^n = t, t) assuming n::posint;

Int(exp((x*t^(1/n)*n+ln(t))/n), t = 0 .. 1)

(9)

>	limit(L1, n=infinity); # OK

(10)

>	####################################################################

Note that the limit can also be computed using an integration by parts, but Maple refuses to finalize:

>	Parts(L, exp(u*x)) assuming n::posint;

n*(exp(x)/(n+1)-(Int(u^(n+1)*x*exp(x*u)/(n+1), u = 0 .. 1)))

(11)

>	simplify(%);

n*(-x*(Int(u^(n+1)*exp(x*u), u = 0 .. 1))+exp(x))/(n+1)

(12)

>	limit(%, n=infinity);

limit(n*(-x*(Int(u^(n+1)*exp(x*u), u = 0 .. 1))+exp(x))/(n+1), n = infinity)

(13)

>	value(%); # we are almost back!

limit(n*((-x)^(-n)*(-(n+1)*n*GAMMA(n)/x-(-x)^n*(x-n-1)*exp(x)/x+(n+1)*n*GAMMA(n, -x)/x)+exp(x))/(n+1), n = infinity)

(14)

>

add, floats, and Kahan sum...

Posted: vv 11977 Product: Maple

April 27 2018

3 2

add, floats, and Kahan sum

I found an intresting fact about the Maple command add for floating point values.
It seems that add in this case uses a summation algorithm in order to reduce the numerical error.
It is probably the Kahan summation algorithm (see wiki), but I wonder why this fact is not documented.

Here is a simple Maple procedure describing and implementing the algorithm.

>

restart;

>	Digits:=15;

(1)

>

KahanSum := proc(f::procedure, ab::range)
local S,c,y,t, i;      # https://en.wikipedia.org/wiki/Kahan_summation_algorithm
S := 0.0;              # S = result (final sum: add(f(n), n=a..b))
c := 0.0;              # c = compensation for lost low-order bits.
for i from lhs(ab) to rhs(ab) do
    y := f(i) - c;
    t := S + y;
    c := (t - S) - y;
    S := t;
od;
return S
end proc:

Now, a numerical example.

>	f:= n -> evalf(1/(n+1/n^3+1) - 1/(n+1+1/(n+1)^3+1));

proc (n) options operator, arrow; evalf(1/(n+1/n^3+1)-1/(n+2+1/(n+1)^3)) end proc

(2)

>	n := 50000; K := KahanSum(f, 1..n);

(3)

>	A := add(f(k),k=1..n);

(4)

>	s:=0.0: for i to n do s:=s+f(i) od: 's' = s;

(5)

>	exact:=( 1/3 - 1/(n+1+1/(n+1)^3+1) );

(6)

>	evalf( [errK = K-exact, errA = A-exact, err_for=s-exact] );

(7)

>	evalf[20]( [errK = K-exact, errA = A-exact, err_for=s-exact] );

(8)

>

Download KahanSum.mw

E-Mail Address:
Password:
Remember Me:	Automatically sign in on future visits

E-Mail Address:
Password:
Remember Me:	Automatically sign in on future visits

Ask a Question

Create a Post

vv

11977 Reputation

19 Badges

MaplePrimes Activity

Putnam Mathematical Competition 2018...

A useful exercise for Maple programmers...

Great Hall Floor and Maple...

A limit from an undergraduate competitio...

add, floats, and Kahan sum...

Save this setting as your default sorting preference?

Ask a Question

Create a Post

Generating PDF…

Save this setting as your default sorting preference?
Note: You can change your preference any time in your account settings
Don't show this again