## Le Monde puzzle [#809]

**A**nother number theory puzzle, completed in the plane to Hamburg:

Integers n are callednobleif they can be decomposed as a sum n=a+b+… of distinct integers such that 1/a+1/b+…=1. They are calledbourgeoisif they are not noble but can be decomposed as a sum n=a+b+… of integers, some of them identical, such that 1/a+1/b+…=1. If neither noble nor bourgeois, they are calledvilleins. Find all nobles less than 60. And characterise villeins.

**A**gain a case where writing a brute-force R code seems harder than solving the problem on a piece of paper… However, a mix could make the best of both worlds. It is rather straightforward to see that if n is not a villein, then 2n+2 is not a villein (moving from 1/2+1/2=1 to 1/2(1/n)+1/2=1). Similarly for 3n+6 (9=3+3+3), 4n+6 (10=4+4+2), 6n+5 (2+3+6=11). Each new decomposition brings a whole series of non-villeins. Another path is to remark that products keep the property: if a and b are non-villeins, so is ab, a², b², 2(a+b), and actually all products of the form m(m+a-1) for any integer m. Starting with the most basic solutions (1,4,9,10,11), we can then repeat the application of all those rules until no new non-villein is exposed.

**H**ere is my R code for finding some decompositions with 4 and 5 terms (since there are only one or two decompositions with one (1), two (2+2) and three (2+3+6, 3+3+3): I first define a function checking for a decomposition with no numerical error *[(sum(1/deco)==1) does not work!]:*

inva=function(deco){ numerat=0 for (i in 1:length(deco)) numerat=numerat+prod(deco[-i]) return((numerat==prod(deco)))}

then check for 4

reve4=NULL a=c(2,2,2,2) while ((a[1]<5)&&(sum(a)<626)){ while ((sum(1/a[-4])>=1)&&(sum(a)<626)) a[3:4]=rep(a[3]+1,2) a[4]=max(a[3],trunc(1/(1-sum(1/a[-4])))-1) while ((sum(1/a)>1)&&(sum(a)<626)) a[4]=a[4]+1 if (inva(a)) reve4=rbind(reve4,a) if ((sum(1/a[-4])+1/a[3]>1)&&(sum(a)<625)){ a[3:4]=rep(a[3]+1,2)}else{ b=rep(a[2]+1,3) if (a[1]+sum(b)<625){ a=c(a[1],b)}else{a=rep(a[1]+1,4) }} }

and 5 term decompositions:

reve5=NULL a=rep(2,5) while ((a[1]<5)&&(sum(a)<626)){ while ((sum(1/a[-5])>=1)&&(sum(a)<626)) a[4:5]=rep(a[4]+1,2) a[5]=max(a[4],trunc(1/(1-sum(1/a[-5])))-1) while ((sum(1/a)>1)&&(sum(a)<626)) a[5]=a[5]+1 if (inva(a)) reve5=rbind(a,reve5) if ((sum(1/a[-5])+1/a[4]>1)&&(sum(a)<624)){ a[4:5]=rep(a[4]+1,2)}else{ b=rep(a[3]+1,3) if (sum(a[1:2])+sum(b)<625){a=c(a[1:2],b)}else{ b=rep(a[2]+1,4) if (a[1]+sum(b)<625){a=c(a[1],b)}else{ a=rep(a[1]+1,5) }}} }

**F**rom there, we have a basis on which we can fill a 25×25 table of further non-villeins, applying the above rules:

nob=rep(0,25^2) nob[c(1,4,9,10,11,16,24)]=1 nob[apply(reve4,1,sum)]=1 nob[apply(reve5,1,sum)]=1 ref=1 newref=sum(nob) while (newref>ref){ for (i in (1:25^2)[nob==1]){ if (i<26) nob[i^2]=1 if (2*i+2<625) nob[2*i+2]=1 if (2*i+9<626) nob[2*i+9]=1 if (3*i+6<626) nob[3*i+6]=1 if (4*i+6<626) nob[4*i+6]=1 if (6*i+5<626) nob[6*i+5]=1 for (m in 2:25) if (m*(m+i-1)<626) nob[m*(m+i-1)]=1} ref=newref;newref=sum(nob) image(1:25,1:25,matrix(nob,25))}

**T**his produces two false villeins, namely 47 and 103, since all numbers larger than 24 are non-villeins: Since both 47 and 103 are prime numbers, using other product rules would not change anything to the result. An extra R code looking at all possible decompositions of those numbers into sums would show them as false villeins. Or moving to 6 term decompositions since 47 = 3+4+8+8+12+12. Here is a small random search:

a=c(3,rep(2,23)) N=47 while (!inva(a)){ b=sample(2:N,1) a0=c(b,N-sum(b)) while (sum(1/a0)<1){ b=sample(2:(N-sum(a0[-length(a0)])),1) a0=c(a0[-length(a0)],b) a0=c(a0,N-sum(a0))} a=a0}

which returns 47 =4+6+20+6+5. And 103=40+35+8+14+2+4

**I**nteresting features of this problem are that (a) it appears fairly frequently in the mathematical games literature, like the Olympiads, see e.g. this resolution incl. the proof about 24 as the upper limit to the existence of villeins, (b) the name of those integers varies from case to case, like good integers, and (c) the denomination of noble integers is used in mathematics for “irrational numbers having a continued fraction representation that becomes an infinite sequence of 1s at some point“.* (There was also a very similar question on stack exchange a few weeks ago but I cannot trace it…)*

February 23, 2013 at 1:55 pm

The solution published in Le Monde of yesterday evening was disappointing, with no higher mathematical principle or notion than the enumeration by the rule 2n+2, 3n+6, &tc. No novelty when compared with this earlier resolution.

February 22, 2013 at 2:49 pm

Christian/Thanks a lot for reminding us the good old days we were struggling with a couple of colleagues at inra and elsewhere with “Le Monde” logic games.

Here is the simple way I found to generate noble integers < or = to 60.

Start with 1/2 + 1/2 =1

Now use the equality 1/m=[1/(m+1)]+[1/m(m+1)] and apply it to 1/2

You get 1/2 + 1/3 + 1/6 =1 and n=2+3+6=11

In 1/2 + 1/3 + 1/6 replace 1/3 by 1/4 + 1/12 so that you get 1/2 + 1/4 + 1/6 +1/12 =1

and n=2+4+6+12=24

In 1/2 + 1/3 + 1/6 replace 1/6 by 1/7 + 1/42 so that you get 1/2 + 1/3 + 1/7 +1/42 =1

and n=2+3+7+42=54

In 1/2 + 1/4 + 1/6 +1/12 replace 1/4 by 1/5 by 1/20 so that you get 1/2 + 1/5 + 1/6 +1/12 + 1/20=1

and n=2+5+6+12+20=45

But, I do not know if this is an exhaustive list of these numbers.

JL Foulley

February 22, 2013 at 3:23 pm

Merci! Il y en a d’autres effectivement: 30,31,32,37,43,50,55…