## Lychrel Numbers

### September 1, 2015

Let `r`

(*n*) be the function that reverses the digits of the number *n*, and let `s`

(*n*) = *n* + `r`

(*n*); for instance, `r`

(281) = 182 and `s`

(281) = 281 + 182 = 463. Repeatedly applying `s`

to the result of `s`

(*n*) frequently leads to a palindrome; for instance, starting with *n* = 281, `s`

(281) = 463, `s`

(463) = 827, `s`

(827) = 1555, `s`

(1555) = 7106, `s`

(7106) = 13123, and `s`

(13123) = 45254, which is a palindrome. There are some numbers, such as 196, that apparently *don’t* lead to palindromes; these numbers are called Lychrel numbers (A023108), and we say apparently because no one knows if there might be a palindrome if the computation is continued sufficiently far. It is conjectured that there are an infinite number of Lychrel numbers.

Your task is to write a function that determines if a number appears to be a Lychrel number and, if not, returns the chain of numbers that shows it is not. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

In Python.

In Scala.

Checks until 1000000000L

I hope that my understanding is correct what chain of numbers was required.

F# solution:

190L is not Lychrel number -> 45254L

191L is not Lychrel number -> 191L

192L is not Lychrel number -> 6996L

193L is not Lychrel number -> 233332L

194L is not Lychrel number -> 2992L

195L is not Lychrel number -> 9339L

Lychrel number -> 196L

197L is not Lychrel number -> 881188L

198L is not Lychrel number -> 79497L

199L is not Lychrel number -> 3113L

200L is not Lychrel number -> 202L

201L is not Lychrel number -> 303L

202L is not Lychrel number -> 202L

203L is not Lychrel number -> 505L

204L is not Lychrel number -> 606L

205L is not Lychrel number -> 707L

206L is not Lychrel number -> 808L

207L is not Lychrel number -> 909L

208L is not Lychrel number -> 1111L

209L is not Lychrel number -> 1111L

210L is not Lychrel number -> 222L

211L is not Lychrel number -> 323L

212L is not Lychrel number -> 212L

213L is not Lychrel number -> 525L

214L is not Lychrel number -> 626L

215L is not Lychrel number -> 727L

216L is not Lychrel number -> 828L

217L is not Lychrel number -> 929L

218L is not Lychrel number -> 1331L

219L is not Lychrel number -> 2442L

220L is not Lychrel number -> 242L

221L is not Lychrel number -> 343L

222L is not Lychrel number -> 222L

223L is not Lychrel number -> 545L

224L is not Lychrel number -> 646L

225L is not Lychrel number -> 747L

226L is not Lychrel number -> 848L

227L is not Lychrel number -> 949L

228L is not Lychrel number -> 1551L

229L is not Lychrel number -> 2662L

230L is not Lychrel number -> 262L

231L is not Lychrel number -> 363L

232L is not Lychrel number -> 232L

233L is not Lychrel number -> 565L

234L is not Lychrel number -> 666L

235L is not Lychrel number -> 767L

236L is not Lychrel number -> 868L

237L is not Lychrel number -> 969L

238L is not Lychrel number -> 1771L

239L is not Lychrel number -> 2882L

240L is not Lychrel number -> 282L

241L is not Lychrel number -> 383L

242L is not Lychrel number -> 242L

243L is not Lychrel number -> 585L

244L is not Lychrel number -> 686L

245L is not Lychrel number -> 787L

246L is not Lychrel number -> 888L

247L is not Lychrel number -> 989L

248L is not Lychrel number -> 1991L

249L is not Lychrel number -> 5115L

250L is not Lychrel number -> 505L

251L is not Lychrel number -> 707L

252L is not Lychrel number -> 252L

253L is not Lychrel number -> 1111L

254L is not Lychrel number -> 4444L

255L is not Lychrel number -> 6666L

256L is not Lychrel number -> 8888L

257L is not Lychrel number -> 11011L

258L is not Lychrel number -> 1221L

259L is not Lychrel number -> 2332L

260L is not Lychrel number -> 545L

261L is not Lychrel number -> 747L

262L is not Lychrel number -> 262L

263L is not Lychrel number -> 2662L

264L is not Lychrel number -> 4884L

265L is not Lychrel number -> 45254L

266L is not Lychrel number -> 88555588L

267L is not Lychrel number -> 13431L

268L is not Lychrel number -> 1441L

269L is not Lychrel number -> 2552L

270L is not Lychrel number -> 585L

271L is not Lychrel number -> 787L

272L is not Lychrel number -> 272L

273L is not Lychrel number -> 5115L

274L is not Lychrel number -> 9559L

275L is not Lychrel number -> 44044L

276L is not Lychrel number -> 8836886388L

277L is not Lychrel number -> 15851L

278L is not Lychrel number -> 1661L

279L is not Lychrel number -> 2772L

280L is not Lychrel number -> 2662L

281L is not Lychrel number -> 45254L

282L is not Lychrel number -> 282L

283L is not Lychrel number -> 2552L

284L is not Lychrel number -> 4774L

285L is not Lychrel number -> 6996L

286L is not Lychrel number -> 8813200023188L

287L is not Lychrel number -> 233332L

288L is not Lychrel number -> 1881L

289L is not Lychrel number -> 2992L

290L is not Lychrel number -> 2552L

291L is not Lychrel number -> 6996L

292L is not Lychrel number -> 292L

293L is not Lychrel number -> 2992L

294L is not Lychrel number -> 9339L

Lychrel number -> 295L

296L is not Lychrel number -> 881188L

297L is not Lychrel number -> 79497L

298L is not Lychrel number -> 3113L

299L is not Lychrel number -> 5335L

300L is not Lychrel number -> 303L

Haskell:

Somebody asked how to compute Lychrel numbers in Python at Stack Overflow today, and I wrote this program:

I’ve been getting in to monad programming lately, so here’s a solution that defines a “bounded computation” monad and then uses that to limit the length of sequence we look at. It’s a bit longer than Francesco’s solution above (but it does terminate for input eg. of 196):

Here’s one in Racket:

(define string-reverse (compose list->string reverse string->list))

(define (string-palindrome? s) (equal? (string-reverse s) s))

(define (f n) (+ n (string->number (string-reverse (number->string n)))))

(define (lychrel? n [tolerance 10000])

(let loop ([n n] [result (list n)] [i 1])

(if (>= i tolerance)

#t

(if (string-palindrome? (number->string n))

result

(let ([y (f n)]) (loop y (append result (list y)) (+ i 1)))))))

Apologies, I forgot to enclose that in source code tags!

Here’s another Haskell solution – to save some effort, perform all calculations on lists of digits, rather than the numbers themselves. We just need some conversions and an add with carry function (smallest digit comes first in the list representation):

#include

int main()

{

int num,rev=0,num1,val=0;

printf(“Enter the number\n”);

scanf(“%d”,&num);

num1 = num;

while(1)

{

for(;num1;val = val*10+num1%10,num1/=10);

if(num==val)

{

printf(“we get the num -> %d\n”,num);

break;

}

printf(“num become -> %d\n”,num);

num1 = num+val;

num = num1;

val=0;

}

}

O/P:

Enter the number

281

num become -> 281

num become -> 463

num become -> 827

num become -> 1555

num become -> 7106

num become -> 13123

Enter the number

261

num become -> 261

num become -> 423

we get the num -> 747

Enter the number

731

num become -> 731

we get the num -> 868

you can enter any number you will get it’s corresponding palindrome number