Numerical property $P(n)$ such that $\forall n P(n)$ is false but a counterexample is difficult to find

Question

I would like to find a nontrivial property $P(n)$ for $n \in \mathbb N$ such that $\forall n P(n)$ is false but the first counterexample can be found only for "very high" $n$ (so high that it wouldn't be found without a calculator).

It would be nice if such counterexample can actually be found by brute force with the help of a calculator so that it could be given as an exercise for high school students that are learning computer programming.

The property $P$ should also be "non-trivial" (for example $P(n)=(n<10^{10^{10}})$ would satisfy the request but it is obvious that it is not true for every $n$).

Answer 1

What about this: it seems that for all $n \ge 1$ $$\gcd(2^n-1, 3^n+2)=1$$ But this fails at $n=176$, and $$\gcd(2^{176}-1, 3^{176}+2)=257$$

Answer 2

This fails for a small $n$, but IMVHO it is instructive, because it addresses a common misconception.

In Euclid's proof that there are infinite primes, one takes the first $n \ge 1$ primes $p_{1}, \dots, p_{n}$, and shows that $$\tag{big} p_{1} p_{2} \cdots p_{n} + 1 $$ (which is obviously greater than $1$) is not divisibile by $p_{1}, \dots, p_{n}$. Hence it is divisible by a prime other than $p_{1}, \dots, p_{n}$.

Sometimes this is incorrectly interpreted as stating that (big) has to be prime - I have even seen a "proof" or two of this in the writings of respectable mathematicians. (We all make errors.)

I think it is interesting to experiment and see that this fails (for a smallish $n$, granted).

Answer 3

Euler's prime-generating polynomial $n^2+n+41$ yields primes for $n\lt40$ but not for $n=40$.

(I had to add something here because otherwise the answer is classified as trivial and automatically converted into a comment.)

Answer 4

This property is very interesting: Any number can be written as the sum of a prime and a power of two, was disproved very early on: $127$ cannot be written as the sum of a prime and a power of two! But then, a question was asked: what about numbers that can be written as the sum or difference of a power of two and a prime?

Would you believe it, that turned out to be false, and the counterexample is: $47,867,742,232,066,880,047,611,079$.

It was conjectured by Brier that there are no numbers which are Riesel ($n$ such that $\forall k,n2^k+1$ is composite) and Sierpinski ($n$ such that $\forall k,n2^k-1$ is composite). Turns out the number $3316923598096294713661$ is both, and he found it himself.

It was conjectured that the prime counting function $\pi(x)$ would never be larger than one of it's approximations widely regarded as it's upper bound until then, the $li$ function. The existence of this number is known, and in fact it's known to be greater than $10^{19}$ and smaller than $e^{728}$.
Here is the paper regarding the first counterexample:
http://www.ams.org/journals/mcom/1975-29-129/S0025-5718-1975-0376583-0/S0025-5718-1975-0376583-0.pdf

Which, in short, is why interestingly computer programs need to run for ages and ages, because counterexamples can be so terribly huge.

Having said that, sometimes you find a property and you wonder if there is no number with that property. For example, for a long time I thought if you take any number and join it back to itself (for example $72$ becomes $7272$), then the resulting number would not be a square. Turns out $1322314049613223140496=363636364^2$.