What is in clear mathematical terms the definition for a sequence of integers, to be called *random*?
There is a long history of attempts to define random sequence, going back to von Mises and perhaps before.
The first reasonably successful attempt was by Per Martin-Lof. There is by now a fairly large literature. The modern notions are based on the theory of computation.
Despite the extensive literature, the opinion that random bit sequence can or should be defined is a distinctly minority view.
I totally agree with the others who have commented, in that no arbitrary sequence of numbers is inherently random. For example, the sequence of primes (as you've pointed out) have been called random, yet we know that they can be represented by a (admittedly complex) system of Diophantine equations. So they form a rather well-ordered group, but just incredibly complicated.
Probability and randomness are ways of working with uncertainty...epistemological or ontological. If you see a sequence of numbers that you can't make sense of, then viewing them as if they were generated by a random process may help you make progress (as with the primes, for example). However, no matter how successful your probability model is, unless you know how the numbers were produced, you cannot conclude that they were, in principle, not predictable with 100% certainty. A truly random process will limit the in-principle predictability to something less than 100%. Whether or not these truly exist in some philosophical sense is somewhat debated, but practically, there are many processes that are accurately modeled as inherently random processes.
As a strong counterexample to your attempt for a rigorous definition of random: even pseudo-random number generators, which drive the vast majority of simulation studies and empirical probabilistic studies, are demonstrably NOT random. Yet, pretending that they are and applying probability theory leads to generally excellent results! So, true randomness is not even needed for probability theory...so what is the utility of such a definition?
Being random is not the property of a particular sequence. It tells you how the sequence was obtained, not what it looks like.
A longer answer:
The question
Is the sequence $$1,4,2,4,5,2,3,4,6,2,1,3$$ random or not?
Is not a valid question and cannot be answered. The sequence can be either, depending on how it was obtained.
- If I obtaned my sequence by rolling a $6$ sided die $12$ times, then the sequence was obtained in a "random" way. My rolling of the die was a random number generator that generated one of the $6^{12}$ possible sequences of length $12$, and it selected that particular sequence completely at random.
- If I walked along my street and wrote how many people live in each of the first $12$ houses I walked past, then the process of creating the sequence can hardly be calles random, as there was no random generator involved in creating it.
My point is that "randomness" is not a property that can be attributed to a series of numbers, we can only say that the process that created the numbers is random (or, if it is not, deterministic).
A more "down to earth" example to convey what I am trying to say:
Imagine a bingo night. $100$ people come in, and at the end of the night, John Doe, entry number $43$, won the prize.
Now answer this question:
Is mister Doe random?
I assume the answer you will give is "That question doesn't make any sense. How could a person be random or not?" Well, same goes for number sequences. You cannot attribute randomness to them.
What you can do in the bingo-night case is that you can say that "John Doe was randomly selected from the set of all $100$ contestants." Again, this is my exact point:
Neither John Doe nor number sequences are inherently random, but both John and the sequence I wrote can be obtained in a random process.