There are two main operations for whole numbers: addition and multiplication. A basic question is what are the "atoms". With respect to addition, the atom is 1, since every number can be written as a sum of 1's, and 1 isn't itself a nontrivial sum. With respect to multiplication, the atoms are the primes, where primes aren't nontrivial products.

A cool thing about breaking a number into multiplicative atoms (the "prime decomposition") is that to multiply two numbers, you can just add up however many copies there are of each atom. Primes turn multiplication into addition in this way. In other words, each prime defines a sort of logarithm that measures the amount of that prime in a number, and knowing the "coordinate" in prime space is enough to determine the original number.

Then one might wonder what is the relationship between primes and addition. When you add two numbers, the prime decomposition of the result seems to be dramatically different from the decompositions of the summands. But there are patterns, like how the sum of even numbers is even. The abc conjecture[1] has to do with one of these patterns.

The relative order of the primes also is saying something about the relationship between addition and multiplication, since addition underlies how you compare two numbers. There are old results about the density of the primes as if they were following a random distribution.

I'm not sure if there's any deep structure that Recamán's sequence has anything to do with. All that seems to be interesting about it is that it evades our capabilities of determining whether every number eventually appears. The Collatz conjecture is similar in this way, though it is further complicated by the fact that it mixes the structures of multiplication and addition.

[1] https://en.wikipedia.org/wiki/Abc_conjecture

Going deeper, in algebraic geometry, what you do is take various number systems (called "rings" -- the integers are an example of a ring) and pretend each element is a function that measures some scalar quantity about an associated space. It's a bold and wild idea. There is a process by which you can figure out what the points of this associated space are, and, at least for the integers, there is one point for each prime. If you think about an integer n as a function defined on this space, then the evaluation of n at the point p ends up being equal to n mod p. All I'm trying to say by bringing this up is that primes are not just aesthetic, they have deep significance, with many analogs in other kinds of mathematics.