A Realization of Real-time Sequence Generator for k-th Powers of Natural Numbers by One-Dimensional Cellular Automata

Abstract

A cellular automaton (CA) is a well-studied non-linear computational model of complex systems in which an infinite one-dimensional array of finite state machines (cells) updates itself in a synchronous manner according to a uniform local rule. A sequence generation problem on the CA model has been studied for a long time and a lot of generation algorithms has been proposed for a variety of non-regular sequences such as { 2^n | n = 1, 2, 3, ... }, primes, Fibonacci sequences etc. In this paper, we study a real-time sequence generation algorithm for k-th powers of natural numbers on a CA . In the previous studies, Kamikawa and Umeo (2012, 2019) showed that sequences { n^2 | n = 1, 2, 3, ...}, { n^3 | n = 1, 2, 3, ... } and { n^4 | n = 1, 2, 3, ... } can be generated in real-time by one-dimensional CA s. We extend the generation algorithm for { n^4 | n = 1, 2, 3, ... } shown by Kamikawa and Umeo, and present a generation algorithm for the sequence { n^k | n = 1, 2, 3, ... } implemented.