회문수

회문수(回文數, 영어: 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의 수열 A002113)

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

회문 소수는 2, 3, 5, 7, 11, 101, 131, 151, ... 등이 있다. (OEIS의 수열 A002385)
회문 정사각수는 0, 1, 4, 9, 121, 484, 676, 10201, 12321, ... 등이 있다. (OEIS의 수열 A002779)

정의

회문수는 주로 십진법에서 다루지만, 다른 기수법에서도 적용할 수 있다. $b$ 진법( $b \geq 2$ )에서 $k + 1$ 자리를 가지는 수 $n$ ( $n > 0$ )에 대해, $n$ 의 $i$ 번째 자릿수를 $a_{i}$ 라 하면

n = \sum_{i = 0}^{k} a_{i} b^{i}

이다. ( $0 \leq a_{i} < b$ , $a_{k} \neq 0$ ) 이때 모든 $i$ 에 대해 $a_{i} = a_{k - i}$ 인 경우 $n$ 을 회문수라고 정의한다. 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개가 존재하며, $1 0^{n}$ 이하의 회문수의 개수는 1999, 10999, 19999, 109999, 199999, 1099999, ... 가 된다. (OEIS의 수열 A070199) 아래 표는 특정 성질을 만족하는 $1 0^{n}$ 이하의 회문수의 개수를 나타낸 것이며, 0도 포함하였다.

	10¹	10²	10³	10⁴	10⁵	10⁶	10⁷	10⁸	10⁹	10¹⁰
자연수	10	19	109	199	1099	1999	10999	19999	109999	199999
짝수	5	9	49	89	489	889	4889	8889	48889	88889
홀수	5	10	60	110	610	1110	6110	11110	61110	111110
제곱수	4		7		14	15	20		31
세제곱수	3		4	5			7			8
소수	4	5	20		113		781		5953
제곱인수가 없는 자연수	6	12	67	120	675	1200	6821	12160
제곱인수가 있는 정수(μ(n)=0)	4	7	42	79	424	799	4178	7839
소수의 제곱수^[1]	2		3		5
μ(n)=1인 수	2	6	35	56	324	583	3383	6093
μ(n)=-1인 수	4	6	32	64	351	617	3438	6067
두 소인수를 가지는 홀수	1	4	25	39	205	303	1768	2403
두 소인수를 가지는 짝수	2	3	11		64		413
세 소인수를 가지는 짝수	1	3	14	24	122	179	1056	1400
서로 다른 세 소인수를 가지는 짝수	0	1	18	44	250	390	2001	2814
세 소인수를 가지는 홀수	0	1	12	34	173	348	1762	3292
카마이클 수	0	0	0	0	0	1	1	1	1	1
σ(n)이 회문수인 수	6	10	47	114	688	1417	5683

거듭제곱인 회문수

자연수 $n$ 과 $k$ ( $k$ 는 2, 3 또는 4)에 대해 거듭제곱수 $n^{k}$ 이 회문수가 되는 여러 경우가 있다.

제곱인 회문수: 0, 1, 4, 9, 121, 484, 676, 10201, 12321, 14641, 40804, 44944, ... (OEIS의 수열 A002779)
세제곱인 회문수: 0, 1, 8, 343, 1331, 1030301, 1367631, 1003003001, ... (OEIS의 수열 A002781)
네제곱인 회문수: 0, 1, 14641, 104060401, 1004006004001, ... (OEIS의 수열 A186080)

1², 11², 111², 1111², ... 의 첫 아홉개 수는 1, 121, 12321, 1234321, ... 가 되어 회문수이다. (OEIS의 수열 A002477)

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

G. J. Simmons는 5 이상의 $k$ 에 대해 $n^{k}$ ( $n > 1$ )꼴의 회문수는 존재하지 않는다고 추측하였다.^[2]

다른 기수법에서의 회문수

이진법에서의 회문수는 다음과 같다.

0, 1, 11, 101, 111, 1001, 1111, 10001, 10101, 11011, 11111, 100001, …

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

