Le Monde puzzle [#809]

Another number theory puzzle, completed in the plane to Hamburg:

Integers n are called noble if they can be decomposed as a sum n=a+b+… of distinct integers such that 1/a+1/b+…=1. They are called bourgeois if 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 called villeins. Find all nobles less than 60. And characterise villeins.

Again 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.

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

From 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 language="(1,4,9,10,11,16,24)"][/c]=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))}

This 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

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