Analysis on Behavioral Similarity of N-Puzzle with 3n+1 Problem
0
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
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.
Abstract
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.
참고문헌 (16)
- F. C. Motta, "An analysis of the Collatz Conjecture"
- G. T. Leavens, "3x+1 search programs", Comput. Math. Appl., 24(11), pp.79~99 (1992)
- S. A. Kurtz, "The undecidability of the generalized Collatz problem;Theory and Applications of Models of Computation", 4-th International Conference, TAMC 2007 (2007)
- M. Winkler, "New results on the stopping time behaviour of the Collatz 3x+1 function", ~ (2015)
- L. Berg, "An analytic approach to the Collatz 3n+1 problem for negative start values", Computational Methods and Function Theory, 13, pp.225~236 (2013)[DOI]
- J. C. Lagarias, "The 3x+1 Problem: An annotated bibliography (1963-1999) (sorted by author)", ~
- M. Chamberland, "An update on the 3x + 1 problem (in Catalan)", Butlleti de la Societat Catalana de Matematiques, 18, pp.19~45 (2003)
- J. LAGARIAS, "The 3x + 1 problem and its generalizations", Amer. Math. Monthly, 92, pp.3~ (1985)[DOI]
- J. Kaiser, "On the relationship between the Collatz conjecture and Mersenne prime numbers", ~
- [URL]
- [URL]
- A. Reinefeld, "Complete solution of the Eight-puzzle and the benefit of node ordering in IDA*", Proc. 13th Int. Joint Conf. on Artificial Intell., pp.248~253 (1993)
- A. Drogul, "A distributed approach to N-puzzle solving", the proceedings of the 13th DAI Workshop
- D. Ratner, "Finding a shortest solution for the NxN extension of the 15-puzzle is intractable", AAAI-86 Proceedings
- Juan A. Perez, "Collatz Conjecture: Is it False?", ~
- I. Ahmad, "N-Puzzle: A General Application of 3n+1 Problem", The 3rd International Conference on Next Generation Computing(ICNGC2017b), pp.97~100 (2017)