Cyclic number

순환 숫자(cyclic number)는 자릿수의 순환 순열(cyclic permutations)이 그 숫자의 연속적인 정수 배수인 정수입니다. 가장 널리 알려진 숫자는 6-자리 숫자 142857이며, 처음 6개의 정수 배수는 다음과 같습니다:

142857 × 1 = 142857

142857 × 2 = 285714

142857 × 3 = 428571

142857 × 4 = 571428

142857 × 5 = 714285

142857 × 6 = 857142

Details

순환 숫자로 자격을 갖추려면, 그것은 연속 배수가 순환 순열이어야 합니다. 따라서, 숫자 076923은 심지어 모든 순환 순열이 배수이지만 연속적인 정수 배수가 아니기 때문에 순환 숫자로 고려되지 않습니다:

076923 × 1 = 076923

076923 × 3 = 230769

076923 × 4 = 307692

076923 × 9 = 692307

076923 × 10 = 769230

076923 × 12 = 923076

다음 자명한 경우는 전형적으로 제외됩니다:

단일 자릿수, 예를 들어: 5
반복된 자릿수, 예를 들어: 555
반복된 순환 숫자, 예를 들어: 142857142857

만약 선행하는 영들이 숫자-표시에 허용되지 않으면, 다음 섹션에 제공된 필수 구조로 인해 142857이 십진수에서 유일한 순환 숫자입니다. 선행하는 영들을 허용하면, 순환 숫자의 수열이 시작됩니다.

(10⁶ − 1) / 7 = 142857 (6 자릿수)

(10¹⁶ − 1) / 17 = 0588235294117647 (16 자릿수)

(10¹⁸ − 1) / 19 = 052631578947368421 (18 자릿수)

(10²² − 1) / 23 = 0434782608695652173913 (22 자릿수)

(10²⁸ − 1) / 29 = 0344827586206896551724137931 (28 자릿수)

(10⁴⁶ − 1) / 47 = 0212765957446808510638297872340425531914893617 (46 자릿수)

(10⁵⁸ − 1) / 59 = 0169491525423728813559322033898305084745762711864406779661 (58 자릿수)

(10⁶⁰ − 1) / 61 = 016393442622950819672131147540983606557377049180327868852459 (60 자릿수)

(10⁹⁶ − 1) / 97 = 010309278350515463917525773195876288659793814432989690721649484536082474226804123711340206185567 (96 자릿수)

Relation to repeating decimals

순환 숫자는 단위 분수(unit fractions)의 반복되는 디지털 표현과 관련이 있습니다. 길이 L의 순환 숫자는 다음의 디지털 표현입니다:

1/(L + 1).

반대로, 만약 if the digital period of 1/p의 디지털 주기는 다음과 같으면, (여기서 p는 소수(prime))

p − 1,

자릿수는 순환 숫자를 나타냅니다.

예를 들어:

1/7 = 0.142857 142857...

이러한 분수의 배수는 순환 순열을 나타냅니다:

1/7 = 0.142857 142857...

2/7 = 0.285714 285714...

3/7 = 0.428571 428571...

4/7 = 0.571428 571428...

5/7 = 0.714285 714285...

6/7 = 0.857142 857142...

Form of cyclic numbers

단위 분수와의 관계에서, 순환 숫자는 페르마 몫(Fermat quotient)의 형식임을 알 수 있습니다:

{\frac {b^{p-1}-1}{p}}

여기서 b는 숫자 밑수 (십진수에 대해 10)이고, p는 b를 나누지 않는 소수(prime)입니다. (밑수 b에서 순환 숫자를 제공하는 소수 p는 밑수 b에서 전체 반복 소수(full reptend primes) 또는 긴 소수라고 합니다.)

예를 들어, b = 10에 대해, p = 7은 순환 숫자 142857을 제공하고, b = 12에 대해, p = 5는 순환 숫자 2497을 제공합니다.

p의 모든 값이 이 공식을 사용하여 순환 숫자를 생성하는 것은 아닙니다; 예를 들어, b = 10에 대해, p = 13은 076923076923를 제공하고, b = 12에 대해, p = 19는 076B45076B45076B45를 제공합니다. 이들 실패한 사례는 항상 반복되는 자릿수 (여러 개도 가능)를 포함합니다.

이 공식이 순환 숫자를 십진수 (b = 10)에서 생성하는 p의 첫 번째 값은 다음과 같습니다 (OEIS에서 수열 A001913):

