tantalizing Computer proofs

Discussions on everything related to the software, electronic, and mechanical components of information systems and instruments.

tantalizing Computer proofs

Postby hyksos on March 11th, 2019, 6:26 pm 

With little introduction, I will assume the reader knows what the Collatz Conjecture is and why there is a strange cult following of it on the internet. Computers have churned through numbers up to 1020 checking that all numbers less than that will bounce around and eventually reach 1.

Image

A certain type of (misleading) common sense would tell you that if a conjecture, or pattern holds up to 1020 that it probably holds for all n to infinity. You might even cross paths with people on the internet who claim , "We know Collatz is true , we just lack a formal proof for all n to infinity."

In this article, I will be showing how wrong those people are in suggesting such. But before we get there, lets delve into the subject of what kinds of size of numbers are capable of being 'crunched' by computers in 2019.

Collatz appears to be plausible for a desktop workstation to find a counter-example (even ripe for it). I watched a professor place a 1000-digit number into a Collatz sequence computed as a program. He let his laptop go, and then continued with a lecture. Ten minutes later, the algorithm finished and spit out a result. So whatever that gigantic 1000-digit number was, it converged to the 4-2-1 cycle at the bottom of the Collatz tree.

A tantalizing idea here is to generate large 100-digit numbers at random, and stick them into the Collatz algorithm to check if maybe one of them diverges. If you stumbled upon one by accident, you would not only have a single counter-example to the Collatz, but every number so generated in the sequence of your algorithm would also be a counter-example (this is true by induction.) So instead of a single counter-example , you would have generated a whole "family" of numbers that break the conjecture. This is extra tantalizing.

Try it here : https://scastie.scala-lang.org/3wkKsLjxQLCum3htLam4iQ

We might ask that in a situation in which a pattern holds for numbers with 100 digits, we can wave our arms and justifiably declare that it likely holds for any n > 0 . We are cerainly not justified in saying this. The hard lesson was Skewes' Number.



Nobody knows the exact value of Skewes Number. We do have upper bounds on it.
In March of 2019, the smallest known upper bound on Skewes is 1.398x10316

Numbers of around the magnitude of 316 digits are slightly out-of-reach of a desktop workstation. The idea that a person in their garage, armed with a GPU , could stumble upon the exact value seems tantalizing.
User avatar
hyksos
Active Member
 
Posts: 1571
Joined: 28 Nov 2014


Re: tantalizing Computer proofs

Postby hyksos on March 11th, 2019, 7:05 pm 

Sum of three cubes.

n = a3 + b3 + c3 {Tc}

(a,b,c) are integers negative or positive, and n > 0

There are some n which cannot be written as the sum of three cubes. These are are any n of the form,
n = 9k + 4
n = 9k - 4

For most n from 1 to 1000, computers have found an (a,b,c) triple which satisfies {Tc}.

Interestingly

33 = 8866128975287528 3 + (-8778405442862239)3 + (-2736111468807040)3

was found literally a few days ago. Other examples :

75 = 43811593 + 4352030833 + -435203233
81 = 396184514443 + -87284087913 + -394767274183
84 = -82411913 + -415317263 + 416396113

We might ask which n < 1000 has not been found yet. There are a handful of them left.

n = {42 , 114, 165, 390, 579, 627, 633, 732, 795, 906, 921, 975 }

For the purposes of this thread, I point your attention to 42 sitting there all innocent and vulnerable to being broken into 3 cubes. If you have an extra computer in your house... or some PC sitting idle at your workplace overnight. Put them to work on 42 = a3 + b3 + c3. You never know what might turn up.
User avatar
hyksos
Active Member
 
Posts: 1571
Joined: 28 Nov 2014



Return to Computers

Who is online

Users browsing this forum: No registered users and 3 guests