Self number
880483
211012780
2008-05-08T12:02:34Z
Pvrantz
7063079
/* Effective test */
A '''self number''', '''Colombian number''' or [[Devlali number]] is an [[integer]] which, in a given [[Radix|base]], cannot be generated by any other integer added to the sum of its digits. For example, 21 is not a self number, since it can be generated by the sum of 15 and the digits comprising 15, that is, 21 = 15 + 1 + 5. No such sum will generate the integer 20, hence it is a self number. These numbers were first described in 1949 by the [[India]]n [[mathematician]] [[D. R. Kaprekar]].
The first few base 10 self numbers are
[[1 (number)|1]], [[3 (number)|3]], [[5 (number)|5]], [[7 (number)|7]], [[9 (number)|9]], [[20 (number)|20]], [[31 (number)|31]], [[42 (number)|42]], [[53 (number)|53]], [[64 (number)|64]], [[75 (number)|75]], [[86 (number)|86]], [[97 (number)|97]], [[108 (number)|108]], [[110 (number)|110]], [[121 (number)|121]], [[132 (number)|132]], [[143 (number)|143]], [[154 (number)|154]], 165, 176, [[187 (number)|187]], 198, 209, [[211 (number)|211]], [[222 (number)|222]], [[233 (number)|233]], 244, [[255 (number)|255]], 266, [[277 (number)|277]], 288, 299, 310, 312, 323, 334, 345, 356, 367, 378, 389, [[400 (number)|400]], 411, 413, 424, 435, 446, 457, 468, 479, 490, 501, 512, 514, 525 {{OEIS|id=A003052}}
In general, for even bases, all [[even and odd numbers|odd]] numbers below the base number are self numbers, since any number below such an odd number would have to also be a 1-digit number which when added to its digit would result in an even number. For odd bases, all odd numbers are self numbers.
The following [[recurrence relation]] generates [[Decimal|base 10]] self numbers:
:<math>C_k = 8 \cdot 10^{k - 1} + C_{k - 1} + 8</math>
(with ''C''<sub>1</sub> = 9)
And for [[binary numeral system|binary]] numbers:
:<math>C_k = 2^j + C_{k - 1} + 1\,</math>
(where ''j'' stands for the number of digits) we can generalize a recurrence relation to generate self numbers in any base ''b'':
:<math>C_k = (b - 2)b^{k - 1} + C_{k - 1} + (b - 2)\,</math>
in which <math>C_1 = b-1</math> for even bases and <math>C_1 = b-2</math> for odd bases.
The existence of these recurrence relations shows that for any base there are infinitely many self numbers.
A search for self numbers can turn up [[self-descriptive number]]s, which are similar to self numbers in being base-dependent, but quite different in definition and much fewer in frequency.
== Self primes ==
A '''self prime''' is a self number that is [[prime number|prime]]. The first few self primes {{OEIS|id=A006378}} are
3, 5, 7, 31, 53, 97, 211, 233, 277, 367, 389
In October 2006 Luke Pebody demonstrated that the largest known [[Mersenne prime]] that is at the same time a self number is 2<sup>24036583</sup>-1. This is then the largest known self prime [[as of 2006]].
== Selfness tests ==
=== Reduction tests ===
Luke Pebody showed (Oct 2006) that a link can be made between the self property of a large number ''n'' and a low-order portion of that number, adjusted for digit sums:
a) In general, ''n'' is self [[if and only if]] ''m'' = R(''n'')+SOD(R(''n''))-SOD(''n'') is self
Where:
R(''n'') is the smallest rightmost digits of ''n'', greater than 9.d(''n'')
d(''n'') is the number of digits in ''n''
SOD(''x'') is the sum of digits of ''x'', the function <math>S_{10}(x)</math> from above.
b) If ''n'' = ''a''.10^''b''+''c'', ''c''<10^''b'', then ''n'' is self if and only if both {''m1'' & ''m2''} are negative or self
Where:
''m1'' = ''c'' - SOD(''a'')
''m2'' = SOD(''a''-1)+9.''b''-(''c''+1)
c) For the simple case of ''a''=1 & ''c''=0 in the previous model (i.e. ''n''=10^''b''), then ''n'' is self if and only if (9.''b''-1) is self
=== Effective test ===
Kaprekar [[Demonstration_(proof)|demonstrated]] that:
<math>
n \mbox{ is self if }
[ n - DR*(n) - 9 \cdot i ] + SOD([ n - DR*(n) - 9 \cdot i ] ) \neq n
\quad \forall i \in 0 \ldots d(n)
</math>
Where:
<math>DR*(n) =
\begin{cases}
\frac{DR(n)}{2}, & \mbox{if } DR(n) \mbox{ is even}\\
\frac{DR(n) + 9}{2}, & \mbox{if } DR(n) \mbox{ is odd}
\end{cases}
</math>
<math> \begin{align}
DR(n) &{}=
\begin{cases}
9, & \mbox{if } SOD(n) \mod 9 = 0\\
SOD(n) \mod 9, & \mbox{ otherwise}
\end{cases} \\
&{}= (n - 1) \mod 9 + 1
\end{align}</math>
<math>SOD(n) \mbox{ is the sum of all digits in } n</math>
<math>d(n) \mbox{ is the number of digits in } n</math>
== Excerpt from the table of bases where 2007 is self or Colombian ==
The following table was calculated in 2007.
<TABLE BORDER=1>
<TR><TH>Base</TH><TH>Certificate</TH><TH>Sum of digits</TH></TR>
<TR><TD>40</TD><TD><math>1959 = [1, 8, 39]_{40}</math></TD><TD>48</TD></TR>
<TR><TD>41</TD><TD>-</TD><TD>-</TD></TR>
<TR><TD>42</TD><TD><math>1967 = [1, 4, 35]_{42}</math></TD><TD>40</TD></TR>
<TR><TD>43</TD><TD>-</TD><TD>-</TD></TR>
<TR><TD>44</TD><TD><math>1971 = [1, 0, 35]_{44}</math></TD><TD>36</TD></TR>
<TR><TD>44</TD><TD><math>1928 = [43, 36]_{44}</math></TD><TD>79</TD></TR>
<TR><TD>45</TD><TD>-</TD><TD>-</TD></TR>
<TR><TD>46</TD><TD><math>1926 = [41, 40]_{46}</math></TD><TD>81</TD></TR>
<TR><TD>47</TD><TD>-</TD><TD>-</TD></TR>
<TR><TD>48</TD><TD>-</TD><TD>-</TD></TR>
<TR><TD>49</TD><TD>-</TD><TD>-</TD></TR>
<TR><TD>50</TD><TD><math>1959 = [39, 9]_{50}</math></TD><TD>48</TD></TR>
<TR><TD>51</TD><TD>-</TD><TD>-</TD></TR>
<TR><TD>52</TD><TD><math>1947 = [37, 23]_{52}</math></TD><TD>60</TD></TR>
<TR><TD>53</TD><TD>-</TD><TD>-</TD></TR>
<TR><TD>54</TD><TD><math>1931 = [35, 41]_{54}</math></TD><TD>76</TD></TR>
<TR><TD>55</TD><TD>-</TD><TD>-</TD></TR>
<TR><TD>56</TD><TD><math>1966 = [35, 6]_{56}</math></TD><TD>41</TD></TR>
<TR><TD>57</TD><TD>-</TD><TD>-</TD></TR>
<TR><TD>58</TD><TD><math>1944 = [33, 30]_{58}</math></TD><TD>63</TD></TR>
<TR><TD>59</TD><TD>-</TD><TD>-</TD></TR>
<TR><TD>60</TD><TD><math>1918 = [31, 58]_{60}</math></TD><TD>89</TD></TR>
</TABLE>
==References==
* Kaprekar, D. R. ''The Mathematics of New Self-Numbers'' Devaiali (1963): 19 - 20.
* Patel, R. B. "Some Tests for -Self Numbers" ''Math. Student'' '''56''' (1991): 206 - 210.
* B. Recaman, "Problem E2408" ''Amer. Math. Monthly'' '''81''' (1974): 407
* {{MathWorld|urlname=SelfNumber|title=Self Number}}
[[Category:Base-dependent integer sequences]]
[[eo:Mem nombro]]
[[fr:Auto nombre]]
[[it:Numero colombiano]]
[[ru:Самопорождённые числа]]
[[sl:Samoštevilo]]
[[zh:自我数]]