7, 17, 19, 23, 29, 47, 59, 61, 97, 109, 113, 131, 149, 167, 179, 181, 193, 223, 229, 233, 257, 263, 269, 313, 337, 367, 379, 383, 389, 419, 433, 461, 487, 491, 499, 503, 509, 541, 571, 577, 593, 619, 647, 659, 701, 709, 727, 743, 811, 821, 823, 857, 863, 887, 937, 941, 953, 971, 977, 983, ...

b = 12 (십이진수)에 대해, 이들 p는 다음과 같습니다 (OEIS에서 수열 A019340):

5, 7, 17, 31, 41, 43, 53, 67, 101, 103, 113, 127, 137, 139, 149, 151, 163, 173, 197, 223, 257, 269, 281, 283, 293, 317, 353, 367, 379, 389, 401, 449, 461, 509, 523, 547, 557, 569, 571, 593, 607, 617, 619, 631, 641, 653, 691, 701, 739, 751, 761, 773, 787, 797, 809, 821, 857, 881, 929, 953, 967, 977, 991, ...

b = 2 (이진수)에 대해, 이들 p는 다음과 같습니다 (OEIS에서 수열 A001122):

3, 5, 11, 13, 19, 29, 37, 53, 59, 61, 67, 83, 101, 107, 131, 139, 149, 163, 173, 179, 181, 197, 211, 227, 269, 293, 317, 347, 349, 373, 379, 389, 419, 421, 443, 461, 467, 491, 509, 523, 541, 547, 557, 563, 587, 613, 619, 653, 659, 661, 677, 701, 709, 757, 773, 787, 797, 821, 827, 829, 853, 859, 877, 883, 907, 941, 947, ...

b = 3 (삼진수)에 대해, 이들 p는 다음과 같습니다 (OEIS에서 수열 A019334):

2, 5, 7, 17, 19, 29, 31, 43, 53, 79, 89, 101, 113, 127, 137, 139, 149, 163, 173, 197, 199, 211, 223, 233, 257, 269, 281, 283, 293, 317, 331, 353, 379, 389, 401, 449, 461, 463, 487, 509, 521, 557, 569, 571, 593, 607, 617, 631, 641, 653, 677, 691, 701, 739, 751, 773, 797, 809, 811, 821, 823, 857, 859, 881, 907, 929, 941, 953, 977, ...

십육진수 시스템에서 그러한 p는 없습니다.

이 수열에 대한 알려진 패턴은 대수적 숫자 이론(algebraic number theory)에서 나옵니다. 구체적으로, 이 수열은 b가 원시 근 모듈로 p인 소수 p의 집합입니다. 에밀 아르틴의 추측에 따르면 이 수열은 소수의 37.395..%를 포함하고 있습니다^[1] (OEIS: A085397에서 b에 대해).

Construction of cyclic numbers

순환 숫자는 다음 절차에 따라 구성될 수 있습니다:

Let b be the number base (10 for decimal)
Let p be a prime that does not divide b.
Let t = 0.
Let r = 1.
Let n = 0.
loop:

    Let t = t + 1
    Let x = r · b
    Let d = int(x / p)
    Let r = x mod p
    Let n = n · b + d
    If r ≠ 1 then repeat the loop.

if t = p − 1 then n is a cyclic number.

이 절차는 긴 나눗셈(long division)에 의해 밑수 b에서 1/p의 자릿수를 계산함으로써 작동합니다. r은 각 단계에서 나머지(remainder)이고, d는 생성된 숫자입니다.

다음 단계는

n = n · b + d

단순히 숫자를 수집하는 역할을 합니다. 매우 큰 정수를 표현할 수 없는 컴퓨터에 대해, 자릿수는 또 다른 방법으로 출력되거나 수집될 수 있습니다.

만약 t가 p/2를 초과하면, 그 숫자는 남아있는 자릿수를 계산할 필요 없이 주기적이어야 합니다.

Properties of cyclic numbers

