Collatz conjecture:
The following program always halts:
void function( ArbitraryInteger input){
while( input > 1){
if(input % 2 == 0)
input /= 2;
else
input = (input*3) + 1;
}
// Halt here
}
Slight variation (still a conjecture, because it's based on a result from Collatz's one):
For some input the following program will never enter the same state twice (where the state is determined by the value held by "input"):
void function( ArbitraryInteger input){
while( input >= 1){ // notice the "="
if(input % 2 == 0)
input /= 2;
else
input = (input*3) + 1;
}
}
Note that the second program never halts, regardless of whether the first program halts or not.
It is believed that the first program always terminates for any input, however, we don't have the proof of that, and there may still exist some integer for which the program don't halt (there's also a $100 prize for proving it).
The second program is interesting too: it states that the program will never enter the same state twice for some input, which basically requires the first program to have a sequence known to diverge without repeating. It does not only require the Collatz conjecture to be false, but it requires it to be false and without loops, apart from the obvious 1,4,2,1 loop.
If Collatz has only looping counter-examples the variation on the conjecture is false
If Collatz is false without loops, the variation on the conjecture is true
If Collatz is true, the variation is false
If Collatz is false both because it has loops and because it has a number for which it diverges, the variation on the conjecture is true (it just requires a number for which it diverges without entering a loop)
I think the variation is more interesting (not just because I found it by accident and noticed it thanks to @LieuweVinkhuijzen), but because it actually requires a real proof. By brute forcing, we may be able to find a loop one day or another (and that will be a loop longer than 70 numbers: current state of the art is that there can't infinite loops shorter than 68 or so), and brute forcing is not interesting: it is just number crunching. However we cannot brute-force an infinite divergent sequence, we don't know if it will really end without a real proof.
EDIT: I skipped the part about Collatz Conjecture sorry, I genuinely answered by heart with an algorithm I read about some years ago, I didn't expect that was already mentioned.
EDIT2: A comment made me notice I wrote the algorithm with a mistake, however, that mistake indeed makes my answer different from Collatz conjecture (but a direct variation of it).
