Euler's criterion

2013-11-26T16:13:20Z

75.73.185.11: /* Proof */

A '''palindromic number''' or '''numeral palindrome''' is a number that remains the same when its digits are reversed. Like 16461, for example, it is "symmetrical". The term ''palindromic'' is derived from [[palindrome]], which refers to a word (such as ''rotor'' or ''racecar'') whose spelling is unchanged when its letters are reversed. The first 30 palindromic numbers (in [[decimal]]) are:
: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 22, 33, 44, 55, 66, 77, 88, 99, 101, 111, 121, 131, 141, 151, 161, 171, 181, 191, 202, … {{OEIS|id=A002113}}.

Palindromic numbers receive most attention in the realm of [[recreational mathematics]]. A typical problem asks for numbers that possess a certain property ''and'' are palindromic. For instance:
*The [[palindromic prime]]s are 2, 3, 5, 7, 11, 101, 131, 151, … {{OEIS|id=A002385}}.
*The palindromic [[square number]]s are 0, 1, 4, 9, 121, 484, 676, 10201, 12321, … {{OEIS|id=A002779}}.

[[Buckminster Fuller]] referred to palindromic numbers as '''Scheherazade numbers''' in his book ''[[Synergetics (Fuller)|Synergetics]]'', because [[Scheherazade]] was the name of the story-telling wife in the ''[[The Book of One Thousand and One Nights|1001 Nights]]''.

It is fairly straightforward to appreciate that in any [[base (exponentiation)|base]] there are [[Infinite set|infinitely many]] palindromic numbers, since in any base the infinite [[sequence]] of numbers written (in that base) as 101, 1001, 10001, etc. (in which the ''n''th number is a 1, followed by ''n'' zeros, followed by a 1) consists of palindromic numbers only.

