Conjectures that have been disproved with extremely large counterexamples? I just came back from my Number Theory course, and during the lecture there was mention of the Collatz Conjecture.
I'm sure that everyone here is familiar with it; it describes an operation on a natural number – $n/2$ if it is even, $3n+1$ if it is odd.
The conjecture states that if this operation is repeated, all numbers will eventually wind up at $1$ (or rather, in an infinite loop of $1-4-2-1-4-2-1$).
I fired up Python and ran a quick test on this for all numbers up to $5.76 \times 10^{18}$ (using the powers of cloud computing and dynamic programming magic).  Which is millions of millions of millions. And all of them eventually ended up at $1$.
Surely I am close to testing every natural number? How many natural numbers could there be?  Surely not much more than millions of millions of millions. (I kid.)
I explained this to my friend, who told me, "Why would numbers suddenly get different at a certain point?  Wouldn't they all be expected to behave the same?"
To which I said, "No, you are wrong!  In fact, I am sure there are many conjectures which have been disproved by counterexamples that are extremely large!"
And he said, "It is my conjecture that there are none! (and if any, they are rare)".
Please help me, smart math people.  Can you provide a counterexample to his conjecture?  Perhaps, more convincingly, several?  I've only managed to find one! (Polya's conjecture). One, out of the many thousands (I presume) of conjectures. It's also one that is hard to explain the finer points to the layman. Are there any more famous or accessible examples?
 A: A famous example that is not quite as large as these others is the prime race.  
