숫자 팰린드롬(palindrome)

펠린드롬이란?

회문(回文) 또는 팰린드롬(palindrome)은 거꾸로 읽어도 제대로 읽는 것과 같은 문장이나 낱말이다. 보통 낱말 사이에 있는 띄어쓰기나 문장 부호는 무시한다.

그렇다.내이름은 '이효리' 거꾸로 읽어도 '이효리'! 같은 단어나 문장을 회문 또는 팰린드롬이라고 부른다.

팰린드롬과 관련해서 흥미로운 수학적 관찰이 있다. 그것은 컴퓨터학자 그루엔버거(F.Gruenberger)는 1984년에 미국의 잡지 "사이언티픽 아케리칸(Scientific American)"에 실린 '컴퓨터 레크리에이션(Computer Recreations)'이라는 칼럼에서 다음과 같은 재미있는 알고리즘을 제기해서 많은 사람의 관심을 끌었다.

1) 숫자를 아무거나 고른다.

2)그 수를 뒤집는다. 그 다음 뒤집어진 수와 원래의 수를 더한다.
ex) 13을 골랐으면 31. 즉 13+31
3) 두 수를 더한 결과가 팰린드롬이 아니면 다시 2로 돌아간다. 
팰린드롬이라면 알고리즘을 종료

예를 들면 87을 입력한다면,

87 + 78 =165

165+561= 726

726+627 =1353

1353+3531=4884 

이런식으로 진행한다. 

위의 내용은 "누워서 읽는 알고리즘" -임백준-(p71-72) 책에서 인용했다. 

책을 읽고서 Java로 한번 알고리즘을 구현해보았다. 

import java.util.Scanner;
 
class Main {
    static Boolean isPalidrom(int num) {
        // Pelindrom인지 체크 하는 Method
        String textNum = Integer.toString(num);
        if (textNum.length() != 1) {
            for (int i = 0; i < textNum.length(); i++) {
                if (textNum.charAt(i) != textNum
                        .charAt(textNum.length() - 1 - i)) {
                    return false;
                }
            }
        } else {
            return true;
        }
        return true;
    }
 
    static int burger(int num) {
        int reverseNum = 0;
        int resultNum = 0;
        int firstNum = num;
        while (num > 0) {
            int i = 10;
            while (10 <= num / i) {// 자릿수 곱하기 num/i가 10이하의 숫자이면 i의 자릿수 증가
                i *= 10;
            }
            if (num > 0 && num < 10) {// num이 일의 자릿수이면
                reverseNum += num;
            } else {// num이 십의자리 이상이면
                reverseNum += num % 10 * i;
            }
            num /= 10;
        }
        resultNum = firstNum + reverseNum;
        System.out.println(firstNum + "+" + reverseNum + "=" + resultNum);
        return resultNum;
    }
 
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int num = sc.nextInt();
        do {
            if(num<0)
            {
                break;
            }
            num = burger(num);
            
        } while (!isPalidrom(num));
 
    }
}
 

그치만 책에선 모든 수가 팰린드롬이냐고 물었을 때 지금은 모든 수는 아니라고 말할 수 있다. 

즉 알고리즘을 진행할 때 팰린드롬이 나오지 않은 수가 있다는 것이다. 물론 현재까지 밝혀지지가 않았다. 앞으로 미래에는 팰린드롬을 발견할수도 있다. 

그 수는 196이다. 

그래서 다른 수를 알고리즘에 돌려보면서 알고리즘이 제대로 작동하는지 확인해보았고 잘 맞는다고 판단하였다. 

그리고서 196을 넣어봤더니..

이런식으로 마지막엔 -값이 나와버렸다.(값의 범위를 넘어버려서 -값이 나왔다.)

혹시 BigInteger로 해보면 나오지 않을까 하고서 다시 int를 BigInteger형으로 바꾸어서 구해보았다. 아래 소스는 BigInteger로 바꾼 소스이다. 

import java.math.BigInteger;
import java.util.Scanner;
 
class Main {
 
    static Boolean isPalidrom(BigInteger num) {
        //Pelindrom인지 체크 하는 Method
        //String textNum = Integer.toString(num);
        String textNum=num.toString();
        if (textNum.length() != 1) {
            for (int i = 0; i < textNum.length(); i++) {
                if (textNum.charAt(i) != textNum.charAt(textNum.length() - 1 - i)) {
                    return false;
                }
            }
        } else {
            return true;
        }
        return true;
    }
 
    static BigInteger burger(BigInteger num) {
 
        BigInteger resultNum =new BigInteger("0");
        BigInteger reverseNum=new BigInteger("0");
        BigInteger firstNum = num;
        while (num.intValue() > 0) {
            BigInteger i = new BigInteger("10");
            while (10 <= num.divide(i).intValue()) {//자릿수 곱하기 num/i가 10이하의 숫자이면 i의 자릿수 증가
                i=i.multiply(BigInteger.TEN);
            }
            if (num.intValue() > 0 && num.intValue() < 10) {//num이 일의 자릿수이면
                reverseNum=reverseNum.add(num);
            } else {//num이 십의자리 이상이면
                reverseNum=reverseNum.add((num.mod(BigInteger.valueOf(10)).multiply(i)));
            }
          num=num.divide(BigInteger.valueOf(10));
        }
        resultNum=firstNum.add(reverseNum);
        System.out.println(firstNum.toString() + "+" + reverseNum.toString() + "=" + resultNum.toString());
        return resultNum;
    }
 
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        BigInteger num = sc.nextBigInteger();
        do {
 
            num = burger(num);
            if(num.intValue()<0)
            {
                break;
            }
        } while (!isPalidrom(num));
 
    }
}
 

이 소스를 실행하고서 196을 입력하였다. 

그래도 팰린드롬을 찾는데에는 실패했다. 역시 슈퍼컴퓨터도 아니고 찾기는 무리겠지 ㅠㅠ 

그러다가 인터넷 검색을 하다가 4994는 그 자체가 펠린드롬이면서 알고리즘을 수행하면 펠린드롬을 찾을 수 없는 수라는 것을 알았다. 

진짜 수학은 아직 인간에겐 모르는것이 너무 많다! 

결론 : 어떤 임의의 숫자를 숫자 펠린드롬 알고리즘을 적용해서 팰린드롬을 못찾을 수 있다.

(즉,현재까지 모든 수에는 무조건 팰린드롬이 존재하는 것은 아니다.)