Lychrel numbers
You are encouraged to solve this task according to the task description, using any language you may know.
- Take an integer n, greater than zero.
- Form the next n of its series by reversing the digits of the current n and adding the result to the current n.
- Stop when n becomes palindromic - i.e. the digits of n in reverse order == n.
The above recurrence relation when applied to most starting numbers n = 1, 2, ... terminates in a palindrome quite quickly, for example if n0 = 12 we get
12 12 + 21 = 33, a palindrome!
And if n0 = 55 we get
55 55 + 55 = 110 110 + 011 = 121, a palindrome!
Notice that the check for a palindrome happens after an addition.
Some starting numbers seem to go on forever; the recurrence relation for 196 has been calculated for millions of repetitions forming numbers with millions of digits, without forming a palindrome. These numbers that do not end in a palindrome are called Lychrel numbers.
For the purposes of this task a Lychrel number is any starting number that does not form a palindrome within 500 (or more) iterations.
- Seed and related Lychrel numbers
Any integer produced in the sequence of a Lychrel number is also a Lychrel number.
In general, any sequence from one Lychrel number might converge to join the sequence from a prior Lychrel number candidate; for example the sequences for the numbers 196 and then 689 begin:
196 196 + 691 = 887 887 + 788 = 1675 1675 + 5761 = 7436 7436 + 6347 = 13783 13783 + 38731 = 52514 52514 + 41525 = 94039 ... 689 689 + 986 = 1675 1675 + 5761 = 7436 ...
So we see that the sequence starting with 689 converges to, and continues with the same numbers as that for 196. Because of this we can further split the Lychrel numbers into true Seed Lychrel number candidates, and Related numbers that produce no palindromes but have integers in their sequence seen as part of the sequence generated from a lower Lychrel number.
- Task
- Find the number of seed Lychrel number candidates and related numbers for n in the range 1..10000 inclusive. (With that iteration limit of 500).
- Print the number of seed Lychrels found; the actual seed Lychrels; and just the number of relateds found.
- Print any seed Lychrel or related number that is itself a palindrome.
Show all output here.
- References
- What's special about 196? Numberphile video.
- A023108 Positive integers which apparently never result in a palindrome under repeated applications of the function f(x) = x + (x with digits reversed).
- Status of the 196 conjecture? Mathoverflow.
FreeBASIC
<lang freebasic>' version 13-09-2015 ' compile with: fbc -s console
' iteration limit
- Define max_it 500
' the highest number to be tested
- Define max_number_to_test 10000
Dim As String num, rev Dim As String temp(), store()
Dim As Integer x, x1, palindrome Dim As UInteger it, s, carry, sum, match, seed, related Dim As UInteger num2test, p_count, lychrel_palindrome()
For num2test = 1 To max_number_to_test
num = Str(num2test)
rev = num : s = Len(num) - 1
For x = 0 To s
rev[s - x] = num[x]
Next
' if num = rev then palindrome = -1 else palindrome = 0
' palindrome is set to the result of the compare of num and rev
palindrome = (num = rev)
it = 0
ReDim temp(1 To max_it)
Do
carry = 0
For x = s To 0 Step -1 'add the two numbers
sum = num[x] + rev[x] + carry
If sum > (9 + 48 + 48) Then
num[x] = sum - 10 - 48
carry = 1
Else
num[x] = sum - 48
carry = 0
End If
Next
If carry = 1 Then num = "1" + num
it = it + 1 : temp(it) = num
rev = num : s = Len(num) - 1
For x = 0 To s
rev[s - x] = num[x]
Next
Loop Until num = rev OrElse it = max_it
If it = max_it Then
match = 0
' if it's palindrome then save the number
If palindrome <> 0 Then
p_count = p_count + 1
ReDim Preserve lychrel_palindrome(1 To p_count)
lychrel_palindrome(p_count) = num2test
End If
For x = 1 To seed ' check against previous found seed(s)
For x1 = max_it To 1 Step -1
If store(x, 1) = temp(x1) Then
match = 1
related = related + 1
Exit For, For
Else
If Len(store(x,1)) > Len(temp(x1)) Then
Exit For
End If
End If
Next
Next
' no match found then it's a new seed, store it
If match = 0 Then
seed = seed + 1
ReDim Preserve store(seed, 1)
store(seed, 0) = Str(num2test)
store(seed, 1) = temp(max_it)
End If
End If
Next
Print Print " Testing numbers: 1 to "; Str(max_number_to_test) Print " Iteration maximum: ";Str(max_it) Print Print " Number of Lychrel seeds: "; seed Print " Lychrel number: "; For x = 1 To seed : Print store(x,0); " "; : Next : Print Print " Number of relateds found: "; related Print " Lychrel numbers that are palindromes: "; p_count Print " Lychrel palindromes: "; For x = 1 To p_count : Print lychrel_palindrome(x); " "; : Next : Print Print
' empty keyboard buffer While Inkey <> "" : Var _key_ = Inkey : Wend Print : Print "hit any key to end program" Sleep End</lang>
- Output:
Testing numbers: 1 to 10000
Iteration maximum: 500
Number of Lychrel seeds: 5
Lychrel number: 196 879 1997 7059 9999
Number of relateds found: 244
Lychrel numbers that are palindromes: 3
Lychrel palindromes: 4994 8778 9999
Go
<lang go>package main
import ( "flag" "fmt" "math" "math/big" "os" )
var maxRev = big.NewInt(math.MaxUint64 / 10) // approximate var ten = big.NewInt(10)
// Reverse sets `result` to the value of the base ten digits of `v` in // reverse order and returns `result`. // Only handles positive integers. func reverseInt(v *big.Int, result *big.Int) *big.Int { if v.Cmp(maxRev) <= 0 { // optimize small values that fit within uint64 result.SetUint64(reverseUint64(v.Uint64())) } else { if true { // Reverse the string representation s := reverseString(v.String()) result.SetString(s, 10) } else { // This has fewer allocations but is slower: // Use a copy of `v` since we mutate it. v := new(big.Int).Set(v) digit := new(big.Int) result.SetUint64(0) for v.BitLen() > 0 { v.QuoRem(v, ten, digit) result.Mul(result, ten) result.Add(result, digit) } } } return result }
func reverseUint64(v uint64) uint64 { var r uint64 for v > 0 { r *= 10 r += v % 10 v /= 10 } return r }
func reverseString(s string) string { b := make([]byte, len(s)) for i, j := 0, len(s)-1; j >= 0; i, j = i+1, j-1 { b[i] = s[j] } return string(b) }
var known = make(map[string]bool)
func Lychrel(n uint64, iter uint) (isLychrel, isSeed bool) { v, r := new(big.Int).SetUint64(n), new(big.Int) reverseInt(v, r) seen := make(map[string]bool) isLychrel = true isSeed = true for i := iter; i > 0; i-- { str := v.String() if seen[str] { //log.Println("found a loop with", n, "at", str) isLychrel = true break } if ans, ok := known[str]; ok { //log.Println("already know:", str, ans) isLychrel = ans isSeed = false break } seen[str] = true
v = v.Add(v, r) //log.Printf("%v + %v = %v\n", str, r, v) reverseInt(v, r) if v.Cmp(r) == 0 { //log.Println(v, "is a palindrome,", n, "is not a Lychrel number") isLychrel = false isSeed = false break } } for k := range seen { known[k] = isLychrel } //if isLychrel { log.Printf("%v may be a Lychrel number\n", n) } return isLychrel, isSeed }
func main() { max := flag.Uint64("max", 10000, "search in the range 1..`N` inclusive") iter := flag.Uint("iter", 500, "limit palindrome search to `N` iterations") flag.Parse() if flag.NArg() != 0 { flag.Usage() os.Exit(2) }
fmt.Printf("Calculating using n = 1..%v and %v iterations:\n", *max, *iter) var seeds []uint64 var related int var pals []uint64 for i := uint64(1); i <= *max; i++ { if l, s := Lychrel(i, *iter); l { if s { seeds = append(seeds, i) } else { related++ } if i == reverseUint64(i) { pals = append(pals, i) } } }
fmt.Println(" Number of Lychrel seeds:", len(seeds)) fmt.Println(" Lychrel seeds:", seeds) fmt.Println(" Number of related:", related) fmt.Println("Number of Lychrel palindromes:", len(pals)) fmt.Println(" Lychrel palindromes:", pals) }</lang>
- Output:
Calculating using n = 1..10000 and 500 iterations:
Number of Lychrel seeds: 5
Lychrel seeds: [196 879 1997 7059 9999]
Number of related: 244
Number of Lychrel palindromes: 3
Lychrel palindromes: [4994 8778 9999]
J
Reverse digits:
<lang J>revdig=:('x',~|.)&.":"0</lang>
Note that we need extended precision numbers because 500 iterations gets us into very large numbers even when we start small. For example, starting from 12:
<lang J> (+revdig)^:500(12) 989330226271793404132120335101444022368928728236373385750622261099268167362912850818170039990942038798808908830140199820181718948328173760873880172226156484473632718819962221534191534021132404387162721132989</lang>
Test whether a number is a lychrel (true or related) number within that 500 iteration limit:
<lang J>lychrel500=: (~: revdig)@((+^:~: revdig)^:500)@(+revdig)"0</lang>
Number of these lychrel numbers not exceeding 10000 (we start from 0 here, because that's natural for J's primitives, so we need 10001 integers if we are to reach 10000):
<lang J> #L=:I.lychrel500 i.10001 249</lang>
(What are they? Note that this isn't a task requirement - just curiosity.)
<lang J> 3 83$L
196 295 394 493 592 689 691 788 790 879 887 978 986 1495 1497 1585 1587 1675 1677 1765 1767 1855 1857 1945 1947 1997 2494 2496 2584 2586 2674 2676 2764 2766 2854 2856 2944 2946 2996 3493 3495 3583 3585 3673 3675 3763 3765 3853 3855 3943 3945 3995 4079 4169 4259 4349 4439 4492 4494 4529 4582 4584 4619 4672 4674 4709 4762 4764 4799 4852 4854 4889 4942 4944 4979 4994 5078 5168 5258 5348 5438 5491 5493
5528 5581 5583 5618 5671 5673 5708 5761 5763 5798 5851 5853 5888 5941 5943 5978 5993 6077 6167 6257 6347 6437 6490 6492 6527 6580 6582 6617 6670 6672 6707 6760 6762 6797 6850 6852 6887 6940 6942 6977 6992 7059 7076 7149 7166 7239 7256 7329 7346 7419 7436 7491 7509 7526 7581 7599 7616 7671 7689 7706 7761 7779 7796 7851 7869 7886 7941 7959 7976 7991 8058 8075 8079 8089 8148 8165 8169 8179 8238 8255 8259 8269 8328 8345 8349 8359 8418 8435 8439 8449 8490 8508 8525 8529 8539 8580 8598 8615 8619 8629 8670 8688 8705 8709 8719 8760 8778 8795 8799 8809 8850 8868 8885 8889 8899 8940 8958 8975 8979 8989 8990 9057 9074 9078 9088 9147 9164 9168 9178 9237 9254 9258 9268 9327 9344 9348 9358 9417 9434 9438 9448 9507 9524 9528 9538 9597 9614 9618 9628 9687 9704 9708 9718 9777 9794 9798 9808 9867 9884 9888 9898 9957 9974 9978 9988 9999</lang>
To figure out which of these lychrel numbers were "true" lychrel numbers, we will need to work with sequences of sums seeded from these numbers. So let's just find those sequences:
<lang J> S=:(+revdig)^:(i.501)"0 L</lang>
And, let's take a peek at some of the numbers in these sequences (the first 10 values in each lychrel sequence, starting from the first lychrel candidate seeds):
<lang J> 10 10 {.S 196 887 1675 7436 13783 52514 94039 187088 1067869 10755470 295 887 1675 7436 13783 52514 94039 187088 1067869 10755470 394 887 1675 7436 13783 52514 94039 187088 1067869 10755470 493 887 1675 7436 13783 52514 94039 187088 1067869 10755470 592 887 1675 7436 13783 52514 94039 187088 1067869 10755470 689 1675 7436 13783 52514 94039 187088 1067869 10755470 18211171 691 887 1675 7436 13783 52514 94039 187088 1067869 10755470 788 1675 7436 13783 52514 94039 187088 1067869 10755470 18211171 790 887 1675 7436 13783 52514 94039 187088 1067869 10755470 879 1857 9438 17787 96558 182127 903408 1707717 8884788 17759676</lang>
So most of these are related... which ones are not? (An integer is owned if it is in the sequence for this lychrel candidate or for any previous candidates. A lychrel candidate is a true lychrel number if none of its sequence is owned by any previous candidate.)
<lang J> owned=: <@~.@,\S
#T=: (-. (<"1 S) +./@e.&> a:,}:owned)#L
5
T
196 879 1997 7059 9999</lang>
And, with that, we can find the count of "just related" lychrel numbers:
<lang J> L -&# T 244</lang>
And, finally, which of the (true or related) lychrel numbers were themselves palindromes?
<lang J> (#~(=revdig))L 4994 8778 9999</lang>
To reiterate, here's the collected definitions with the task required results (everything above this point was basically just documentation - J tends to need that kind of documentation, because of the nature of the language):
<lang J> revdig=:('x',~|.)&.":"0
lychrel500=: (~: revdig)@((+^:~: revdig)^:500)@(+revdig)"0 L=:I.lychrel500 i.10001 S=:(+revdig)^:(i.501)"0 L owned=: <@~.@,\S #T=: (-. (<"1 S) +./@e.&> a:,}:owned)#L
5
T
196 879 1997 7059 9999
L -&# T
244
(#~(=revdig))L
4994 8778 9999</lang>
T is the "seed" or "true" lychrel numbers, and #T is how many of them we found. L is all of the candidates (both seeds and relateds), so the difference in the lengths of L and T is the number of relateds.
Perl 6
<lang perl6>my @lychrels; my @test; my $count = 0; my $max = 500;
for 1 .. 10000 -> $int {
@lychrels.push( $int => [@test] ) if lychrel($int); $count = 0; @test = ();
sub lychrel (Int $l) {
return True if $count++ > $max;
@test.push: my $m = $l + $l.flip;
return False if $m == $m.flip;
lychrel($m);
}
}
my @palindromes; my @roots = @lychrels[0]; for @lychrels -> $i {
@palindromes.push: $i.key if $i.key == $i.key.flip;
my $trial = 0;
for @roots -> $t {
last if any($t.value) ~~ any($i.value);
$trial++;
}
@roots.push: $i if $trial == +@roots;
}
say " Number of Lychrel seed numbers < 10_000: ", +@roots; say " Lychrel seed numbers < 10_000: ", join ", ", @roots>>.keys; say "Number of Lychrel related numbers < 10_000: ", +@lychrels -@roots; say " Number of Lychrel palindromes < 10_000: ", +@palindromes; say " Lychrel palindromes < 10_000: ", join ", ", @palindromes;</lang>
- Output:
Number of Lychrel seed numbers < 10_000: 5
Lychrel seed numbers < 10_000: 196, 879, 1997, 7059, 9999
Number of Lychrel related numbers < 10_000: 244
Number of Lychrel palindromes < 10_000: 3
Lychrel palindromes < 10_000: 4994, 8778, 9999
PicoLisp
<lang PicoLisp>(de pali? (N)
(let N (chop N)
(= N (reverse N)) ) )
(de lychrel (A)
(let
(R NIL
Lst
(make
(for X A
(let (N X C 500)
(while
(and
(inc 'N (format (flip (chop N))))
(gt0 (dec 'C))
(not (pali? N)) ) )
(and (=0 C) (link X) ) ) ) )
Lst22
(by
'((N)
(let (X N C 3)
(prog1
(bool
(or
(member (+ N (format (flip (chop N)))) R)
(find
'((N) (member N R))
(make
(do C
(link (inc 'X (format (flip (chop X))))) ) ) ) ) )
(do C
(push1
'R
(inc 'N (format (flip (chop N)))) ) ) ) ) )
group
Lst )
P (filter pali? Lst) )
(prinl
"Using n = 1..10000 and limiting each search to 500 reverse-digits-and-adds" )
(prinl
" Number of Lychrel numbers: "
(length (car Lst22)) )
(prin " Lychrel numbers: ")
(println (car Lst22))
(prinl
" Number of Lychrel related: "
(length (cadr Lst22)) )
(prinl
" Number of Lychrel palindroms: "
(length P) )
(prin " Lychrel palindromes: ")
(println P) ) )
(lychrel 10000)
(bye)</lang>
- Output:
Using n = 1..10000 and limiting each search to 500 reverse-digits-and-adds
Number of Lychrel numbers: 5
Lychrel numbers: (196 879 1997 7059 9999)
Number of Lychrel related: 244
Number of Lychrel palindroms: 3
Lychrel palindromes: (4994 8778 9999)
Python
<lang python>from __future__ import print_function
def add_reverse(num, max_iter=1000):
i, nums = 0, {num}
while True:
i, num = i+1, num + reverse_int(num)
nums.add(num)
if reverse_int(num) == num or i >= max_iter:
break
return nums
- @functools.lru_cache(maxsize=2**20)
def reverse_int(num):
return int(str(num)[::-1])
def split_roots_from_relateds(roots_and_relateds):
roots = roots_and_relateds[::]
i = 1
while i < len(roots):
this = roots[i]
if any(this.intersection(prev) for prev in roots[:i]):
del roots[i]
else:
i += 1
root = [min(each_set) for each_set in roots]
related = [min(each_set) for each_set in roots_and_relateds]
related = [n for n in related if n not in root]
return root, related
def find_lychrel(maxn, max_reversions):
'Lychrel number generator' series = [add_reverse(n, max_reversions*2) for n in range(1, maxn + 1)] roots_and_relateds = [s for s in series if len(s) > max_reversions] return split_roots_from_relateds(roots_and_relateds)
if __name__ == '__main__':
maxn, reversion_limit = 10000, 500
print("Calculations using n = 1..%i and limiting each search to 2*%i reverse-digits-and-adds"
% (maxn, reversion_limit))
lychrel, l_related = find_lychrel(maxn, reversion_limit)
print(' Number of Lychrel numbers:', len(lychrel))
print(' Lychrel numbers:', ', '.join(str(n) for n in lychrel))
print(' Number of Lychrel related:', len(l_related))
#print(' Lychrel related:', ', '.join(str(n) for n in l_related))
pals = [x for x in lychrel + l_related if x == reverse_int(x)]
print(' Number of Lychrel palindromes:', len(pals))
print(' Lychrel palindromes:', ', '.join(str(n) for n in pals))</lang>
- Output:
Calculations using n = 1..10000 and limiting each search to 2*500 reverse-digits-and-adds
Number of Lychrel numbers: 5
Lychrel numbers: 196, 879, 1997, 7059, 9999
Number of Lychrel related: 244
Number of Lychrel palindromes: 3
Lychrel palindromes: 9999, 4994, 8778
If we test the numbers in ascending order, many of them would have been encountered when checking smaller numbers (i.e. 10 is seen when testing 5), caching them causes a large performance boost, more so with larger ranges. <lang python>from __future__ import print_function
def rev(n): return int(str(n)[::-1])
def lychel(n, cache = {}):
if n in cache: return cache[n]
n0, r = n, rev(n)
res, seen = (True, n), []
for i in range(1000):
n += r
r = rev(n)
if n == r:
res = (False, 0)
break
if n in cache:
res = cache[n]
break
seen.append(n)
for x in seen: cache[x] = res return res
seeds, related, palin = [], [], []
for i in range(1, 1000000):
tf, s = lychel(i) if not tf: continue (seeds if i == s else related).append(i) if i == rev(i): palin.append(i)
print("%d Lychel seeds:"%len(seeds), seeds) print("%d Lychel related" % len(related)) print("%d Lychel palindromes:" % len(palin), palin)</lang>
Racket
<lang racket>#lang racket (require racket/splicing)
(define (reverse-digits_10 N)
(let inr ((n N) (m 0))
(match n
[0 m]
[(app (curryr quotient/remainder 10) q r)
(inr q (+ r (* 10 m)))])))
(define (palindrome?_10 n)
(= n (reverse-digits_10 n)))
- hash of integer? -> one of 'seed 'related #f
(splicing-let ((memo# (make-hash)))
(define (generate-lychrel?-chain i i-rev n acc)
(cond
[(zero? n) ; out of steam
(cons 'seed acc)]
[else
(let* ((i+ (+ i i-rev)) (i+-rev (reverse-digits_10 i+)))
(cond
[(= i+ i+-rev) ; palindrome breaks the chain
(cons #f acc)]
[(eq? 'related (hash-ref memo# i+ #f)) ; deja vu
(cons 'related acc)]
[else ; search some more
(generate-lychrel?-chain i+ i+-rev (sub1 n) (cons i+ acc))]))]))
;; returns 'seed, 'related or #f depending of the Lychrel-ness of a number
(define (lychrel-number? i #:n (n 500))
(match (hash-ref memo# i 'unfound)
['unfound
(match (generate-lychrel?-chain i (reverse-digits_10 i) n null)
[(cons 'related chain) 'related]
[(cons (and seed (or (and 'seed (app (λ (_) 'related) related?))
(and #f (app (λ (_) #f) related?))))
chain)
(for ((c (in-list chain))) (hash-set! memo# c related?))
(hash-set! memo# i seed)
seed])]
[seed/related/false seed/related/false])))
(module+ main
(define-values (seeds/r n-relateds palindromes/r)
(for/fold ((s/r null) (r 0) (p/r null))
((i (in-range 1 (add1 10000))))
(define lych? (lychrel-number? i))
(define p/r+ (if (and lych? (palindrome?_10 i)) (cons (list i (list lych?)) p/r) p/r))
(match lych?
['seed (values (cons i s/r) r p/r+)]
['related (values s/r (add1 r) p/r+)]
[#f (values s/r r p/r+)])))
(printf #<<EOS
Seed Lychrel numbers: ~a count:~a Related Lychrel numbers: count:~a Palindromic Lychrel numbers: ~a~% EOS
(reverse seeds/r) (length seeds/r) n-relateds (reverse palindromes/r)))</lang>
- Output:
Seed Lychrel numbers: (196 879 1997 7059 9999) count:5 Related Lychrel numbers: count:244 Palindromic Lychrel numbers: ((4994 (related)) (8778 (related)) (9999 (seed)))
REXX
<lang rexx>/*REXX program finds and displays Lychrel numbers, related #s, and palindromes*/ numeric digits 5000 /*ensure enough decimal digits for adds*/ limit=500*2 /*limit: number of Lychrel iterations.*/ parse arg high . /*obtain the optional argument from CL.*/ if high= | high==',' then high=10000 /*Not specified? Then use the default.*/ T.=.; @.=.; c=; $=; #.=; w=length(high) /*W is used for output.*/ p=
do j=1 for high; call Lychrel j; end /*j*/
do k=1 for high; rk=reverse(k) if #.k==1 then $=$ k /*build a list of Lychrel numbers. */ if T.k==1 then c=c k /* " " " " " related nums.*/ if T.k==1 & k==rk then p=p k /* " " " " " palindromes. */ end /*j*/
say 'For the range 1 to' high", and limiting each search to" limit 'steps:' say say right(words($) ,w) 'Lychrel numbers were found:' $ say right(words(c)-words($),w) 'Lychrel related numbers were found.' say right(words(p) ,w) 'Lychrel palindromes:' p exit /*stick a fork in it, we're all done. */ /*────────────────────────────────────────────────────────────────────────────*/ Lychrel: procedure expose limit @. #. T.; parse arg x 1 z /*set X&Z to arg 1*/
rels=0 /*# related nums (so far)*/
do limit; z=z+reverse(z) /*add reverse of Z ··· */
if z==reverse(z) then return /*Not palindromic? Skip.*/
rels=rels+1; !.rels=z /*add to related numbers.*/
end /*k*/
#.x=1
T.x=1; do a=1 for rels; _=!.a /*process related numbers*/
if @._==1 then #.x=3 /*unmark it for Lychrel. */
@._=1; T._=1 /*mark number as related.*/
end /*a*/
return</lang>
output when using the default inputs:
For the range 1 to 10000, and limiting each search to 1000 steps:
5 Lychrel numbers were found: 196 879 1997 7059 9999
244 Lychrel related numbers were found.
3 Lychrel palindromes: 4994 8778 9999
Rust
This uses the num library for arbitrary-sized integer support as normal integers will overflow.
Cargo.toml
[package] name = "lychrel" version = "0.1.0" authors = ["monsieursquirrel"] [dependencies] num = "0.1.27"
src/main.rs <lang rust>extern crate num; use num::FromPrimitive; use num::bigint::BigInt;
use std::collections::HashSet;
/// Reverse a number then add it to the original. fn rev_add(num: &BigInt) -> BigInt {
let rev_string: String = num.to_string().chars().rev().collect(); // should be safe, our string is guaranteed to be a number let rev_val: BigInt = rev_string.parse().unwrap(); num + rev_val
}
/// Check if a number is a palindrome when written in base 10. fn is_palindrome(num: &BigInt) -> bool {
let num_string = num.to_string(); let rev_string: String = num_string.chars().rev().collect(); let comp_len = num_string.len() / 2; num_string[0..comp_len] == rev_string[0..comp_len]
}
/// Perform a lychrel test on a number, stopping after max_tests /// Returns the sequence of numbers if this number is a lychrel, None otherwise. fn test_lychrel(num: &BigInt, max_tests: usize) -> Option<Vec<BigInt>> {
let mut sequence = Vec::<BigInt>::new();
let is_lychrel = (0..max_tests)
.scan(num.clone(), |current, _| {
*current = rev_add(current);
Some(current.clone())
})
.inspect(|current| sequence.push(current.clone()))
.filter(|curent| is_palindrome(curent))
.next()
.is_none();
if is_lychrel {
Some(sequence)
}
else {
None
}
}
/// Determine if the sequence for a lychrel number is related to a previously seen sequence fn is_related(seq: &Vec<BigInt>, lychrel_seq_numbers: &HashSet<BigInt>) -> bool {
seq.iter().filter(|num| lychrel_seq_numbers.contains(num)).next().is_some()
}
/// Find the lychrel numbers up to max_num (inclusive). /// Returns a tuple (lychrel numbers, related numbers, palindrome lychrel/related numbers) fn find_lychrels(max_num: u64, max_tests: usize) -> (Vec<BigInt>, Vec<BigInt>, Vec<BigInt>) {
// storage for various outputs let mut lychrels = Vec::<BigInt>::new(); let mut relateds = Vec::<BigInt>::new(); let mut palindrome_lychrels = Vec::<BigInt>::new();
let mut lychrel_seq_numbers: HashSet<BigInt> = HashSet::new();
for i in (1..(max_num + 1)) {
let num = FromPrimitive::from_u64(i).unwrap();
let maybe_lychrel = test_lychrel(&num, max_tests);
if let Some(lychrel_seq) = maybe_lychrel {
// it's a lychrel - check if it's a related number
let related = is_related(&lychrel_seq, &lychrel_seq_numbers);
// update our sequences
for seq_num in lychrel_seq.into_iter() {
lychrel_seq_numbers.insert(seq_num);
}
if !related {
// the number has a new lychrel sequence, store it
lychrels.push(num.clone());
}
else {
// just count it as a related number
relateds.push(num.clone());
}
if is_palindrome(&num) {
// doesn't matter if palindromes are related or not
palindrome_lychrels.push(num.clone());
}
}
}
(lychrels, relateds, palindrome_lychrels)
}
fn print_nums(before: &str, numbers: &Vec<BigInt>) {
print!("{}", before);
for (i, current) in numbers.iter().enumerate() {
print!("{}", current);
if i + 1 < numbers.len() {
print!(", ");
}
}
println!("");
}
fn main() {
let max_num: u64 = 10_000; let max_tests: usize = 500;
println!("Calculations using n = 1..{} and limiting each search to {} reverse-digits-and-adds",
max_num, max_tests);
let (lychrels, relateds, palindrome_lychrels) = find_lychrels(max_num, max_tests);
println!("Number of Lychrel numbers: {}", lychrels.len());
print_nums("Lychrel numbers: ", &lychrels);
println!("Number of Lychrel related: {}", relateds.len());
println!("Number of Lychrel palindromes: {}", palindrome_lychrels.len());
print_nums("Lychrel palindromes: ", &palindrome_lychrels);
}</lang>
- Output:
Calculations using n = 1..10000 and limiting each search to 500 reverse-digits-and-adds Number of Lychrel numbers: 5 Lychrel numbers: 196, 879, 1997, 7059, 9999 Number of Lychrel related: 244 Number of Lychrel palindromes: 3 Lychrel palindromes: 4994, 8778, 9999
Tcl
As we collect Lychrel numbers, we can save some time by storing all the members of their orbits in a hash table so that related numbers can be quickly identified. This is what the $visited variable is for: using the keys of a dictionary (or on earlier Tcl versions, an array) for a hash table is a common trick in Tcl. Native bignums mean we don't have to worry about overflow
<lang Tcl>proc pal? {n} {
expr {$n eq [string reverse $n]}
}
proc step {n} {
set n_ [string reverse $n]
set n_ [string trimleft $n_ 0]
expr {$n + $n_}
}
proc lychrels {{max 10000} {iters 500}} {
set lychrels {} ;# true Lychrels
set visited {} ;# visited numbers for Related test
set nRelated 0 ;# count of related numbers seen
set pals {} ;# palindromic Lychrels and related
puts "Searching for Lychrel numbers in \[1,$max\]" puts "With a maximum of $iters iterations"
for {set i 1} {$i <= $max} {incr i} {
set n $i ;# seed the sequence
set seq {} ;# but don't check the seed, nor remember it for the Related test
for {set j 0} {$j < $iters} {incr j} {
set n [step $n]
dict set seq $n {}
if {[dict exists $visited $n]} {
incr nRelated
if {[pal? $i]} {
lappend pals $i
}
break ;# bail out if it's Related
}
if {[pal? $n]} {
break ;# bail out if it's a palindrome
}
}
if {$j >= $iters} { ;# the loop was exhausted: must be a Lychrel!
if {[pal? $i]} {
lappend pals $i
}
lappend lychrels $i
set visited [dict merge $visited $seq]
}
}
puts "[llength $lychrels] Lychrel numbers found:" puts $lychrels puts "Count of related numbers: $nRelated" puts "Palindromic Lychrel and related numbers: $pals"
}
lychrels</lang>
- Output:
Searching for Lychrel numbers in [1,10000] With a maximum of 500 iterations 5 Lychrel numbers found: 196 879 1997 7059 9999 Count of related numbers: 244 Palindromic Lychrel and related numbers: 4994 8778 9999
zkl
Uses the GNU GMP big int library.
The Lychrel number chain is stored as a long string with '\0' separating each number, which we can then search to find relateds. <lang zkl>var BN=Import("zklBigNum");
// 192-->"887\01675\07436\013783\0..." ~60k bytes
fcn lychrel(n,returnListof=False){ n=BN(n); //-->Bool|Data(==StringBuf)
sink:=(if(returnListof) Data(0,String) else Void);
nls:=(500).pump(sink,'wrap(){
ns:=n.add(BN(n.toString().reverse())).toString();
if(ns==ns.reverse()) return(Void.Stop,False); // not a Lychrel number
ns
});
if(nls) if(returnListof) return(sink.mode(Int).howza(2)) else return(True);
False;
} fcn isPalindrome(n){ n==n.toString().reverse().toInt() } fcn findSeeds(lychrels){
seeds:=List(lychrels[0]);
foreach n,lnns in ([1..].zip(lychrels[1,*])){ ln,seq:=lnns;
foreach _,s2 in (seeds){
foreach s3 in (seq){ if(Void!=(z:=s2.findString(s3)) and 0==s2[z-1]) break(2); }
}
fallthrough{ seeds.append(lnns) }
}
seeds.apply("get",0)
}</lang> <lang zkl>lychrels:=[1..0d10_000].filter(lychrel).apply(fcn(n){ T(n,lychrel(n,True)) }); println("[1..10,000] contains ",lychrels.len()," Lychrel numbers.");
lychrels.pump(List,fcn([(n,_)]){ isPalindrome(n) and n or Void.Skip })
.println("<-- Palindromic Lychrel numbers");
(n:=findSeeds(lychrels)) .println("<-- Lychrel seeds (%d) ==> %d related" .fmt(n.len(),lychrels.len() - n.len()));</lang>
- Output:
[1..10,000] contains 249 Lychrel numbers. L(4994,8778,9999)<-- Palindromic Lychrel numbers L(196,879,1997,7059,9999)<-- Lychrel seeds (5) ==> 244 related