[책-알고리즘퍼즐68]6.콜라츠 추측

문제

 수학의 미해결 문제중 하나로 콜라츠 추측이 있다.

 

 콜라츠 추측

   -n이 짝수인 경우, n을 2로 나눈다.

   -n이 홀수인 경우, n에 3을 곱해 1을 더한다.

  이 계산을 반복하면 초깃값이 어떤 수였더라도 반드시 1에 도달한다.

 

이 내용을 조금 바꾸어 초깃값이 짝수면 맨 처음에만 n에 3을 곱하여 1을 더하는 것에서 시작하기로 하고 '맨 처음의 수'로 돌아가는 법을 생각해 보자.

ex)

 2 7 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2

 4 13 40 20 10 5 16 8 4

 6 ....(6으로 돌아가지 않음)

 

10000 이하의 짝수 중 앞의 2나 4와 같이 '처음의 수로 돌아가는 수'가 몇 개 있는지 구해 보세요.

 

난이도

IQ 75

 

목표시간

15분

 

풀이(c#,VS)

1.재귀함수를 이용

2.초기값이 어떤 수더라도 반드시 1에 도달하다는 점

/*
 *2020.01.28
 * ksj
 */

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace _6_CollatzConjecture
{
    class Program
    {
        static void Main(string[] args)
        {
            int count = 0;

            for(int i=2; i<=10000; i += 2) //10000이하의 짝수 갯수만큼 반복
            {
                int num = i * 3 + 1;

                if (cal(i,num))
                {
                    count++;
                }
            }

            Console.WriteLine(count);
        }

        private static bool cal(int originalNum, int curNum)
        {
            if(originalNum == curNum)
            {
                return true;
            }

            if(curNum == 1)
            {
                return false;
            }

            if (curNum % 2 == 0)
            {
                int temp = curNum / 2;
                return cal(originalNum, temp);
            }
            else
            {
                int tmep = curNum * 3 + 1;
                return cal(originalNum, tmep);
            }
        }
    }
}

 

문제정답(사용언어:python)

1.초기값이 어떤 수더라도 반드시 1에 도달하다는 점

# 반복하며 확인
def is_loop(n):
    # 맨 처음에는 3을 곱하고 1을 더함
    check = n*3+1
    # 1이 될 때까지 숫자를 변화시키는 작업 반복
    while check !=1:
        check = check // 2 if check % 2 == 0 else check * 3 +1
        if check == n:
            return True
        
    return False

# 2~10000 범위의 짝수 확인하기
cnt = 0
for i in range(2, 10000+1,2):
    if is_loop(i):
        cnt+=1
print(cnt)