==Formal definition==
Although palindromic numbers are most often considered in the [[decimal]] system, the concept of '''palindromicity''' can be applied to the [[natural numbers]] in any [[numeral system]]. Consider a number ''n'' > 0 in [[radix|base]] ''b'' ≥ 2, where it is written in standard notation with ''k''+1 [[numerical digit|digit]]s ''a''''i'' as:
:<math>n=\sum_{i=0}^ka_ib^i</math>
with, as usual, 0 ≤ ''a''''i'' < ''b'' for all ''i'' and ''a''''k'' ≠ 0. Then ''n'' is palindromic if and only if ''a''''i'' = ''a''''k''−''i'' for all ''i''. [[0 (number)|Zero]] is written 0 in any base and is also palindromic by definition.

==Decimal palindromic numbers==
All numbers in [[Decimal|base 10]] with one [[numerical digit|digit]] are palindromic. The number of palindromic numbers with two digits is 9:
:{11, 22, 33, 44, 55, 66, 77, 88, 99}.
There are 90 palindromic numbers with three digits (Using the [[Rule of product]]: 9 choices for the first digit - which determines the third digit as well - multiplied by 10 choices for the second digit):
:{101, 111, 121, 131, 141, 151, 161, 171, 181, 191, …, 909, 919, 929, 939, 949, 959, 969, 979, 989, 999}
and also 90 palindromic numbers with four digits: (Again, 9 choices for the first digit multiplied by ten choices for the second digit. The other two digits are determined by the choice of the first two)
:{1001, 1111, 1221, 1331, 1441, 1551, 1661, 1771, 1881, 1991, …, 9009, 9119, 9229, 9339, 9449, 9559, 9669, 9779, 9889, 9999},
so there are 199 palindromic numbers below 104. Below 105 there are 1099 palindromic numbers and for other exponents of 10n we have: 1999, 10999, 19999, 109999, 199999, 1099999, … {{OEIS|id=A070199}}. For some types of palindromic numbers these values are listed below in a table. Here 0 is included.
<table border="1" cellspacing="0" cellpadding="2">
<tr>
<td bgcolor="#CCCC00"> </td>
<td bgcolor="#CCCC00">101</td>
<td bgcolor="#CCCC00">102</td>
<td bgcolor="#CCCC00">103</td>
<td bgcolor="#CCCC00">104</td>
<td bgcolor="#CCCC00">105</td>
<td bgcolor="#CCCC00">106</td>
<td bgcolor="#CCCC00">107</td>
<td bgcolor="#CCCC00">108</td>
<td bgcolor="#CCCC00">109</td>
<td bgcolor="#CCCC00">1010</td>
</tr>
<tr>
<td bgcolor="#FFCC99">''n'' [[Natural number|natural]]</td>
<td>10</td>
<td>19</td>
<td>109</td>
<td>199</td>
<td>1099</td>
<td>1999</td>
<td>10999</td>
<td>19999</td>
<td>109999</td>
<td>199999</td>
</tr>
<tr>
<td bgcolor="#FFCC99">''n'' [[even and odd numbers|even]]</td>
<td>5</td>
<td>9</td>
<td>49</td>
<td>89</td>
<td>489</td>
<td>889</td>
<td>4889</td>
<td>8889</td>
<td>48889</td>
<td>88889</td>
</tr>
<tr>
<td bgcolor="#FFCC99">''n'' [[odd number|odd]]</td>
<td>5</td>
<td>10</td>
<td>60</td>
<td>110</td>
<td>610</td>
<td>1110</td>
<td>6110</td>
<td>11110</td>
<td>61110</td>
<td>111110</td>
</tr>
<tr>
<td bgcolor="#FFCC99">''n'' [[square number|square]]</td>
<td colspan="2">4</td>
<td colspan="2">7</td>
<td>14</td>
<td>15</td>
<td colspan="2">20</td>
<td colspan="2">31</td>
</tr>
<tr>
<td bgcolor="#FFCC99">''n'' [[Cube (algebra)|cube]]</td>
<td colspan="2">3</td>
<td>4</td>
<td colspan="3">5</td>
<td colspan="3">7</td>
<td>8</td>
</tr>
<tr>
<td bgcolor="#FFCC99">''n'' [[prime number|prime]]</td>
<td>4</td>
<td>5</td>
<td colspan="2">20</td>
<td colspan="2">113</td>
<td colspan="2">781</td>
<td colspan="2">5953</td>
</tr>
<tr>
<td bgcolor="#FFCC99">''n'' [[square-free integer|squarefree]]</td>
<td>6</td>
<td>12</td>
<td>67</td>
<td>120</td>
<td>675</td>
<td>1200</td>
<td>6821</td>
<td>12160</td>
<td>+</td>
<td>+</td>
</tr>
<tr>
<td bgcolor="#FFCC99">''n'' non-squarefree ([[Möbius function|μ(''n'')]]=0)</td>
<td>4</td>
<td>7</td>
<td>42</td>
<td>79</td>
<td>424</td>
<td>799</td>
<td>4178</td>
<td>7839</td>
<td>+</td>
<td>+</td>
</tr>
<tr>
<td bgcolor="#FFCC99">''n'' square with prime root</td>
<td colspan="2">2</td>
<td colspan="2">3</td>
<td colspan="6">5</td>
</tr>
<tr>
<td bgcolor="#FFCC99">''n'' with an even number of distinct [[prime factor]]s (μ(''n'')=1)</td>
<td>2</td>
<td>6</td>
<td>35</td>
<td>56</td>
<td>324</td>
<td>583</td>
<td>3383</td>
<td>6093</td>
<td>+</td>
<td>+</td>
</tr>
<tr>
<td bgcolor="#FFCC99">''n'' with an odd number of distinct prime factors
(μ(''n'')=-1)</td>
<td>4</td>
<td>6</td>
<td>32</td>
<td>64</td>
<td>351</td>
<td>617</td>
<td>3438</td>
<td>6067</td>
<td>+</td>
<td>+</td>
</tr>
<tr>
<td bgcolor="#FFCC99">''n'' even with an odd number of prime factors</td>
<td>1</td>
<td>2</td>
<td>9</td>
<td>21</td>
<td>100</td>
<td>180</td>
<td>1010</td>
<td>6067</td>
<td>+</td>
<td>+</td>
</tr>
<tr>
<td bgcolor="#FFCC99">''n'' even with an odd number of distinct prime factors</td>
<td>3</td>
<td>4</td>
<td>21</td>
<td>49</td>
<td>268</td>
<td>482</td>
<td>2486</td>
<td>4452</td>
<td>+</td>
<td>+</td>
</tr>
<tr>
<td bgcolor="#FFCC99">''n'' odd with an odd number of prime factors</td>
<td>3</td>
<td>4</td>
<td>23</td>
<td>43</td>
<td>251</td>
<td>437</td>
<td>2428</td>
<td>4315</td>
<td>+</td>
<td>+</td>
</tr>
<tr>
<td bgcolor="#FFCC99">''n'' odd with an odd number of distinct prime factors</td>
<td>4</td>
<td>5</td>
<td>28</td>
<td>56</td>
<td>317</td>
<td>566</td>
<td>3070</td>
<td>5607</td>
<td>+</td>
<td>+</td>
</tr>
<tr>
<td bgcolor="#FFCC99">''n'' even squarefree with an even number of (distinct) prime factors</td>
<td>1</td>
<td>2</td>
<td>11</td>
<td>15</td>
<td>98</td>
<td>171</td>
<td>991</td>
<td>1782</td>
<td>+</td>
<td>+</td>
</tr>
<tr>
<td bgcolor="#FFCC99">''n'' odd squarefree with an even number of (distinct) prime factors</td>
<td>1</td>
<td>4</td>
<td>24</td>
<td>41</td>
<td>226</td>
<td>412</td>
<td>2392</td>
<td>4221</td>
<td>+</td>
<td>+</td>
</tr>
<tr>
<td bgcolor="#FFCC99">''n'' odd with exactly 2 prime factors</td>
<td>1</td>
<td>4</td>
<td>25</td>
<td>39</td>
<td>205</td>
<td>303</td>
<td>1768</td>
<td>2403</td>
<td>+</td>
<td>+</td>
</tr>
<tr>
<td bgcolor="#FFCC99">''n'' even with exactly 2 prime factors</td>
<td>2</td>
<td>3</td>
<td colspan="2">11</td>
<td colspan="2">64</td>
<td colspan="2">413</td>
<td>+</td>
<td>+</td>
</tr>
<tr>
<td bgcolor="#FFCC99">''n'' even with exactly 3 prime factors</td>
<td>1</td>
<td>3</td>
<td>14</td>
<td>24</td>
<td>122</td>
<td>179</td>
<td>1056</td>
<td>1400</td>
<td>+</td>
<td>+</td>
</tr>
<tr>
<td bgcolor="#FFCC99">''n'' even with exactly 3 distinct prime factors</td>
<td>0</td>
<td>1</td>
<td>18</td>
<td>44</td>
<td>250</td>
<td>390</td>
<td>2001</td>
<td>2814</td>
<td>+</td>
<td>+</td>
</tr>
<tr>
<td bgcolor="#FFCC99">''n'' odd with exactly 3 prime factors</td>
<td>0</td>
<td>1</td>
<td>12</td>
<td>34</td>
<td>173</td>
<td>348</td>
<td>1762</td>
<td>3292</td>
<td>+</td>
<td>+</td>
</tr>
<tr>
<td bgcolor="#FFCC99">''n'' [[Carmichael number]]</td>
<td>0</td>
<td>0</td>
<td>0</td>
<td>0</td>
<td>0</td>
<td>1</td>
<td>1</td>
<td>1</td>
<td>1</td>
<td>1</td>
</tr>
<tr>
<td bgcolor="#FFCC99">''n'' for which [[Divisor function|σ(''n'')]] is palindromic</td>
<td>6</td>
<td>10</td>
<td>47</td>
<td>114</td>
<td>688</td>
<td>1417</td>
<td>5683</td>
<td>+</td>
<td>+</td>
<td>+</td>
</tr>
</table>

==Perfect powers==
There are many palindromic [[perfect power]]s ''n''''k'', where ''n'' is a natural number and ''k'' is 2, 3 or 4.
* Palindromic [[Square number|squares]]: 0, 1, 4, 9, 121, 484, 676, 10201, 12321, 14641, 40804, 44944, ... {{OEIS|id=A002779}}
* Palindromic [[Cube (algebra)|cubes]]: 0, 1, 8, 343, 1331, 1030301, 1367631, 1003003001, ... {{OEIS|id=A002781}}
* Palindromic [[fourth power]]s: 0, 1, 14641, 104060401, 1004006004001, ... {{OEIS|id=A186080}}

