Kaprekar Constant ( 카프리카 상수 )

1. 카프리카 상수란

인도 수학자인 D.R.카프리카가 발견한 숫자이다.

base(진수)와 digit(자리수)에 따라

정수의 자릿수를 내림차순으로 정렬한 정수 - 올림차순으로 정렬한 정수 = 기존 정수를 만족하는 수를 카프리카 상수라고 한다.

(단 모든 자릿수가 같아서는 안된다.)

간단하게 예를 보자.

base가 10, digit이 4라고 정해져있다고 하자.

그러면 0000 ~ 9999까지 정수가 있을 것이다. 하지만 조건에 의해 모든 자릿수가 같으면 안되므로 0000 1111 2222 ~ 9999 같은 자릿수 4개가 모두 동일한 수는 제외한다.

이 정수중에서 하나인 2134를 뽑았다하면,

2134의 자릿수를 내림차순으로 정렬한 정수인 4321 오름차순으로 정렬한 정수인 1234 이 둘의 차는 3087이다.

3087은 2134와 같지 않으므로 2134는 카프리카 상수가 아니다.

그럼 6174라는 수를 살펴보자.

6174 = 7641 - 1467 이므로 6174는 카프리카 상수이다.(base 10 digit 4의 카프리카 상수는 단 한개 6174 밖에 존재하지 않는다.)

이런 카프리카 상수는 base나 digit에 따라 달라지며 존재하지 않을 수도, 많이 존재할 수도 있다.

2. T operation

위에서 보았듯이 정수의 자릿수를 내림차순으로 정렬한 정수 - 올림차순으로 정렬한 정수

이를 T operation이라 한다 예를들어

T(6174) = 6174

T(2134) = 3087

T(a) = a 를 만족하는 a가 카프리카 상수라고 할 수 있다.

base 10 digit 4의 모든 정수들은 (단 모든 자리수가 같아서는 안된다.) T operation을 반복했을때,

결국 카프리카 상수인 6174로 온다고 알려져있다.

무슨말이나면

T(2134) = 3087

T(3087) = 8352

T(8352) = 6174

이렇듯 계속 T operation을 반복하면 6174로 모이게 된다.

( 모든 수는 7번 이내의 T operation수행하여 6174가 될 수 있다. )

 

3. 카프리카 상수 프로그램 (Kaprekar Constant Program)

이 프로그램은 base와 digt이 주어져 있을 때, 카프리카 상수를 구해주는 프로그램이다.

이 프로그램은 입력을 받지 않으므로 #define으로 되어있는 base와 digit을 사용자가 스스로 변경해 주어야 한다.

주석 처리가 되어있는 부분은 T operation의 반복을 print해주는 부분이므로 모든 수가 kaprekar constant로 귀결되는지 눈으로 확인하려면 주석을 해제해보면 된다.

Colored By Color Scripter™

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91

#include <stdio.h> #define digit 4 #define base 10 //digit 1은 불가능   int T_operation(int dec);   int main() {     int i,j;     int temp, temp2;     int limit = 1;     int check = 0;     int caprekar_constant[100];     int n=0;       for (i = 0; i < digit; i++)         limit *= base;     for (i = 0; i < digit; i++)     {         check *= base;         check += 1;     }       for (i = 1; i < limit; i++)     {         if (i % check)         {             if (i == T_operation(i))             {                 printf("%d is caprekar constant - digit %d\n", i, digit);                 caprekar_constant[n++] = i;             }         }     }     if (n == 0)     {         printf("This is not Kaprekar constant\n");         return 0;     }     /*     for (i = 1; i < limit; i++)     {         temp = i;         if (i % check)         {             do             {                 printf("%d ", temp);                 temp2 = temp;             } while ((temp = T_operation(temp)) != temp2);             printf("\n");                      }     }     */     return 0; } int T_operation(int dec) {     int i,j;     int arr[digit];     int temp;       for (i = 0; i < digit; i++)     {         arr[i] = dec % base;         dec /= base;     }       for (i = 0; i < digit ; i++)     {         for (j = 0; j+1 < digit-i; j++)         {             if (arr[j] < arr[j + 1])             {                 temp = arr[j];                 arr[j] = arr[j + 1];                 arr[j + 1] = temp;             }         }     }     //dec은 이미 0이기에 초기화 불필요     for (i = 0; i < digit; i++)     {         dec *= base;         dec += arr[i] - arr[digit - 1 - i];     }       return dec; }