The reverse-then-add sequence

Arjen Markus (7 june 2012) It is just one of those vexing questions: why does the number 196 behave so differently from most other numbers in the following algorithm:

Take a number, say 167 and reverse the digits (yielding: 761)
Add these two (yielding: 928)
If the result is not a palindrome (that is: reversing the digits gives the same number), then do it again
After a while the result is a palindrome

If you do this for the number 196, you are in for trouble: even after several million or even billion steps, no palindrome pops up. There are quite a few numbers that behave that way, but 196 is the smallest. (See: The 196 algorithm for more details)

The program below illustrates this:

# p196.tcl --
#     Program to illustrate a vexing problem:
#     The number 196 behaves differently than most others in the
#     reverse-and-add algorithm
#
#

proc isPalindrome {number} {

    set reverse [string reverse $number]

return [expr {$reverse eq $number? 1 :  0}] }

proc nextNumber {number} {

    set reverse [string trimleft [string reverse $number] 0]

    return [expr {$reverse + $number}]
}

# Print the series that lead to the palindrome for "13", "76", "167", "196"
#
foreach n {13 76 167} {

    puts "Start: $n"
    while { ! [isPalindrome $n] } {
        set n [nextNumber $n]
        puts "    ... $n"
    }
    puts "Palindrome: $n"
}

#
# 196 is the smallest Lychrel number
#
set n 196

set iteration 0
puts "Start: $n"
while { ! [isPalindrome $n] && $iteration < 100 } {
    incr iteration
    set n [nextNumber $n]
    puts "    ... $n"
}
puts "No palindromic output is known!"

It produces the following output:

Start: 13
    ... 44
Palindrome: 44
Start: 76
    ... 143
    ... 484
Palindrome: 484
Start: 167
    ... 928
    ... 1757
    ... 9328
    ... 17567
    ... 94138
    ... 177287
    ... 960058
    ... 1810127
    ... 9020308
    ... 17050517
    ... 88555588
Palindrome: 88555588
Start: 196
    ... 887
    ... 1675
    ... 7436
    ... 13783
    ... 52514
    ... 94039
    ... 187088
    ... 1067869
    ... 10755470
    ... 18211171
    ... 35322452
    ... 60744805
    ... 111589511
    ... 227574622
    ... 454050344
    ... 897100798
    ... 1794102596
    ... 8746117567
    ... 16403234045
    ... 70446464506
    ... 130992928913
    ... 450822227944
    ... 900544455998
    ... 1800098901007
    ... 8801197801088
    ... 17602285712176
    ... 84724043932847
    ... 159547977975595
    ... 755127757721546
    ... 1400255515443103
    ... 4413700670963144
    ... 8827391431036288
    ... 17653692772973576
    ... 85191620502609247
    ... 159482241005228405
    ... 664304741147513356
    ... 1317620482294916822
    ... 3603815405135183953
    ... 7197630720180367016
    ... 13305261530450734933
    ... 47248966933966985264
    ... 93507933867933969538
    ... 177104867844767940077
    ... 947154635293536341848
    ... 1795298270686072793597
    ... 9749270977546801719568
    ... 18408442064004592449047
    ... 92502871604050616929528
    ... 175095833209091234750057
    ... 925153265399993573340628
    ... 1751196640799987135692157
    ... 9264161958699957602603728
    ... 17537224026299926194218357
    ... 92918473189299188236491928
    ... 175837936477498486373973857
    ... 934217310162393261013712428
    ... 1758434620324786522027424867
    ... 9442681822581660752291773438
    ... 17786453745152322604573635887
    ... 96640091285774647759309104658
    ... 182280281681549295517528109327
    ... 906182107397142240703710191608
    ... 1712373124704184482497411473217
    ... 8836114272647029296571625205388
    ... 17671139534403958504034349321776
    ... 85383533877444544434477942439447
    ... 159876958854887988978955775977805
    ... 668656536414767878767414635656756
    ... 1326313072829535757534829271313622
    ... 3589444802113893332894111974449853
    ... 7178889593228875666877224058899706
    ... 13258878097456662332665448018788423
    ... 45747659181913285659330927106673654
    ... 91385319354816681317562845302348408
    ... 171869639709643252636224690693706727
    ... 899477035806065888888571598630674898
    ... 1797953072701241777777132207161449896
    ... 8787394689723559555548553279865047867
    ... 16474800379447118011108106559729985745
    ... 71233793175007298122189281057030833206
    ... 131467596250025596244378551114170566423
    ... 456132667661181469687074071166866330554
    ... 911166336322351940474038252333632562208
    ... 1713431572655604770948087405557266223327
    ... 8946658200210652579438861471120017566498
    ... 17893315300422394267788614031240046132996
    ... 87816479304635435956564863353640397472867
    ... 164643958609270772803130816807280794934745
    ... 712083455691979390834439093880187654281206
    ... 1314265912473067781768877187859384208661423
    ... 4555933937312655599557549065463126404285554
    ... 9111757983526301209015109021025263797681108
    ... 17123625957151502418030218042061517695252227
    ... 89348885628667526499233299462576693647884398
    ... 178697760268335052998466598925153376306768796
    ... 876565363941686582894131498175687238374565667
    ... 1643130837774473154788262996461373387738131345
    ... 7074449215608204801780891870975118165118444806
    ... 13158897331226320592562872742059146230247889513
    ... 44757771534490515617290699271561508443627774644
No palindromic output is known!

Category Mathematics