회문수 문서 원본 보기

{{위키데이터 속성 추적}}
'''회문수'''(回文數, {{llang|en|palindromic number}}) 또는 '''대칭수'''(對稱數)는 순서대로 읽은 수와 거꾸로 읽은 수가 같은 수를 말한다. 예를 들어 34543은 회문수이고, 34567은 회문수가 아니다. 처음 30개의 회문수([[십진법]])는 다음과 같다.

: 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}}

회문수는 [[유희 수학]]에서 주목받는 수이며, 일반적으로 어떤 성질을 가지는 동시에 대칭인 수를 다룬다. 예를 들어,

* [[회문 소수]]는 2, 3, 5, 7, 11, 101, 131, 151, ... 등이 있다. {{OEIS|id=A002385}}
* 회문 [[정사각수]]는 0, 1, 4, 9, 121, 484, 676, 10201, 12321, ... 등이 있다. {{OEIS|id=A002779}}

== 정의 ==
회문수는 주로 십진법에서 다루지만, 다른 기수법에서도 적용할 수 있다. <math>b</math>진법(<math>b\geq2</math>)에서 <math>k+1</math>자리를 가지는 수 <math>n</math>(<math>n>0</math>)에 대해, <math>n</math>의 <math>i</math>번째 자릿수를 <math>a_i</math>라 하면

: <math>n=\sum_{i=0}^ka_ib^i</math>

이다. (<math>0\leq a_i<b</math>, <math>a_k\neq0</math>) 이때 모든 <math>i</math>에 대해 <math>a_i=a_{k-i}</math>인 경우 <math>n</math>을 회문수라고 정의한다. 0은 모든 진법에서 0이 되므로 회문수이다.

== [[십진법]]에서의 회문수 ==
십진법에서 짝수 자릿수의 회문수는 11로 나눌 수 있다.

십진법에서 한 자릿수는 모두 회문수이며, 이는 다른 기수법에서도 마찬가지이다. 두 자릿수인 회문수는 모두 9개가 있다.

: 11, 22, 33, 44, 55, 66, 77, 88, 99

세 자릿수인 회문수는 90개가 있다(일의 자리에서 9가지 경우, 십의 자리에서 10가지 경우가 있기 때문).

: 101, 111, 121, 131, 141, 151, 161, 171, 181, 191,…, 909, 919, 929, 939, 949, 959, 969, 979, 989, 999

네 자릿수인 회문수도 세 자릿수와 마찬가지로 90개가 존재한다.

: 1001, 1111, 1221, 1331, 1441, 1551, 1661, 1771, 1881, 1991,…, 9009, 9119, 9229, 9339, 9449, 9559, 9669, 9779, 9889, 9999,

따라서 10000 이하의 수에는 199개의 회문수가 존재한다. 100000 이하의 수에는 1099개가 존재하며, <math>10^n</math> 이하의 회문수의 개수는 1999, 10999, 19999, 109999, 199999, 1099999, ... 가 된다. {{OEIS|id=A070199}} 아래 표는 특정 성질을 만족하는 <math>10^n</math> 이하의 회문수의 개수를 나타낸 것이며, 0도 포함하였다.
{| class="wikitable"
!
!10<sup>1</sup>
!10<sup>2</sup>
!10<sup>3</sup>
!10<sup>4</sup>
!10<sup>5</sup>
!10<sup>6</sup>
!10<sup>7</sup>
!10<sup>8</sup>
!10<sup>9</sup>
!10<sup>10</sup>
|-
! style="font-weight:normal; text-align:left" |[[자연수]]
|10
|19
|109
|199
|1099
|1999
|10999
|19999
|109999
|199999
|-
! style="font-weight:normal; text-align:left" |[[짝수]]
|5
|9
|49
|89
|489
|889
|4889
|8889
|48889
|88889
|-
! style="font-weight:normal; text-align:left" |[[홀수]]
|5
|10
|60
|110
|610
|1110
|6110
|11110
|61110
|111110
|-
! style="font-weight:normal; text-align:left" |[[제곱수]]
| colspan="2" |4
| colspan="2" |7
|14
|15
| colspan="2" |20
| colspan="2" |31
|-
! style="font-weight:normal; text-align:left" |[[세제곱수]]
| colspan="2" |3
|4
| colspan="3" |5
| colspan="3" |7
|8
|-
! style="font-weight:normal; text-align:left" |[[소수]]
|4
|5
| colspan="2" |20
| colspan="2" |113
| colspan="2" |781
| colspan="2" |5953
|-
! style="font-weight:normal; text-align:left" |[[제곱인수가 없는 정수|제곱인수가 없는 자연수]]
|6
|12
|67
|120
|675
|1200
|6821
|12160
|
|
|-
! style="font-weight:normal; text-align:left" |제곱인수가 있는 정수([[뫼비우스 함수|μ(n)]]=0)
|4
|7
|42
|79
|424
|799
|4178
|7839
|
|
|-
! style="font-weight:normal; text-align:left" |소수의 제곱수<ref>{{OEIS|A065379}} The next example is 19 digits - 900075181570009.</ref>
| colspan="2" |2
| colspan="2" |3
| colspan="6" |5
|-
! style="font-weight:normal; text-align:left" |[[뫼비우스 함수|μ(n)]]=1인 수
|2
|6
|35
|56
|324
|583
|3383
|6093
|
|
|-
! style="font-weight:normal; text-align:left" |[[뫼비우스 함수|μ(n)]]=-1인 수
|4
|6
|32
|64
|351
|617
|3438
|6067
|
|
|-
! style="font-weight:normal; text-align:left" |두 소인수를 가지는 홀수
|1
|4
|25
|39
|205
|303
|1768
|2403
|
|
|-
! style="font-weight:normal; text-align:left" |두 소인수를 가지는 짝수
|2
|3
| colspan="2" |11
| colspan="2" |64
| colspan="2" |413
|
|
|-
! style="font-weight:normal; text-align:left" |세 소인수를 가지는 짝수
|1
|3
|14
|24
|122
|179
|1056
|1400
|
|
|-
! style="font-weight:normal; text-align:left" |서로 다른 세 소인수를 가지는 짝수
|0
|1
|18
|44
|250
|390
|2001
|2814
|
|
|-
! style="font-weight:normal; text-align:left" |세 소인수를 가지는 홀수
|0
|1
|12
|34
|173
|348
|1762
|3292
|
|
|-
! style="font-weight:normal; text-align:left" |[[카마이클 수]]
|0
|0
|0
|0
|0
|1
|1
|1
|1
|1
|-
! style="font-weight:normal; text-align:left" |[[약수 함수|σ(n)]]이 회문수인 수
|6
|10
|47
|114
|688
|1417
|5683
|
|
|
|}