생성하는 소수를 곱했을 때, 그 결과는 b − 1 자릿수의 수열이며, 여기서 b는 밑수입니다 (예를 들어, 십진법 9). 예를 들어, 십진수에서, 142857 × 7 = 999999입니다.
같은 길이의 그룹 (2, 3, 4, 등...의 자릿수)으로 나누고, 그룹을 더할 때, 그 결과는 9들의 수열입니다. 예를 들어, 14 + 28 + 57 = 99, 142 + 857 = 999, 1428 + 5714+ 2857 = 9999, 등... 이것은 미디의 정리(Midy's Theorem)의 특수한 경우입니다.
모든 순환 숫자는 b − 1로 나눌 수 있으며, 여기서 b는 밑수 (예를 들어, 십진수에서 9)이고 나머지의 합은 약수의 배수입니다. (이것은 이전 요점에서 이어집니다.)

Other numeric bases

위의 기술을 사용하여, 순환 숫자는 다른 숫자-표시 밑수에서 찾을 수 있습니다. (이들 모두가 위의 특별 사례 섹션에 나열된 두 번째 규칙 (모든 연속적인 배수는 순환 순열임)을 따르는 것은 아닙니다.) 이들 각각의 경우에서, 구간의 절반에 걸친 자릿수는 밑수 빼기 1까지 합해집니다. 따라서 이진수에 대해, 주기의 절반에 걸친 비트의 합은 1입니다; 삼진수에 대해, 그것은 2, 이런 식입니다.

이진수(binary)에서, 순환 숫자의 수열은 다음과 같이 시작됩니다: (OEIS에서 수열 A001122)

11 (3) → 01

101 (5) → 0011

1011 (11) → 0001011101

1101 (13) → 000100111011

10011 (19) → 000011010111100101

11101 (29) → 0000100011010011110111001011

삼진수(ternary)에서: (OEIS에서 수열 A019334)

2 (2) → 1

12 (5) → 0121

21 (7) → 010212

122 (17) → 0011202122110201

201 (19) → 001102100221120122

사진수(quaternary)에서, 어떤 것도 없습니다.

오진수(quinary)에서: (OEIS에서 수열 A019335)

2 (2) → 2

3 (3) → 13

12 (7) → 032412

32 (17) → 0121340243231042

43 (23) → 0102041332143424031123

122 (37) → 003142122040113342441302322404331102

육진수(senary)에서: (OEIS에서 수열 A167794)

15 (11) → 0313452421

21 (13) → 024340531215

25 (17) → 0204122453514331

105 (41) → 0051335412440330234455042201431152253211

135 (59) → 0033544402235104134324250301455220111533204514212313052541

141 (61) → 003312504044154453014342320220552243051511401102541213235335

밑수 7에서: (OEIS에서 수열 A019337)

2 (2) → 3

5 (5) → 1254

14 (11) → 0431162355

16 (13) → 035245631421

23 (17) → 0261143464055232

32 (23) → 0206251134364604155323

팔진수(octal)에서: (OEIS에서 수열 A019338)

3 (3) → 25

5 (5) → 1463

13 (11) → 0564272135

35 (29) → 0215173454106475626043236713

65 (53) → 0115220717545336140465103476625570602324416373126743

73 (59) → 0105330745756511606404255436276724470320212661713735223415

구진수(nonary)에서, 고유한 순환 숫자는 다음과 같습니다:

2 (2) → 4

밑수 11에서: (OEIS에서 수열 A019339)

2 (2) → 5

3 (3) → 37

12 (13) → 093425A17685

16 (17) → 07132651A3978459

21 (23) → 05296243390A581486771A

27 (29) → 04199534608387A69115764A2723

십이진수(duodecimal)에서: (OEIS에서 수열 A019340)

5 (5) → 2497

7 (7) → 186A35

15 (17) → 08579214B36429A7

27 (31) → 0478AA093598166B74311B28623A55

35 (41) → 036190A653277397A9B4B85A2B15689448241207

37 (43) → 0342295A3AA730A068456B879926181148B1B53765

삼진수 (b = 3)에서, 경우 p = 2는 순환 숫자로 1을 산출합니다. 단일 자릿수는 자명한 경우로 고려될 수 있지만, 그것들은 이러한 방법에서 생성된 경우에만 고려하는 것이 이론의 완성도에 유용할 수 있습니다.

밑수 4, 9, 16, 25 등의 완전 제곱(perfect square)인 임의의 숫자-표시 밑수에는 순환 숫자가 (자명한 단일 자릿수, 즉, p = 2 이외의) 존재하지 않는다는 것을 알 수 있습니다.

References

^ Weisstein, Eric W. "Artin's Constant". mathworld.wolfram.com.

External links

[1] Weisstein, Eric W. "Artin's Constant". mathworld.wolfram.com.

[1]