Earticle

초록

영어

3n+1 problem is well known in mathematics as arithmetically simplest to state yet hard to prove conjecture. The difficulty in finding a proof for the conjecture lies in its isolation from other mathematical areas and the fact that no pattern can be seen in the sequence. The N-puzzle is a tile game in which a sequence of moves is performed to reach goal state from any initial configuration. In this paper we present the study of 3n+1 problem’s iterations with respect to the moves of N-puzzle. We have implemented the Modified Syracuse algorithm to find length of T-trajectory of 3n+1 problem, and A* algorithm with Manhattan distance for finding optimal number of moves in N-puzzle. We have shown that in N-puzzle the sequence of optimal moves behaves similar to the random nature of 3n+1 problem iteration based on the Hamming distance and Kendall tau distance of N-puzzle initial configuration and goal state.

한국어

3n+1 문제는 산술적으로는 단순하나 이에 대한 추정을 수학적으로는 증명하기 어려운 문제로 유명하다. 이 추정에대한 증명을 찾는 것이 어려운 이유는 다른 수학 분야들과 다소 동떨어진 분야이고, 수렴하는 순서에 있어서 특정패턴이 존재하지 않는다는 사실에 있다. N-puzzle은 초기 상태로부터 최종 목적 상태에 도달하기 위해 순서적으로타일을 움직이는 타일 게임 중 하나이다. 본 논문에서는 N-puzzle 에서의 타일 이동 패턴에 대한 3n+1 문제의 반복에 따른 수렴 패턴의 유사성을 연구하였다. 3n+1 문제에 대한 T-trajectory의 길이를 찾기 위하여 변형 시라쿠스(Modified Syracuse) 알고리즘을 구현하였고, N-puzzle에서 최적의 이동수를 도출하기 위해 맨하탄 디스턴스(Manhattan Distance)를 고려한 A* 알고리즘을 구현하였다. 연구로부터 N-puzzle의 초기 상태로부터 목적 상태까지의 Hamming distance와 Kendall tau distance에 기반하여 3n+1 문제의 반복 랜덤 특성이 N-puzzle 의 최적 이동 순서와 유사한 행위를 보임을 증명하였다.

목차

요약
 Abstract
 1. Introduction
 2. 3n+1 Problem
 3. N-Puzzle
 4. Implementation Results and Analysis
 5. Conclusion
 참고문헌

키워드

3n+1문제 N-퍼즐 시라쿠스 알고리즘 A*알고리즘 맨하탄 거리 해밍 거리 켄달 타우 거리 3n+1 problem N-puzzle Syracuse Algorithm A* algorithm Manhattan distance Hamming distance Kendall tau distance

저자

• 아흐마드이자즈 [ Ahmad Ijaz | Department of Computer Engineering, Chosun University Gwangju, Republic of Korea ]
• 신석주 [ Seokjoo Shin | Department of Computer Engineering, Chosun University Gwangju, Republic of Korea ] Corresponding author

참고문헌

발행기관

간행물