5
$\begingroup$

Firstly, I have a hard time expressing my question. (English is my second language and I have no math education. If you know what I mean, please edit the question.)

Suppose, $a_{1,n} ; a_{2,n} ; a_{3,n} ;a_{4,n}; ...$ series are given. All the elements included in these series are Natural Numbers: $\left\{a_{1,n} ; a_{2,n} ; a_{3,n} ;a_{4,n}; ....\right\}\in \mathbb{Z^{+}}.$

I would like to give an example before asking my question.

$a_{1,n}= \left\{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,... \right\}$

$a_{2,n}=\left\{1,3,4,5,6,7,8,9,13,15,17,19,20...\right\}$

$a_{3,n}=\left\{1,5,7,9,11,14,19,20...\right\}$

We see that, for sequence $a_{1,n}$ the distribution of numbers is more "orderly" than for sequence $a_{2,n}.$ For sequence $a_{2,n}$ the distribution of numbers is more "orderly" for sequence $a_{3,n}.$ By "orderly", I mean the denser settlement of the positive integer numbers. We can define the sequence of $a_{1,n}$ as the "most orderly" sequence.

For example: The numbers in sequence $a_{4,n}$ are more "orderly distributed" than from sequence $a_{5,n}.$

$a_{4,n}=\left\{1,2,3,4,5,6,7,8,9,11,13,15,17,19,21,23,25 ...\right\}$

$a_{5,n}=\left\{1,7,9,13,17,19,21,23,25...\right\}$

How can I say that the sequence of $a_{3,n}$ is more "orderly" than the sequence of $a_{5,n}?$

I can not say which sequences/series are more "orderly", because I have no mathematical criterion to do this. Is there a theory that deals with the distribution of positive integer numbers? For example, which sequence of numbers are more "orderly distributed?"

$\endgroup$
  • 1
    $\begingroup$ It's hard for me to understand how you define your sequences $\endgroup$ – Yuriy S Mar 10 '18 at 19:45
  • 4
    $\begingroup$ Maybe you're looking for asymptotic density? $\endgroup$ – Noah Schweber Mar 10 '18 at 19:45
  • $\begingroup$ Just in case you are not familiar, take a look at oeis.org $\endgroup$ – Yuriy S Mar 10 '18 at 19:45
  • $\begingroup$ I am not sure I understand why you think $a_{1,n}$ is more orderly than $a_{2,n}$. Both are arithmetic progressions and feel exactly the same to me. What is the criterion you have in mind? $\endgroup$ – RKD Mar 10 '18 at 19:46
  • $\begingroup$ @Noah Schweber I think Yes you are right, please help improve question Thank you! $\endgroup$ – Learner Mar 10 '18 at 19:49
8
$\begingroup$

I'm not sure to well interpret your question, but I think that what you are searching for may be something that is called algorithmic complexity (or other names that you can see here), applied to a sequence of integers numbers.

Intuitively:

the complexity of a sequence of number is the minimum lenght of a program that generate exactly this sequence.

As an example, for your sequence $a_{1,n}$ you can think to something as:

1) write $1$

2) memorize the writed number

3) write the memorized number $+1$

4) go to 2)

This is a simple ''program'' that, in some programming language can be reduced to a minimum length, and this is assumed to be the ''complexity'' of the sequence.

The other sequences in your example can be generated by other programs with different minimum length, so we can compare the ''complexities'' of different sequences.

The maximum complexity is given, in such context, for a sequence that cannot be ''compressed'' in some set of rules that generates all the numbers in the sequence. This is the case if we chose ''randomly'' any element of the sequence so that we cannot write a program that generates the numbers, but we can only list them all.

All this gives you only a partial flavor (not rigorous at all) of the fascinating theory that was developed by Kolmogorov and Chaitin in the years '60 where we encounter many questions about complexity, randomness and incompleteness.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ And Solomonoff should get some credit, too, I think. :) $\endgroup$ – paul garrett Mar 10 '18 at 21:47
  • $\begingroup$ I agree. Chaitin is the pop-star of algorithmic complexity thanks to his popular books, but it always cites Solomonoff and Kolmogorov. $\endgroup$ – Emilio Novati Mar 11 '18 at 9:23
3
$\begingroup$

Your line of thought is studied in calculus under the topics of sequences and subsequences. In your examples the $$ a_{1,n}= \left\{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25... \right\}$$

is called a sequence $ (a_n)$ defined by $$a_n=n$$ for $n=1,2,3,...$

The next one $$a_{2,n}=\left\{1,3,5,7,9,11,13,15,17,19,21,23,25...\right\}$$

is a subsequence denoted by $$a_{2n-1}$$ and the next one $$a_{3,n}=\left\{1,5,9,13,17,21,25...\right\}$$

is denoted by $$a_{4n-3}$$

Notice that in a proper subsequence of a sequence, the order is preserved and we are skipping some terms.

It is not always possible to retrieve the sequence form one of its subsequences.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I edited quesyion, Can you look again,thank you! $\endgroup$ – Learner Mar 10 '18 at 20:14
  • 1
    $\begingroup$ Now that you have defined the idea of orderly as having more density, we might say that a sequence is more orderly than any of its proper subsequence. This should not be interpreted as having a larger cardinality. Your examples all have the cardinality. $\endgroup$ – Mohammad Riazi-Kermani Mar 10 '18 at 20:21
  • $\begingroup$ @MohammadRiazi-Kermani for better understanding, you may calculate density of each set conntected to . $\endgroup$ – Abr001am Mar 10 '18 at 20:34
  • $\begingroup$ But $a_{3,n}$ starts out $\{1,5,7,9,\dots\}$. $\endgroup$ – Teepeemm Mar 12 '18 at 1:41
  • $\begingroup$ You are correct. Apparently it is not as orderly as I thought it would be.I made up my own $ a3,n$ $\endgroup$ – Mohammad Riazi-Kermani Mar 12 '18 at 1:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.