Prime numbers? numbers X where there's no X'<X,N>1,i>0 with X' * N^i = X

Question

I'm writing an algorithm to find some natural number X > 1 which satisfies some "test" Predicate(X) = true. I just noticed that due to the inner workings of Predicate I know the following:

If Predicate(X) = false, then Predicate is also false for all numbers

• X * 2^i with 0 < i
• X * 3^i with 0 < i
• X * 4^i with 0 < i (this is also due to X * 2^2 of course)
• ... and so on for every natural number

Now testing just all natural numbers one after the other doesn't make too much sense, as many are already ruled out by above rules. Which natural numbers remain to be tested, though?

I feel like this could be just the prime numbers, but I'm not sure how to approach verifying this.

Specifically, I'm looking for this set:

{ X | forall X'<X, N>1, i>0: X' * N^i != X }

edit: Not sure if that's an accurate description. Example: 30 is ruled out after testing Predicate(2) = false because this rules out 2 * 3^1 = 6. Therefore Predicate(6) = false, this rules out 6 * 5^1 = 30.

Answer 1

Let $A\subseteq \Bbb N$ be the set of natural numbers $n$ for which your predicate $P(n)$ is true. What we know is that $a\notin A$ implies $ka\notin A$ for all naturals $k>1$. In other words, $a\in A$ implies that all divisors of $a$ are also $\in A$. This still leaves many possibilities for $A$ (and accordingly for the predicate $P$). The simplest examples are:

• $A=\emptyset$. To verify this, it would suffice to verify that $P(1)$ is false.
• $A=\{1\}$. To verify this, one needs to test that $P(1)$ is true and that $P(p)$ is false for all primes $p$.
• $A=\Bbb N$. To verify this, one needs to test that $P(n)$ is true for infinitely many suitable $n$ with the property that each natural number divides some such $n$. There is no strictly minimal set of numbers to test though. For example, testing all $n$ of the form $n=k!^{1000}$ with $k>42$ would suffice ...

The most general $A$ has the following form: $$ A=\{\,d\in\Bbb N\mid\exists b\in B,\,\exists k\in\Bbb N\colon b=kd\,\}$$ where $B$ is an arbitrary subset of $\Bbb N$. For example with $B=\{30,343\}$, we arrive at $A=\{1,2,3,5,6,7,10,15,30,49,343\}$. In order to determine $A$, it suffices to test that $P(b)$ is true for all elements of $B$, and $P(bp)$ is false for all elements of $b$ and primes $p$. (So in the example, $P(30$ and $P(343)$ should be true and $P(60)$, $P(90)$, $P(150)$, $P(210)$, $P(330)$, etc. as well as $P(686)$, $P(1029)$, etc should be false.

Answer 2

Let $P$ denote Predicate.

Assume that $P$ is false for all prime numbers. Then using your main assumption you can prove by an immediate induction on $n$ that $P$ is false for all composite numbers that are a product of $n$ primes. Therefore $P$ is false for all numbers.

Conclusion: you are right, all you need to test is the set of primes.