From: ksbrown@ksbrown.seanet.com (Kevin Brown) Newsgroups: can.schoolnet.math.jr,can.schoolnet.math.sr,sci.math Subject: Re: Palindromic Numbers Date: Mon, 19 Feb 1996 18:39:50 GMT Bob Shingleton wrote: > The number 17 is not palindromic, but if its digits are reversed to > give 71, then the sum 17+71=88 which is a palindromic number. The > number 19 needs 2 reversals and additions to become a Palindromic > number 19+91=110, 110+011=121. How many reversals does 89 need? rmorewoo@cln.etc.bc.ca (Robert Morewood) wrote: > I get 24 steps ending with the palindrome: 8813200023188. > ...I followed 196 for 7500 flips (let the computer run all night) > and still no palindrome. Has anyone any idea of how to show it > NEVER gives a palindrome? There's no known proof that any sequence of "digit reversal sums" is palindrome-free when working in base 10. However, it isn't hard to prove the existence of sequences that never produce a palindrome in certain other bases. For example, the smallest number that never becomes palindromic in the base 2 is 10110 (decimal 22). To prove this, first observe that the reverse-sum sequence beginning with 10110 is 10110 100011 1010100 1101001 10110100 etc. The last term quoted above is 10110100, which is of the form 10 [n*1] 01 [n*0] where the symbol [n*x] signifies n consecutive occurences of the digit x. By simple arithmetic we can demonstrate that the reverse-sum sequence beginning with any number of this form proceedes as follows 10 [n*1] 01 [n*0] 11 [(n-2)*0] 1000 [(n-2)*1] 01 10 [n*1] 01 [(n+1)*0] 11 [n*0] 10 [(n-1)*1] 01 10 [(n+1)*1] 01 [(n+1)*0] The last representation is identical to the first, except that n has been replaced by n+1. By induction, it follows that the entire sequence consists of repetitions of this cycle, and none of the elements are palindromes. In the base 4, the number 255 (decimal) leads to a palindrome-free sequence with the following six-step cycle 22 [n*0] 131 [n*3] 12 10 [(n+2)*3] 23 [(n+2)*0] 11 [n*0] 3222 [n*3] 01 22 [n*0] 2111 [n*3] 12 10 [(n+2)*3] 23 [(n+3)*0] 11 [(n+1)*0] 312 [(n+1)*3] 01 22 [(n+1)*0] 131 [(n+1)*3] 12 If a similar sort of argument can be constructed for palindrome-free sequences in the base 10, it would probably be much more complicated, and based on a much longer formal cycle. The smallest numbers leading to palindrome-free sequences in each base from 2 through 19 are listed below (in decimal): 2 22 8 1021 14 361 3 100 9 593 15 447 4 255 10 196 16 413 5 708 11 1011 17 3297 6 1079 12 237 18 519 7 2656 13 2196 19 341 It's interesting that, in each base, all the palindrome-free sequences converge very rapidly on just a small number of sequences. For example, there are 63 decimal numbers less than or equal to 4619 that [evidently] never become palindromic, and these 63 numbers each lead to one of only three palindrome-free sequences. The initial values of these sequences are A B C ------ ------- -------- 887 1857 9988 1675 9438 18887 7436 17787 97768 13783 96558 184547 52514 182127 930028 94039 903408 1750067 187088 1707717 9350638 1067869 8884788 17711177 etc. etc. etc. I suspect these sequence are cyclical (in the sense of the base 2 and base 4 cycles described above), but with irrational periods. Notice that each term in the sequence can be regarded as a sort of "convolution" of the preceeding term, and there are known examples of sequences based on convolution that are cyclical with irrational periods. ===================================================================== MathPages at --> http://www.seanet.com/~ksbrown/ ===================================================================== ============================================================================== From: stl137@aol.com (STL137) Newsgroups: sci.math Subject: Re: numbers, mirror numbers Date: 20 Oct 1998 01:17:13 GMT In binary and hex, it has been proven that some numbers go forever. 196 is an open question in the decimal system. See "Two years of computing" at http://www.fourmilab.ch ------ STL137@aol.com ===> Website: http://members.aol.com/stl137/ PGP keys: ~~~pgp.html Quotes: ~~~quotes.html "I have sworn upon the altar of God eternal hostility against every form of tyranny over the mind of man" - Thomas Jefferson ============================================================================== From: Kurt Foster Newsgroups: sci.math Subject: Re: numbers, mirror numbers Date: 20 Oct 1998 02:57:26 GMT In <70d2bd$8mg$1@news01.btx.dtag.de>, Heidelberg said: [snip] . Take a number, Add the mirror number. Repeat this until you get a . 'palindrom' - this is a number which looks the same from both sides, . like 123431. [snip] . The problem: does this sequence stop for each number you start with ? . Does it stop for 196 ? When ? - . Unknown, but the computations have been pushed pretty far. When I asked about this in June 1996 I got the following response: . From: cmcmanus . Subject: Re: Status of palindrome conjecture? . Date: 17 Jun 1996 . Message-ID: <4q4ged$q2p@news6.erols.com> . references: <4q3s5k$9g7@natasha.rmii.com> . newsgroups: sci.math . Probably the final word on the palindromic quest involving 196 is found . in two articles by John Walker. . See: www.fourmilab.ch/documents/threeyears/threeyears.html . and www.fourmilab.ch/documents/threeyears/two_months_more.html . In the first paper, Walker reports on a 3-year project, which reached . 2,415,836 steps, and a number containing 1 million digits, without ever . yielding a palindrome. . In the second paper, one Tim Irvin reports on a project building on . Walker's efforts, and which took only two months to reach a nonpalindromic number of two . million digits. [snip] ============================================================================== Mathematical Reviews on the Web 1999/01/13 Selected Matches for: Anywhere=(palindrom* and digit*) _________________________________________________________________ Next Review 97m:11015 11A63 Yamashita, Koji A problem on palindromic numbers. (English. English summary) Math. Japon. 45 (1997), no. 1, 159--163. For a positive integer $n$, written in base 10, let $n'$ be the integer obtained by reversing the digits of $n$ and let $f\sb 1(n)=n+n'$. For $k\geq 2$, let $f\sb k(n)=f\sb 1(f\sb {k-1}(n))$. It has been asked whether for each positive integer $n$ there exists a positive integer $k$ for which $f\sb k(n)=(f\sb k(n))'$; that is, for which $f\sb k(n)$ is palindromic. The author verifies that this is so for $n\leq 195$. It is also shown that for all but perhaps 246 values of $n<10\,000$, such a $k$ exists. For the exceptional cases, it is shown that there is no such $k\leq 1000$. Reviewed by H. L. Abbott _________________________________________________________________ 48 #5993 10A40 Trigg, Charles W. Versum sequences in the binary system. Pacific J. Math. 47 (1973), 263--275; corrections, ibid. 49 (1973), 619. The result $S'$ of adding a positive integer $S$, relative to some base, to the integer whose digits are those of $S$ reversed, is called a versum. An old conjecture is that, relative to base 10, any iterative sequence of versa $S,S',S",S"',\cdots$ contains a palindromic number. D. C. Duncan [Sphinx 9 (1939), 91--92] showed that the conjecture is false relative to base 2 by exhibiting a palindromefree recursive cycle of 4 versums. The present author, also working in base 2, is concerned with further instances of such palindrome-free sequences as well as with palindromefree sequences not exhibiting such recursive cycles. Reviewed by J. B. Roberts _________________________________________________________________ 40 #7192 10.08 Gabai, Hyman; Coogan, Daniel On palindromes and palindromic primes. Math. Mag. 42 1969 252--254. Let $N'$ be the integer obtained from the positive integer $N$ by reversing the digits of $N$ written to the base $b$. Let $S\sb 1=N+N'$ and $S\sb {k+1}=S\sb k+S\sb k{}'$. An old conjecture states that, when $b=10$, for each $N$ there is a $k=k(N)$ such that $S\sb k$ is palindromic (i.e., $S\sb k=S\sb k{}'$). Whether there is such a $k$ for $N=196$ remains in doubt. The authors point out that the conjecture fails when $b=2$. In fact, when $N=837=1101000101$ the number $S\sb {4h}(N)$ is obtained from $N$ by replacing the third and eighth binary digits by $h+1$ zeros and ones, respectively. This fact is enough to show that $S\sb k$ is palindromic for no value of $k$. (This fact was communicated to the reviewer in 1954 by T. S. Motzkin.) When $b$ is ten, some interest has been expressed in the past in palindromic primes. The authors have counted palindromic primes of 3, 5 and 7 digits and have found 15, 93 and 668. They note that palindromic primes appear to be denser in the domain of all palindromes than the ordinary primes are in the domain of all positive integers. Reviewed by D. H. Lehmer © Copyright American Mathematical Society 1999 ============================================================================== [Comments: 1. There is a misprint in Brown's tables: 100(decimal) is a palindrome base 3. The first presumably non-terminating number in base 3 is 103(decimal)=10211_{3}. 2. There appear to be plenty of other palindrome-free sequences. Taking a few 5-digit integers at random, it is easy to find some whose sequences appear not to terminate, yet which also appear not to join the other sequences. For example, taken to 10,000 digits, the given chains lead to numbers beginning 196: 1572252888008383803714884446997489576027567542194112240651342698432831 879: 1622485170768957736604537323008989748932494401998087270917988660255293 9988: 1459431769898319536260032364690389326185404937834733563462909955368107 while, for example, 32419 hits a 10,000-digit number at 1989576889978067474446699628914346714396644395657983240389351328928338 so it has not joined the sequence yet. Likewise we try 36973, which hits 10000 digits at 1715082280172088855721474956398093581002933490396524032093400018750325 and 43844, which hits at 1590066149997562703886911665885975140825357757205142835710959608698026 So there appears to be little room for optimism that the sequences coalesce. Indeed, trying random integers shows that longer numbers are increasingly likely to fail to reach a palindrome (testing to a few tens of thousands of iterations).