수학자 스타니스와프 울람(Stanisław Ulam)은 임의의 양의 정수 n(n > 0)으로부터 다음과 같은 규칙에 따라 수열을 생성하는 방법을 제안했습니다.
수열 생성 규칙
- n이 1이면 수열 생성을 종료합니다.
- n이 짝수이면, 다음 수는 n / 2 입니다.
- n이 홀수이면, 다음 수는 3 * n + 1 입니다.
- 1에 도달할 때까지 위 과정을 계속 반복합니다.
예시
처음 몇 개의 정수에 대해 적용하면 다음과 같습니다.
2 -> 1
3 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1
4 -> 2 -> 1
6 -> 3 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1
7 -> 22 -> 11 -> 34 -> 17 -> 52 -> 26 -> 13 -> 40 -> 20 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1
참고로 이 수열은 콜라츠 추측(Collatz Conjecture), 즉 '3n+1 문제'라고도 불리며, 어떤 양의 정수에서 시작하더라도 반드시 1에 도달한다는 내용의 유명한 미해결 수학 문제이기도 합니다.
이제 숫자 하나를 입력받아 해당 숫자로 시작하는 울람 수열 전체를 배열로 반환하는 자바스크립트 함수를 작성해 보겠습니다.
구현 코드
const num = 7;
const generateUlam = num => {
const res = [num];
if(num && num === Math.abs(num) && isFinite(num)){
while (num !== 1) {
if(num % 2){
num = 3 * num + 1;
}else{
num /= 2;
};
res.push(num);
};
}else{
return false;
};
return res;
};
console.log(generateUlam(num));
console.log(generateUlam(3));
코드 설명
- 먼저 시작 숫자를 담은 결과 배열
res를 초기화합니다. - 입력값이 유효한 양의 유한 숫자인지 검사하여, 유효하지 않으면
false를 반환합니다. num이 1이 될 때까지 반복하면서, 홀수이면3 * num + 1을, 짝수이면num / 2를 계산합니다.- 매 단계의 결과를 배열에 추가(
push)하여 최종적으로 전체 수열을 반환합니다.
실행 결과
콘솔 출력 결과는 다음과 같습니다.
[
7, 22, 11, 34, 17, 52, 26,
13, 40, 20, 10, 5, 16, 8,
4, 2, 1
]
[
3, 10, 5, 16,
8, 4, 2, 1
]