Mathematical function alike to primes

107 Views Asked by At

Note: I'm currently in a low level algebra class and have very little knowledge of some of the more complex mathematical concepts. That being said, I can probably figure out anything I don't know through research.

If I understand correctly, prime numbers become (roughly)exponentially less common and cannot be calculated readily with an explicit formula. Mainly what I'm interested is the fact that they become increasingly difficult to calculate and are more difficult to calculate than to verify(verifying 7 is prime is quicker than finding all prime numbers between 1 and 10). Is there another set of numbers like this, or are primes absolutely unique in this sense? I don't really care what the ratio is, as long as finding these numbers takes longer than it takes to verify them and cannot be found with an elementary function.

1

There are 1 best solutions below

0
On BEST ANSWER

Is there another set of numbers like this, or are primes absolutely unique in this sense?

Primes are definitely not unique in this sense. For example, the sequence of prime powers (OEIS A000961) has all the same properties that you mentioned.

Another example is the sequence of even perfect numbers. Here the cost to verify is low because we know that each even perfect number $n$ must fit the formula $n=2^{p-1}(2^p-1)$ where both $p$ and $2^p-1$ are primes; see Euclid-Euler theorem. On the other hand, the cost to find perfect numbers is very high. (We do not even know if there are infinitely many of them.)