The conjecture states, roughly: Consider the first n primes, not counting 2 or 3. Divide them into two groups: A contains all of those primes congruent to 1 modulo 3 and B contains those primes congruent to 2 modulo 3. A will never contain more numbers than B. The smallest value of n for which this is false is 23338590792.
A: I heard this story from Professor Estie Arkin at Stony Brook (sorry, I don't know what conjecture she was talking about):

For weeks we tried to prove the conjecture (without success) while we left a computer running looking for counter-examples.  One morning we came in to find the computer screen flashing: "Counter-example found".  We all thought that there must have been a bug in the algorithm, but sure enough, it was a valid counter-example.
I tell this story to my students to emphasize that "proof by lack of counter-example" is not a proof at all!


[Edit] Here was the response from Estie:

It is mentioned in our paper:
Hamiltonian Triangulations for Fast Rendering
E.M. Arkin, M. Held, J.S.B. Mitchell, S.S. Skiena (1994). Algorithms -- ESA'94, Springer-Verlag, LNCS 855, J. van Leeuwen (ed.), pp. 36-47; Utrecht, The Netherlands, Sep 26-28, 1994. 
Specifically section 4 of the paper, that gives an example of a set of points that does not have a so-called "sequential triangulation".
The person who wrote the code I talked about is Martin Held.

A: In this paper http://arxiv.org/abs/math/0602498 a sequence of integers is proposed, which, when started with $1$ begins like this:
$$1, 1, 2, 1, 1, 2, 2, 2, 3, 1, 1, 2, 1, 1, 2, 2, 2, 3, 2, \dots$$
This is also the sequence A090822 at OEIS. The description there is somewhat better:

Gijswijt's sequence: $a(1) = 1$; for $n>1$, $a(n) =$ largest integer $k$ such that the word $a(1)a(2)...a(n-1)$ is of the form $xy^k$ for words $x$ and $y$ (where $y$ has positive length), i.e. the maximal number of repeating blocks at the end of the sequence so far.

The rules are better explained by demonstration:
$$\color{blue}{1} \to 1$$
$$\color{blue}{1} \color{red}{1} \to 2$$
$$11 \color{blue}{2} \to 1$$
$$112 \color{blue}{1} \to 1$$
$$112 \color{blue}{1}\color{red}{1} \to 2$$
$$ \color{blue}{112}\color{red}{112} \to 2$$
$$11211 \color{blue}{2}\color{red}{2} \to 2$$
$$11211 \color{blue}{2}\color{red}{2}\color{green}{2} \to 3$$
$$11211222 \color{blue}{3} \to 1$$
etc.
What's really surprising:

*

*$4$ appears for the first time in position $220$

*$5$ appears for the first time in approximately position $10^{10^{23}}$ (sic !)

*The sequence is unbounded
To clarify, this fits the question like this: If someone tried to check this sequence for large numbers experimentally they would most likely conclude that it's bounded, and has no numbers larger than $4$

Edit
Curiously, this paper explicitly states that the authors initially thought that no number greater than $4$ appears in the sequence.
A: The wikipedia article on the Collatz conjecture gives these three examples of conjectures that were disproved with large numbers:
Polya conjecture.
Mertens conjecture.
Skewes number.
A: For an old example, Mersenne made the following conjecture in 1644:
The Mersenne numbers, $M_n=2^n  − 1$, are prime for n = 2, 3, 5, 7, 13, 17, 19, 31, 67, 127 and 257, and no others.
Pervushin observed that the Mersenne number at $M_{61}$ is prime, so refuting the conjecture.
$M_{61}$ is quite large by the standards of the day: 2 305 843 009 213 693 951.
According to Wikipedia, there are 51 known Mersenne primes as of 2018
A: The first example which came to my mind is the Skewes' number, that is the smallest natural number n for which π(n) > li(n). Wikipedia states that now the limit is near e727.952, but the first estimation was much higher.
A: Another class of examples arise from diophantine equations with huge minimal solutions. Thus the conjecture that such an equation is unsolvable in integers has only huge counterexamples. Well-known examples arise from Pell equations, e.g. the smallest solution to the classic Archimedes Cattle problem has 206545 decimal digits, namely 77602714 ... 55081800.
A: A case where you can "dial in" a large counterexample involves this theorem:
"A natural number is square if and only if it is a $p$-adic square for all primes $p$."
A $p$-adic square is a number $n$ for which $x^2\equiv n\bmod p^k$ has a solution for any positive $k$.
If we include all primes $p$ we have no counterexamples, but suppose we are computationally testing for squares and we have only space and time to include finitely many primes.  How high we can go before we get a non-square number that slips through the sieve depends on how many primes we include in our test.
With $p=2$ as the only prime base, the first non-square we miss is $17$.  Putting $p=3$ in addition to $p=2$ raises that threshold to $73$.  Using $2,3,5,7$ gives $1009$ as the first "false positive".  The numbers appear to be growing fast enough to make the first counterexample large with a fairly modest number of primes.  See http://oeis.org/A002189 for more details.
A: It is well known that Goldbach's conjecture is one of the oldest unsolved problems in mathematics. A counterexample if it exists it will be a number greater than $4\cdot10^{18}$. 
What is not well-known is that Goldbach made another conjecture which turned out to be false. The conjecture was 

All odd numbers are either prime, or can be expressed as the sum of a prime and twice a square.

The first of only two known counterexamples is $5777$ (The second being $5993$).
This number is not "extremely large" for today's data but surely it was on 1752 when Goldbach proposed this conjecture in a letter to Euler who failed to find the counterexample. It was found a century later in 1856 by Moritz Abraham Stern (see this). The prime numbers that cannot be written as a sum of a (smaller) prime and twice a square are called Stern primes. It is believed that there are only finitely many Stern primes.
A: I was so pissed after testing one of my own conjectures that I remembered this question and wanted to post it here. 
I conjectured after numerical observations that for every prime p, and integers $k \ge 1, n \ge 1$, that 
$$
p^k \, || 2^n-1 \quad \Longleftrightarrow \quad p^{k-1} \, || \, n \quad and \quad O(2,p) \, |\, n,
$$
where $O(2,p)$ is the least integer $m$ such that $2^m \equiv 1 \pmod p$, and $||$ stands for exact division (i.e. $a^k \, | \, m$ but $a^{k+1} \, \nmid \, m$ is written $p^k \, || \, m$). This conjecture happens to be true for the first $180$ primes and the first $3000$ multiples of $O(2,p)$ (when $n$ is not a multiple of $O(2,p)$ we already know what happens). But it so happens that $1093$ is prime, that $O(2,1093) = 364$ and $2^{364} \equiv 1 \pmod {1093^2}$, so that the statement above is not true when $k=1$, $n = 364$ and $p=1093$ because the division on the LHS is not exact.
A: Fermat conjectured that $F_n=2^{2^n}+1$ is prime for all $n$, 
but Euler showed that $ F_{5}=2^{2^{5}}+1=2^{32}+1=4294967297=641\times 6700417.$
A: I don't know if I would consider this accessible or 'large', but the counterexample of Adyan to the famous General Burnside Problem in group theory requires an odd exponent greater than or equal to 665. The "shorter" counterexample (proof) due to Olshanskii requires an exponent greater than $10^{10}$. The reason for the large number in the latter proof is essentially due to 'large scale' consequences of Gauss-Bonnet theorem for certain planar graphs expressing relations in groups. It may be that a finer analysis can show that a counterexample can occur at exponent as low as 5, but this is still not known. 
This is probably essentially different than what you are asking, since we aren't forced to consider 665 because the cases 1-664 are known to be true. I thought it may be fun to point out, here, though! 
A: Further counterexamples can be found here: https://mathoverflow.net/questions/15444/the-phenomena-of-eventual-counterexamples
A: Here's a recent one I didn't see on either page.  The following are true statements:
$\displaystyle{ \int_0^\infty \frac{\sin t}{t} \, dt = \frac{\pi}{2} }$
$\displaystyle{ \int_0^\infty \frac{\sin t}{t} \, \frac{\sin \left(\frac{t}{101}\right)}{\frac{t}{101}} \, dt = \frac{\pi}{2} }$
$\displaystyle{ \int_0^\infty \frac{\sin t}{t} \, \frac{\sin \left(\frac{t}{101}\right)}{\frac{t}{101}} \, \frac{\sin \left(\frac{t}{201}\right)}{\frac{t}{201}} \, dt = \frac{\pi}{2} }$
$\displaystyle{ \int_0^\infty \frac{\sin t}{t} \, \frac{\sin \left(\frac{t}{101}\right)}{\frac{t}{101}} \, \frac{\sin \left(\frac{t}{201}\right)}{\frac{t}{201}} \, \frac{\sin \left(\frac{t}{301}\right)}{\frac{t}{301}} \, dt = \frac{\pi}{2} }$
Is it true that
$\forall n,\displaystyle{ \int_0^\infty \prod_0^n\frac{\sin \left(\frac{t}{100n+1}\right)}{\frac{t}{100n+1}} \, dt = \frac{\pi}{2} }$
?

No, it's not.  However, you could have a computer calculating this for the rest of your life and never find a counter-example. The first counter-example for n has 43 digits.
I found this example here. It was specially constructed to have a large counter-example - the page gives a way to construct similar statements with arbitrarily large counter-examples.
A: Another example: Euler's sum of powers conjecture, a generalization of Fermat's Last Theorem. It states:
If the equation $\sum_{i=1}^kx_i^n=z^n$ has a solution in positive integers, then $n \leq k$ (unless $k=1$). Fermat's Last Theorem is the $k=2$ case of this conjecture.
A counterexample for $n=5$ was found in 1966: it's
$$
61917364224=27^5+84^5+110^5+133^5=144^5
$$
The smallest counterexample for $n=4$ was found in 1988:
$$
31858749840007945920321 = 95800^4+217519^4+414560^4=422481^4
$$
This example used to be even more useful in the days before FLT was proved, as an answer to the question "Why do we need to prove FLT if it has been verified for thousands of numbers?" :-)
A: My favorite example, which I'm surprised hasn't been posted yet, is the conjecture:

$n^{17}+9 \text{ and } (n+1)^{17}+9 \text{ are relatively prime}$

The first counterexample is $n=8424432925592889329288197322308900672459420460792433$
A: I had a conjecture that for any two natural numbers with the same least prime factor, there must be at least one number in between them with a higher least prime factor. It seemed extremely robust for small numbers and gave every indication via empirical trends that it would hold for arbitrarily large numbers as well.
Just this morning, I discovered a counterexample at 724968762211953720363081773921156853174119094876349. While this may not be the smallest one possible, it's easy to show that any counterexample that does exist can't be too much smaller. I was amazed to see such a big number pop out of a relatively simple problem statement.
A: I have a conjecture that can be maybe disproved by an extremely huge counterexample:
Consider sequence https://oeis.org/A301806
I conjecture that if n divides a(n), then a(n) +1 is prime.
