# Thread: Beginner Programming Challenge #10

1. ## Re: Beginner Programming Challenge #10

Originally Posted by Some Penguin
The entries already posted tend to reject numbers that are palindromes.
from wikipedia:
A Lychrel number is a natural number which cannot form a palindrome through the iterative process of repeatedly reversing its base 10 digits and adding the resulting numbers.
the way i read that is that the entries already posted are doing the right thing.

2. ## Re: Beginner Programming Challenge #10

i modified the code to use some of the in-built scheme functions, like reverse and equal?. this shortens the code considerably but also introduces an element of cargo-cult programming.

Code:
```(define reverse-chain reverse)

(define num->chain
(lambda (num)
(if (< num 10)
(list num)
(cons (remainder num 10) (num->chain (quotient num 10))))))

(define empty-chain? null?)

(lambda (c1 c2)
(num->chain (+ (chain->num c1) (chain->num c2)))))

(define chain->num
(lambda (chain)
(if (null? chain)
0
(+ (car chain) (* 10 (chain->num (cdr chain)))))))

(define same-chain? equal?)

(define is-palindrome?
(lambda (n)
(same-chain? n (reverse-chain n))))

(define find-lychrel-seeds
(lambda (limit max-tries)

(define iterate
(lambda (chain)

(define is-lychrel-number?
(lambda (chain try return)
(cond ((> try max-tries)
'())
((and (> try 0) (is-palindrome? chain))
(return (chain->num chain)))
(else
(cons (chain->num chain) (is-lychrel-number? (iterate chain) (+ try 1) return))))))

(define loop
(lambda (number results)
(if (< number limit)
(let ((result (call/cc (lambda (k) (is-lychrel-number? (num->chain number) 0 k)))))
(if (list? result)
(loop (+ 1 number) (cons result results))
(loop (+ 1 number) results)))
(reverse results))))

(define get-first-elements
(lambda (ll)
(if (null? ll)
'()
(cons (car (car ll)) (get-first-elements (cdr ll))))))

(let ((lychrel-numbers (loop 1 '())))

(define my-list-test?
(lambda (in1 in2 pred?)
(let loop ((obj1 in1)
(obj2 in2))
(cond ((null? obj1) #f)
((pred? (car obj1) obj2) #t)
(else (loop (cdr obj1) obj2))))))

(define in-list?
(lambda (l elem)
(my-list-test? l elem =)))

(lambda (list-of-lists l2)
(my-list-test? list-of-lists l2 same-seed?)))

(define same-seed?
(lambda (l1 l2)
(cond ((null? l1) #f)
((in-list? l2 (car l1)) #t)
(else
(same-seed? (cdr l1) l2)))))

(define inner-loop
(lambda (seed-list lychrel-list)
(cond ((null? lychrel-list) seed-list)
(inner-loop seed-list (cdr lychrel-list)))
(else (inner-loop (cons (car lychrel-list) seed-list) (cdr lychrel-list))))))

(let ((lychrel-seed-lists (inner-loop '() lychrel-numbers)))

(cons (get-first-elements lychrel-numbers) (list (reverse (get-first-elements lychrel-seed-lists))))))))

(display (find-lychrel-seeds 10000 40))
(newline)```
--edit--
okay, i've modified the code to also return palindromes which are lychrel candidates.
Last edited by howlingmadhowie; March 8th, 2010 at 11:02 AM. Reason: modified the code

3. ## Re: Beginner Programming Challenge #10

the way i read that is that the entries already posted are doing the right thing.
I thought so too. Can clarification be added please if we are wrong?

-Silver Fox

4. Iced Almond Soy Ubuntu, No Foam
Join Date
Nov 2009
Beans
1,081

## Re: Beginner Programming Challenge #10

http://www.p196.org/lychrel%20records.html

Well, if you go by that -- 9999 is a suspected Lychrel number, tested to over 60M iterations. The question is whether it can form a palindrome by that process -- going zero iterations does not appear to be permitted.

5. ## Re: Beginner Programming Challenge #10

from wikipedia:

the way i read that is that the entries already posted are doing the right thing.
Seed numbers are a subset of Lychrel numbers, that is the smallest number of each non palindrome producing thread. A seed number may be a palindrome itself. The first three examples are shown in bold in the list above.
Since a seed is necessarily a Lychrel number and may be a palindrome itself, a palindrome seed would be a palindrome Lychrel number.

6. ## Re: Beginner Programming Challenge #10

Originally Posted by Bachstelze
Since a seed is necessarily a Lychrel number and may be a palindrome itself, a palindrome seed would be a palindrome Lychrel number.
i think op means that we should take something like 9999 to be a lychrel candidate, so we have to change our code to start checking after one iteration.

7. ## Re: Beginner Programming Challenge #10

i think op means that we should take something like 9999 to be a lychrel candidate, so we have to change our code to start checking after one iteration.

8. ## Re: Beginner Programming Challenge #10

i think op means that we should take something like 9999 to be a lychrel candidate, so we have to change our code to start checking after one iteration.
That is accurate if you are saying one iteration of the 196-algorithm.
Last edited by cprofitt; March 8th, 2010 at 01:41 PM.

9. ## Re: Beginner Programming Challenge #10

I'm working on mine.
It's in python and I'm not sure on how accurate is it yet.
It's a quite difficult challenge.

It's taking about 6 seconds to run up to 10000 and it finds lots of numbers, I'm not sure if they are all Lychrel candidates.
I'll try again latter.

10. ## Re: Beginner Programming Challenge #10

Originally Posted by Marlonsm
I'm working on mine.
It's in python and I'm not sure on how accurate is it yet.
It's a quite difficult challenge.

It's taking about 6 seconds to run up to 10000 and it finds lots of numbers, I'm not sure if they are all Lychrel candidates.
I'll try again latter.
You can look at howlingmadhowie's and my entries to check your results.