0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I'm not sure what you're asking. Are you asking for a set of numbers that have the same difficulty as the primes to find? Or just any set of numbers where the cost to verify grows at a much slower rate than the cost to find(how you find might need to be defined better since if you're using the successor function every exponential function has this characteristic). $\endgroup$ – ruler501 Mar 24 '14 at 6:37
  • $\begingroup$ I was looking for any set of numbers where the cost to verify grows much slower than the cost to find. $\endgroup$ – Dylan Katz Mar 24 '14 at 16:41
  • $\begingroup$ And what operations can you use to find? Just addition? $\endgroup$ – ruler501 Mar 24 '14 at 16:43
  • $\begingroup$ Any method to find it as long as new numbers cannot be found with a function. $\endgroup$ – Dylan Katz Mar 24 '14 at 16:47
  • $\begingroup$ Cannot be found with an elementary function. Every sequence of integers is representable as $f(n) : \mathbb{N} \to \mathbb{Z}$ $\endgroup$ – ruler501 Mar 24 '14 at 16:50
1
$\begingroup$

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.)

$\endgroup$

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.