[PYTHON] Natural number generator
It is a natural number that I use casually, but it needs to be defined strictly in order to handle it in mathematics. This time, I will show you how to do it. Below is a matter of personal preference, but natural numbers start at $ 0 $.
How to make natural numbers
Natural numbers start at $ 0 $ (or $ 1 $) and have the property of being infinite and in a row. Of course, it doesn't break, branch, or merge anywhere. The properties that such natural numbers must satisfy are defined by the "Peano axioms". Regarding Peano's axioms, I think it would be good if you could refer to "Beautiful story of high school mathematics: What is a natural number (may include 0)". In addition, it is discussed in detail and in an easy-to-understand manner in "Mathematics Girl Goedel's Incompleteness Theorem".
However, Peano's axiom only mentions the condition for being a natural number. There is no problem with this, but one of the algorithms that formally defines those that satisfy these conditions, that is, gives substance to natural numbers, is "Von Neumann's construction method". In the words of an engineer, is it an image of defining the requirements for natural numbers using Peano's axioms and coding with Neumann's construction method? Neumann's construction method uses sets (something like {1, 2, 3}) to generate something that satisfies Peano's axioms.
In Neumann's construction method, $ 0 $ is the first natural number, and the natural number is defined as follows.
\begin{eqnarray}
0 &:=& \{\} \\
1 &:=& \{0\} = \{\{\}\} \\
2 &:=& \{1,\ 0\} = \{\{\{\}\},\ \{\}\} \\
3 &:=& \{2,\ 1,\ 0\} = \{\{\{\{\}\},\ \{\}\},\ \{\{\}\},\ \{\}\}
\end{eqnarray}
After that, it is repeated.
Arrangement of algorithms
Create an algorithm that defines natural numbers according to Neumann's construction method. The goal is to create a program that outputs the definition as a standard character string when an integer of $ 0 $ or more is input.
In Neumann's construction method, we first define 0 = {} and then recursively define it using only the already defined natural numbers. Ultimately, natural numbers are represented by only three types of characters: {, }, ,. I will put an image diagram.
All you have to do is output this character by character from the left.
Implementation
Click here for the source code. I'm using python 3.7.
natural_number_generator.py
import sys
#Natural number generator
def neumann_algorithm(target_num: int):
processing = target_num - 1
yield '{'
while processing >= -1:
# (1)
if processing == -1:
yield '}'
return 0
else:
natural_number_generator = neumann_algorithm(processing)
yield from natural_number_generator
# (2)
if processing == 0:
yield '}'
return 0
else:
yield ', '
processing -= 1
return 0
#Get input value
def get_input_num():
args = sys.argv
input_num = int(args[1])
return input_num
if __name__ == "__main__":
target_num = get_input_num()
natural_number_generator = neumann_algorithm(target_num)
for char in natural_number_generator:
print(char, end='')
Source code explanation
The neumann_algorithm function in the source code is the algorithm that generates natural numbers. Inside the function, there are two branches, (1) and (2) (see comments in the source code). I will put a brief explanation on it.
(1) is the part that determines whether the value to be output from now on is $ 0 $, that is, whether it is defined or not. Since 0 = {} is defined first, you can output {} directly, but since the other numbers are not defined, you need to call the function recursively.
(2) is the part that determines whether to output } or , each time one restart process is completed.
The definition of a natural number becomes explosively long as the number increases (about $ O (2 ^ n) $) **. Therefore, if you wake it up to a string or list, you may run out of memory. To prevent this, we implemented it using a generator that can judge each character to be output and discard it when it is no longer needed. If you want to run it, we recommend you to wait for about $ 10 $.
Output result
Here is the result of entering $ 0 $ to $ 5 $ and executing it.
>python natural_number_generator.py 0
{}
>python natural_number_generator.py 1
{{}}
>python natural_number_generator.py 2
{{{}}, {}}
>python natural_number_generator.py 3
{{{{}}, {}}, {{}}, {}}
>python natural_number_generator.py 4
{{{{{}}, {}}, {{}}, {}}, {{{}}, {}}, {{}}, {}}
>python natural_number_generator.py 5
{{{{{{}}, {}}, {{}}, {}}, {{{}}, {}}, {{}}, {}}, {{{{}}, {}}, {{}}, {}}, {{{}}, {}}, {{}}, {}}
>
it is a good feeling.
By the way, I noticed when I moved it, but it seems that } does not continue more than 3 times. It is clear from the way of branching, but I was not aware of it at the stage of thinking about the algorithm. You made a new discovery.
bonus
The definition of $ 10 $.
>python natural_number_generator.py 10
{{{{{{{{{{{}}, {}}, {{}}, {}}, {{{}}, {}}, {{}}, {}}, {{{{}}, {}}, {{}}, {}}, {{{}}, {}}, {{}}, {}}, {{{{{}}, {}}, {{}}, {}}, {{{}}, {}}, {{}}, {}}, {{{{}}, {}}, {{}}, {}}, {{{}}, {}}, {{}}, {}}, {{{{{{}}, {}}, {{}}, {}}, {{{}}, {}}, {{}}, {}}, {{{{}}, {}}, {{}}, {}}, {{{}}, {}}, {{}}, {}}, {{{{{}}, {}}, {{}}, {}}, {{{}}, {}}, {{}}, {}}, {{{{}}, {}}, {{}}, {}}, {{{}}, {}}, {{}}, {}}, {{{{{{{}}, {}}, {{}}, {}}, {{{}}, {}}, {{}}, {}}, {{{{}}, {}}, {{}}, {}}, {{{}}, {}}, {{}}, {}}, {{{{{}}, {}}, {{}}, {}}, {{{}}, {}}, {{}}, {}}, {{{{}}, {}}, {{}}, {}}, {{{}}, {}}, {{}}, {}}, {{{{{{}}, {}}, {{}}, {}}, {{{}}, {}}, {{}}, {}}, {{{{}}, {}}, {{}}, {}}, {{{}}, {}}, {{}}, {}}, {{{{{}}, {}}, {{}}, {}}, {{{}}, {}}, {{}}, {}}, {{{{}}, {}}, {{}}, {}}, {{{}}, {}}, {{}}, {}}, {{{{{{{{}}, {}}, {{}}, {}}, {{{}}, {}}, {{}}, {}}, {{{{}}, {}}, {{}}, {}}, {{{}}, {}}, {{}}, {}}, {{{{{}}, {}}, {{}}, {}}, {{{}}, {}}, {{}}, {}}, {{{{}}, {}}, {{}}, {}}, {{{}}, {}}, {{}}, {}}, {{{{{{}}, {}}, {{}}, {}}, {{{}}, {}}, {{}}, {}}, {{{{}}, {}}, {{}}, {}}, {{{}}, {}}, {{}}, {}}, {{{{{}}, {}}, {{}}, {}}, {{{}}, {}}, {{}}, {}}, {{{{}}, {}}, {{}}, {}}, {{{}}, {}}, {{}}, {}}, {{{{{{{}}, {}}, {{}}, {}}, {{{}}, {}}, {{}}, {}}, {{{{}}, {}}, {{}}, {}}, {{{}}, {}}, {{}}, {}}, {{{{{}}, {}}, {{}}, {}}, {{{}}, {}}, {{}}, {}}, {{{{}}, {}}, {{}}, {}}, {{{}}, {}}, {{}}, {}}, {{{{{{}}, {}}, {{}}, {}}, {{{}}, {}}, {{}}, {}}, {{{{}}, {}}, {{}}, {}}, {{{}}, {}}, {{}}, {}}, {{{{{}}, {}}, {{}}, {}}, {{{}}, {}}, {{}}, {}}, {{{{}}, {}}, {{}}, {}}, {{{}}, {}}, {{}}, {}}, {{{{{{{{{}}, {}}, {{}}, {}}, {{{}}, {}}, {{}}, {}}, {{{{}}, {}}, {{}}, {}}, {{{}}, {}}, {{}}, {}}, {{{{{}}, {}}, {{}}, {}}, {{{}}, {}}, {{}}, {}}, {{{{}}, {}}, {{}}, {}}, {{{}}, {}}, {{}}, {}}, {{{{{{}}, {}}, {{}}, {}}, {{{}}, {}}, {{}}, {}}, {{{{}}, {}}, {{}}, {}}, {{{}}, {}}, {{}}, {}}, {{{{{}}, {}}, {{}}, {}}, {{{}}, {}}, {{}}, {}}, {{{{}}, {}}, {{}}, {}}, {{{}}, {}}, {{}}, {}}, {{{{{{{}}, {}}, {{}}, {}}, {{{}}, {}}, {{}}, {}}, {{{{}}, {}}, {{}}, {}}, {{{}}, {}}, {{}}, {}}, {{{{{}}, {}}, {{}}, {}}, {{{}}, {}}, {{}}, {}}, {{{{}}, {}}, {{}}, {}}, {{{}}, {}}, {{}}, {}}, {{{{{{}}, {}}, {{}}, {}}, {{{}}, {}}, {{}}, {}}, {{{{}}, {}}, {{}}, {}}, {{{}}, {}}, {{}}, {}}, {{{{{}}, {}}, {{}}, {}}, {{{}}, {}}, {{}}, {}}, {{{{}}, {}}, {{}}, {}}, {{{}}, {}}, {{}}, {}}, {{{{{{{{}}, {}}, {{}}, {}}, {{{}}, {}}, {{}}, {}}, {{{{}}, {}}, {{}}, {}}, {{{}}, {}}, {{}}, {}}, {{{{{}}, {}}, {{}}, {}}, {{{}}, {}}, {{}}, {}}, {{{{}}, {}}, {{}}, {}}, {{{}}, {}}, {{}}, {}}, {{{{{{}}, {}}, {{}}, {}}, {{{}}, {}}, {{}}, {}}, {{{{}}, {}}, {{}}, {}}, {{{}}, {}}, {{}}, {}}, {{{{{}}, {}}, {{}}, {}}, {{{}}, {}}, {{}}, {}}, {{{{}}, {}}, {{}}, {}}, {{{}}, {}}, {{}}, {}}, {{{{{{{}}, {}}, {{}}, {}}, {{{}}, {}}, {{}}, {}}, {{{{}}, {}}, {{}}, {}}, {{{}}, {}}, {{}}, {}}, {{{{{}}, {}}, {{}}, {}}, {{{}}, {}}, {{}}, {}}, {{{{}}, {}}, {{}}, {}}, {{{}}, {}}, {{}}, {}}, {{{{{{}}, {}}, {{}}, {}}, {{{}}, {}}, {{}}, {}}, {{{{}}, {}}, {{}}, {}}, {{{}}, {}}, {{}}, {}}, {{{{{}}, {}}, {{}}, {}}, {{{}}, {}}, {{}}, {}}, {{{{}}, {}}, {{}}, {}}, {{{}}, {}}, {{}}, {}}
>
that's all. Thank you very much.
Recommended Posts