The only known non-palindromic number whose cube is a palindrome is 2201.

G. J. Simmons conjectured there are no palindromes of form ''n''''k'' for ''k'' > 4 (and ''n'' > 1).<ref>Murray S. Klamkin (1990), ''Problems in applied mathematics: selections from SIAM review'', [http://books.google.com/books?id=WI9ZGl3M8bYC&pg=PA520 p. 520].</ref>

==Other bases==
Palindromic numbers can be considered in other [[numeral system]]s than [[decimal]]. For example, the [[Binary numeral system|binary]] palindromic numbers are:
:0, 1, 11, 101, 111, 1001, 1111, 10001, 10101, 11011, 11111, 100001, …
or in decimal: 0, 1, 3, 5, 7, 9, 15, 17, 21, 27, 31, 33, … {{OEIS|id=A006995}}. The [[Mersenne prime]]s form a subset of the binary palindromic primes.

All numbers are palindromic in an infinite number of bases. But, it's more interesting to consider bases smaller than the number itself - in which case most numbers are palindromic in more than one base.

In [[base 18]], some powers of seven are palindromic:

73 = 111
74 = 777
76 = 12321
79 = 1367631

And in [[base 24]] the first eight powers of five are palindromic as well:

51 = 5
52 = 11
53 = 55
54 = 121
55 = 5A5
56 = 1331
57 = 5FF5
58 = 14641
5A = 15AA51
5C = 16FLF61

Any number ''n'' is palindromic in all bases ''b'' with ''b'' ≥ ''n'' + 1 (trivially so, because ''n'' is then a single-digit number), and also in base ''n''−1 (because ''n'' is then 11''n''−1). A number that is non-palindromic in all bases 2 ≤ ''b'' < ''n'' − 1 is called a [[strictly non-palindromic number]].

==Lychrel process==

Non-palindromic numbers can be paired with palindromic ones via a series of operations. First, the non-palindromic number is reversed and the result is added to the original number. If the result is not a palindromic number, this is repeated until it gives a palindromic number.

It is not known whether all non-palindromic numbers can be paired with palindromic numbers in this way. While no number has been proven to be unpaired, many do not appear to be. For example, 196 does not yield a palindrome even after 700,000,000 iterations. Any number that never becomes palindromic in this way is known as a [[Lychrel number]].

==Sum of the reciprocals==

The sum of the reciprocals of the palindromic numbers is a convergent series, whose value is approximately 3.37028... {{OEIS|id=A118031}}.

==See also==
*[[Lychrel number]]
*[[Palindromic prime]]
*[[Palindrome]]

==Notes==
{{Reflist}}

==References==
*Malcolm E. Lines: ''A Number for Your Thoughts: Facts and Speculations about Number from Euclid to the latest Computers'': CRC Press 1986, ISBN 0-85274-495-1, S. 61 ([http://books.google.de/books?id=Am9og6q_ny4C&pg=PT69&dq=palindromic+number&lr=&as_brr=3&sig=ACfU3U2mB1VPUV1xTg17Sw0BI3XuZzvQow Limited Online-Version (Google Books)])

==External links==

*[http://www.codenirvana.in/2013/10/Palindrome-Number-in-JAVA.html Java program to check palindrome]
*{{MathWorld|urlname=PalindromicNumber|title= Palindromic Number}}
*[http://www.jasondoucette.com/worldrecords.html Jason Doucette - 196 Palindrome Quest / Most Delayed Palindromic Number]
*[http://www.p196.org 196 and Other Lychrel Numbers]
*[http://www.mathpages.com/home/kmath359.htm On General Palindromic Numbers] at MathPages
*[http://mathforum.org/library/drmath/view/57170.html Palindromic Numbers to 100,000] from Ask Dr. Math
*[http://users.skynet.be/worldofnumbers/ P. De Geest, Palindromic cubes]

{{Classes of natural numbers}}
[[Category:Base-dependent integer sequences]]
[[Category:Palindromes]]

[[pl:Palindrom#Palindromy liczbowe]]

formulasearchengine - User contributions [en]

Euler's criterion