== 거듭제곱인 회문수 ==
자연수 <math>n</math>과 <math>k</math>(<math>k</math>는 2, 3 또는 4)에 대해 거듭제곱수 <math>n^k</math>이 회문수가 되는 여러 경우가 있다.

* [[제곱]]인 회문수: 0, 1, 4, 9, 121, 484, 676, 10201, 12321, 14641, 40804, 44944, ... {{OEIS|id=A002779}}
* [[세제곱]]인 회문수: 0, 1, 8, 343, 1331, 1030301, 1367631, 1003003001, ... {{OEIS|id=A002781}}
* [[네제곱수|네제곱]]인 회문수: 0, 1, 14641, 104060401, 1004006004001, ... {{OEIS|id=A186080}}

1<sup>2</sup>, 11<sup>2</sup>, 111<sup>2</sup>, 1111<sup>2</sup>, ... 의 첫 아홉개 수는 1, 121, 12321, 1234321, ... 가 되어 회문수이다. {{OEIS|id=A002477}}

제곱수가 회문수이지만 자기 자신은 회문수가 아닌 것으로 알려진 수로는 현재까지 2201이 유일하다. 또한 현재까지 발견된 네제곱인 회문수들의 네제곱근은 모두 <math>10^n+1</math>꼴이며, 모든 네제곱인 회문수에 대해 성립하는지는 밝혀지지 않았다.