숫자 자신보다 밑이 더 큰 경우 수는 한 자릿수가 되므로, 모든 수들은 무한히 많은 기수법에서 대칭이다. 숫자 자신보다 밑이 더 작은 경우만을 고려하면, 여러 기수법에서 회문수가 되는 경우가 존재한다. 예를 들어 $122 1_{4} = 15 1_{8} = 7 7_{14} = 5 5_{20} = 3 3_{34} = 1 1_{104}$ , $199 1_{10} = 7 C 7_{16}$ 이다.

7진법에서 101₇은 5²=34₇의 2배이기 때문에, 다음과 같이 여러 101₇의 배수들은 제곱수인 회문수가 된다.

13²	=	202
26²	=	1111
55²	=	4444
101²	=	10201
143²	=	24442

18진법에서, 다음과 같이 여러 7의 거듭제곱수들은 회문수가 된다.

7⁰	=	1
7¹	=	7
7³	=	111
7⁴	=	777
7⁶	=	12321
7⁹	=	1367631

24진법에서, 다음과 같이 첫 여덟제곱을 포함하여 여러 거듭제곱수들은 회문수가 된다.

5⁰	=	1
5¹	=	5
5²	=	11
5³	=	55
5⁴	=	121
5⁵	=	5A5
5⁶	=	1331
5⁷	=	5FF5
5⁸	=	14641
5^A	=	15AA51
5^C	=	16FLF61

자연수 $n$ 에 대해 $n - 1$ 진법에서는 $1 1_{n - 1}$ 로 회문수가 되고, $2 \leq b < n - 1$ 인 모든 $b$ 진법에서 회문수가 아닌 수를 강한 비회문수라 한다.

라이크렐 수

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

회문 알고리즘을 거쳤을 때 결코 회문수가 되지 않는 수를 라이크렐 수라고 하며, 라이크렐 수가 존재하는지는 아직 밝혀지지 않았지만 196을 포함한 여러 수들을 라이크렐 수로 추측하고 있다.^[3] 라이크렐 수의 후보로는 196, 879, 1997 등이 있다.

현재 가장 늦게 회문수가 되는 수는 12,000,700,000,025,339,936,491로, 288단계 후에 142자리의 회문수 44562665878976437622437848976653870388884783662598425855963436955852489526638748888307835667984873422673467987856626544에 도달한다.

회문수의 합

2018년에는 밑이 5 이상인 기수법에서 모든 양의 정수는 세 회문수의 합으로 표현할 수 있음을 증명하는 논문이 게재되었다.^[4]

또한 회문수의 역수들의 합은 수렴하는 수열이 되며, 수렴값은 3.37028...이다. (OEIS의 수열 A118031)

같이 보기

각주

↑ (OEIS의 수열 A065379) The next example is 19 digits - 900075181570009.
↑ Murray S. Klamkin (1990), Problems in applied mathematics: selections from SIAM review, p. 520.
↑ O'Bryant, Kevin (26 December 2012). "Reply to Status of the 196 conjecture?". Math Overflow.
↑ Cilleruelo, Javier; Luca, Florian; Baxter, Lewis (2016년 2월 19일). “Every positive integer is a sum of three palindromes”. 《Mathematics of Computation》. (arXiv preprint)

외부 링크

(영어) 196 회문수 찾기 세계신기록
(영어) Wade Van Landingham의 페이지
(영어) Wolfram mathworld의 196-알고리즘 소개 페이지

[1] (OEIS의 수열 A065379) The next example is 19 digits - 900075181570009.

[2] Murray S. Klamkin (1990), Problems in applied mathematics: selections from SIAM review, p. 520.

[3] O'Bryant, Kevin (26 December 2012). "Reply to Status of the 196 conjecture?". Math Overflow.

[4] Cilleruelo, Javier; Luca, Florian; Baxter, Lewis (2016년 2월 19일). “Every positive integer is a sum of three palindromes”. 《Mathematics of Computation》. (arXiv preprint)

[1]

[2]

[3]

[4]