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:自我数]]