G. J. Simmons는 5 이상의 <math>k</math>에 대해 <math>n^k</math>(<math>n>1</math>)꼴의 회문수는 존재하지 않는다고 추측하였다.<ref>Murray S. Klamkin (1990), ''Problems in applied mathematics: selections from SIAM review'', [https://books.google.com/books?id=WI9ZGl3M8bYC&pg=PA520 p. 520].</ref>

== 다른 기수법에서의 회문수 ==
[[이진법]]에서의 회문수는 다음과 같다.

: 0, 1, 11, 101, 111, 1001, 1111, 10001, 10101, 11011, 11111, 100001, &#x2026;

이를 십진법으로 표기하면 0, 1, 3, 5, 7, 9, 15, 17, 21, 27, 31, 33, …이다. {{OEIS|id=A006995}}. [[페르마 수|페르마 소수]]와 [[메르센 소수]]는 이진법에서 회문수인 소수가 된다.

숫자 자신보다 밑이 더 큰 경우 수는 한 자릿수가 되므로, 모든 수들은 무한히 많은 기수법에서 대칭이다. 숫자 자신보다 밑이 더 작은 경우만을 고려하면, 여러 기수법에서 회문수가 되는 경우가 존재한다. 예를 들어 <math>1221_4=151_8=77_{14}=55_{20}=33_{34}=11_{104}</math>, <math>1991_{10}=7C7_{16}</math>이다.

7진법에서 101<sub>7</sub>은 5<sup>2</sup>=34<sub>7</sub>의 2배이기 때문에, 다음과 같이 여러 101<sub>7</sub>의 배수들은 제곱수인 회문수가 된다.
{| class="toccolours"
|13<sup>2</sup>
|=
| style="text-align:right" |202
|-
|26<sup>2</sup>
|=
| style="text-align:right" |1111
|-
|55<sup>2</sup>
|=
| style="text-align:right" |4444
|-
|101<sup>2</sup>
|=
| style="text-align:right" |10201
|-
|143<sup>2</sup>
|=
| style="text-align:right" |24442
|}
18진법에서, 다음과 같이 여러 7의 거듭제곱수들은 회문수가 된다.
{| class="toccolours"
|7<sup>0</sup>
|=
| style="text-align:right" |1
|-
|7<sup>1</sup>
|=
| style="text-align:right" |7
|-
|7<sup>3</sup>
|=
| style="text-align:right" |111
|-
|7<sup>4</sup>
|=
| style="text-align:right" |777
|-
|7<sup>6</sup>
|=
| style="text-align:right" |12321
|-
|7<sup>9</sup>
|=
| style="text-align:right" |1367631
|}
24진법에서, 다음과 같이 첫 여덟제곱을 포함하여 여러 거듭제곱수들은 회문수가 된다.
{| class="toccolours"
|5<sup>0</sup>
|=
| style="text-align:right" |1
|-
|5<sup>1</sup>
|=
| style="text-align:right" |5
|-
|5<sup>2</sup>
|=
| style="text-align:right" |11
|-
|5<sup>3</sup>
|=
| style="text-align:right" |55
|-
|5<sup>4</sup>
|=
| style="text-align:right" |121
|-
|5<sup>5</sup>
|=
| style="text-align:right" |5A5
|-
|5<sup>6</sup>
|=
| style="text-align:right" |1331
|-
|5<sup>7</sup>
|=
| style="text-align:right" |5FF5
|-
|5<sup>8</sup>
|=
| style="text-align:right" |14641
|-
|5<sup>A</sup>
|=
| style="text-align:right" |15AA51
|-
|5<sup>C</sup>
|=
| style="text-align:right" |16FLF61
|}
자연수 <math>n</math>에 대해 <math>n-1</math>진법에서는 <math>11_{n-1}</math>로 회문수가 되고, <math>2\leq b<n-1</math>인 모든 <math>b</math>진법에서 회문수가 아닌 수를 [[강한 비회문수]]라 한다.

== [[라이크렐 수]] ==
비회문수는 알고리즘을 통해 회문수로 만들 수도 있다. 먼저 비회문수와 그 수를 뒤집은 수를 더하여 새로운 수를 얻는다. 이 과정을 회문수가 나올 때까지 반복하며, 이를 196-알고리즘 또는 회문 알고리즘이라고 한다.

회문 알고리즘을 거쳤을 때 결코 회문수가 되지 않는 수를 [[라이크렐 수]]라고 하며, 라이크렐 수가 존재하는지는 아직 밝혀지지 않았지만 196을 포함한 여러 수들을 라이크렐 수로 추측하고 있다.<ref>O'Bryant, Kevin (26 December 2012). [https://mathoverflow.net/q/117277 "Reply to Status of the 196 conjecture?"]. Math Overflow.</ref> 라이크렐 수의 후보로는 196, 879, 1997 등이 있다.

현재 가장 늦게 회문수가 되는 수는 12,000,700,000,025,339,936,491로,  [http://jasondoucette.com/pal/12000700000025339936491 288]단계 후에 142자리의 회문수 ''44562665878976437622437848976653870388884783662598425855963436955852489526638748888307835667984873422673467987856626544''에 도달한다.

== 회문수의 합 ==
2018년에는 밑이 5 이상인 기수법에서 모든 양의 정수는 세 회문수의 합으로 표현할 수 있음을 증명하는 논문이 게재되었다.<ref>{{저널 인용|제목=Every positive integer is a sum of three palindromes|저널=Mathematics of Computation|성=Cilleruelo|이름=Javier|성2=Luca|이름2=Florian|url=http://www.ams.org/journals/mcom/2018-87-314/S0025-5718-2017-03221-X/home.html|날짜=2016-02-19|성3=Baxter|이름3=Lewis}} ([[arxiv:1602.06208|arXiv preprint]])</ref>

또한 회문수의 역수들의 합은 수렴하는 수열이 되며, 수렴값은 3.37028...이다. {{OEIS|id=A118031}}

== 같이 보기 ==
* [[라이크렐 수]]
* [[회문]]

== 각주 ==
{{각주}}

== 외부 링크 ==

* {{언어링크|en}} [http://www.jasondoucette.com/worldrecords.html 196 회문수 찾기 세계신기록]
* {{언어링크|en}} [https://web.archive.org/web/20061104023524/http://www.p196.org/ Wade Van Landingham의 페이지]
* {{언어링크|en}} [http://mathworld.wolfram.com/196-Algorithm.html Wolfram mathworld의 196-알고리즘 소개 페이지]

[[분류:회문]]