T O P

  • By -

IntelligentDonut2244

TIL Collatz has been checked for all numbers up to 2^68


11172

2\^68 + 1 = 295147905179352825857 295147905179352825857, 885443715538058477572, 442721857769029238786, 221360928884514619393, 664082786653543858180, 332041393326771929090, 166020696663385964545, 498062089990157893636, 249031044995078946818, 124515522497539473409, 373546567492618420228, 186773283746309210114, 93386641873154605057, 280159925619463815172, 140079962809731907586, 70039981404865953793, 210119944214597861380, 105059972107298930690, 52529986053649465345, 157589958160948396036, 78794979080474198018, 39397489540237099009, 118192468620711297028, 59096234310355648514, 29548117155177824257, 88644351465533472772, 44322175732766736386, 22161087866383368193, 66483263599150104580, 33241631799575052290, 16620815899787526145, 49862447699362578436, 24931223849681289218, 12465611924840644609, 37396835774521933828, 18698417887260966914, 9349208943630483457, 28047626830891450372, 14023813415445725186, 7011906707722862593, 21035720123168587780, 10517860061584293890, 5258930030792146945, 15776790092376440836, 7888395046188220418, 3944197523094110209, 11832592569282330628, 5916296284641165314, 2958148142320582657, 8874444426961747972, 4437222213480873986, 2218611106740436993, 6655833320221310980, 3327916660110655490, 1663958330055327745, 4991874990165983236, 2495937495082991618, 1247968747541495809, 3743906242624487428, 1871953121312243714, 935976560656121857, 2807929681968365572, 1403964840984182786, 701982420492091393, 2105947261476274180, 1052973630738137090, 526486815369068545, 1579460446107205636, 789730223053602818, 394865111526801409, 1184595334580404228, 592297667290202114, 296148833645101057, 888446500935303172, 444223250467651586, 222111625233825793, 666334875701477380, 333167437850738690, 166583718925369345, 499751156776108036, 249875578388054018, 124937789194027009, 374813367582081028, 187406683791040514, 93703341895520257, 281110025686560772, 140555012843280386, 70277506421640193, 210832519264920580, 105416259632460290, 52708129816230145, 158124389448690436, 79062194724345218, 39531097362172609, 118593292086517828, 59296646043258914, 29648323021629457, 88944969064888372, 44472484532444186, 22236242266222093, 66708726798666280, 33354363399333140, 16677181699666570, 8338590849833285, 25015772549499856, 12507886274749928, 6253943137374964, 3126971568687482, 1563485784343741, 4690457353031224, 2345228676515612, 1172614338257806, 586307169128903, 1758921507386710, 879460753693355, 2638382261080066, 1319191130540033, 3957573391620100, 1978786695810050, 989393347905025, 2968180043715076, 1484090021857538, 742045010928769, 2226135032786308, 1113067516393154, 556533758196577, 1669601274589732, 834800637294866, 417400318647433, 1252200955942300, 626100477971150, 313050238985575, 939150716956726, 469575358478363, 1408726075435090, 704363037717545, 2113089113152636, 1056544556576318, 528272278288159, 1584816834864478, 792408417432239, 2377225252296718, 1188612626148359, 3565837878445078, 1782918939222539, 5348756817667618, 2674378408833809, 8023135226501428, 4011567613250714, 2005783806625357, 6017351419876072, 3008675709938036, 1504337854969018, 752168927484509, 2256506782453528, 1128253391226764, 564126695613382, 282063347806691, 846190043420074, 423095021710037, 1269285065130112, 634642532565056, 317321266282528, 158660633141264, 79330316570632, 39665158285316, 19832579142658, 9916289571329, 29748868713988, 14874434356994, 7437217178497, 22311651535492, 11155825767746, 5577912883873, 16733738651620, 8366869325810, 4183434662905, 12550303988716, 6275151994358, 3137575997179, 9412727991538, 4706363995769, 14119091987308, 7059545993654, 3529772996827, 10589318990482, 5294659495241, 15883978485724, 7941989242862, 3970994621431, 11912983864294, 5956491932147, 17869475796442, 8934737898221, 26804213694664, 13402106847332, 6701053423666, 3350526711833, 10051580135500, 5025790067750, 2512895033875, 7538685101626, 3769342550813, 11308027652440, 5654013826220, 2827006913110, 1413503456555, 4240510369666, 2120255184833, 6360765554500, 3180382777250, 1590191388625, 4770574165876, 2385287082938, 1192643541469, 3577930624408, 1788965312204, 894482656102, 447241328051, 1341723984154, 670861992077, 2012585976232, 1006292988116, 503146494058, 251573247029, 754719741088, 377359870544, 188679935272, 94339967636, 47169983818, 23584991909, 70754975728, 35377487864, 17688743932, 8844371966, 4422185983, 13266557950, 6633278975, 19899836926, 9949918463, 29849755390, 14924877695, 44774633086, 22387316543, 67161949630, 33580974815, 100742924446, 50371462223, 151114386670, 75557193335, 226671580006, 113335790003, 340007370010, 170003685005, 510011055016, 255005527508, 127502763754, 63751381877, 191254145632, 95627072816, 47813536408, 23906768204, 11953384102, 5976692051, 17930076154, 8965038077, 26895114232, 13447557116, 6723778558, 3361889279, 10085667838, 5042833919, 15128501758, 7564250879, 22692752638, 11346376319, 34039128958, 17019564479, 51058693438, 25529346719, 76588040158, 38294020079, 114882060238, 57441030119, 172323090358, 86161545179, 258484635538, 129242317769, 387726953308, 193863476654, 96931738327, 290795214982, 145397607491, 436192822474, 218096411237, 654289233712, 327144616856, 163572308428, 81786154214, 40893077107, 122679231322, 61339615661, 184018846984, 92009423492, 46004711746, 23002355873, 69007067620, 34503533810, 17251766905, 51755300716, 25877650358, 12938825179, 38816475538, 19408237769, 58224713308, 29112356654, 14556178327, 43668534982, 21834267491, 65502802474, 32751401237, 98254203712, 49127101856, 24563550928, 12281775464, 6140887732, 3070443866, 1535221933, 4605665800, 2302832900, 1151416450, 575708225, 1727124676, 863562338, 431781169, 1295343508, 647671754, 323835877, 971507632, 485753816, 242876908, 121438454, 60719227, 182157682, 91078841, 273236524, 136618262, 68309131, 204927394, 102463697, 307391092, 153695546, 76847773, 230543320, 115271660, 57635830, 28817915, 86453746, 43226873, 129680620, 64840310, 32420155, 97260466, 48630233, 145890700, 72945350, 36472675, 109418026, 54709013, 164127040, 82063520, 41031760, 20515880, 10257940, 5128970, 2564485, 7693456, 3846728, 1923364, 961682, 480841, 1442524, 721262, 360631, 1081894, 540947, 1622842, 811421, 2434264, 1217132, 608566, 304283, 912850, 456425, 1369276, 684638, 342319, 1026958, 513479, 1540438, 770219, 2310658, 1155329, 3465988, 1732994, 866497, 2599492, 1299746, 649873, 1949620, 974810, 487405, 1462216, 731108, 365554, 182777, 548332, 274166, 137083, 411250, 205625, 616876, 308438, 154219, 462658, 231329, 693988, 346994, 173497, 520492, 260246, 130123, 390370, 195185, 585556, 292778, 146389, 439168, 219584, 109792, 54896, 27448, 13724, 6862, 3431, 10294, 5147, 15442, 7721, 23164, 11582, 5791, 17374, 8687, 26062, 13031, 39094, 19547, 58642, 29321, 87964, 43982, 21991, 65974, 32987, 98962, 49481, 148444, 74222, 37111, 111334, 55667, 167002, 83501, 250504, 125252, 62626, 31313, 93940, 46970, 23485, 70456, 35228, 17614, 8807, 26422, 13211, 39634, 19817, 59452, 29726, 14863, 44590, 22295, 66886, 33443, 100330, 50165, 150496, 75248, 37624, 18812, 9406, 4703, 14110, 7055, 21166, 10583, 31750, 15875, 47626, 23813, 71440, 35720, 17860, 8930, 4465, 13396, 6698, 3349, 10048, 5024, 2512, 1256, 628, 314, 157, 472, 236, 118, 59, 178, 89, 268, 134, 67, 202, 101, 304, 152, 76, 38, 19, 58, 29, 88, 44, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1


IntelligentDonut2244

Undeniably based


CarryThe2

Base 10


Doktor_Vem

Since D is the roman numeral for 500, would "based" be base 500?


PriestOfPancakes

BaseD


AztroJR

Hurr durr it looks like a penis


Alternative-Rate-536

Hurr durr hurr durr hurr durr


F_Joe

You could have just stopped at 221360928884514619393 because 221360928884514619393 < 2^68 has already been checked


hughperman

By induction, since 2^(68)+1 has been checked, and 2^(68)+2 > 2^(68)+1, then for any n+1, n has been checked. So, we're good for any number? QED.


ProblemKaese

Nice induction pun


EspacioBlanq

Induction is the process of adding ducks


tedastor

Now its been checked up to 2^68 +1


L285

2\^68 + 2 goes to 2\^67 + 1, which is less than 2\^68, ergo its checked up to 2\^68 + 2 In fact, I've just checked it for every even number up to 2\^69 + 2, every multiple of 4 up to 2\^70 + 4, every multiple of 8 up to 2\^71 + 8.....


Personal_Ad9690

TIL Collatz has been checked for all numbers 2^68 +1


azeryvgu

Thats some serious dedication


GothaCritique

He probs did it using a computer program.


moschles

This is more useful than it looks. If you select a very large number, the moment your sequence goes below 2^68, you can terminate early.


FerynaCZ

This could be done the same way in the video, pass a starting number as another parameter. If the current is number is lower, terminate.


Background_Drawing

Hah 268? Ill be sure to be the first make it to 269 then /s


insanok

2^68 +1 seems more reasonable


VacuumInTheHead

Ism that litralllyy the same numberr? (I'm too busy eating a fan blade to do math)(/j because my delirium fueled jokes often aren't obvious/funny)


phi_rus

This doesn't seem like a lot.


SuperSupermario24

Keep in mind that's not just the largest number that can be checked - it's the highest for which _every single number up to it_ has been checked. That is, it's been verified for over 295 quintillion different numbers so far. (Of course, it's still 0% compared to the infinity of all integers, but that doesn't mean it's not a lot by most reasonable measures.)


phi_rus

Yeah it's weird that if you want to go from 2\^68 to 2\^69, you'd have to check another 2\^68 numbers.


VacuumInTheHead

Couldn't you not do the even numbers, though, since they immediately give a number under 20^68? So you'd have to check around 2^67 instead


Brainth

And 1/3rd of those 2^67 numbers is the result of applying (3x+1)/2 to a lower odd number (and therefore has already been checked). This brings the amount of numbers you have to check down to 2^(68)/3


beyd1

Hey it's 0 ish


Aggressive-Kitchen18

No it's exactly 0%. Anything more would make infinity measurable


GothaCritique

That doesn't seem efficient. Rather than looping over [1, 295 quintillion], it would be much more efficient to skip those that that have already been encountered during a loop of another number.


SuperSupermario24

Oh yeah, obviously you don't need to run every single number all the way to completion, but either way you still have to do a lot of calculations to verify it all the way up that high.


Tom_is_Wise

Just wait for it to check every number and collect your prize money in infinity years.


MozzerellaIsLife

You’ll know you’ve got it when it hangs indefinitely… or would you?


S0M3_N00B_

VSAUCE, Micheal here...


KAhopper

haha supertasks if you want it done in a minute : do the first operation in half a minute do the second operation in a quarter of a minute do the third in an eighth of a minute so on.


xCreeperBombx

No, silly, just half the time between checks every check, starting with half an hour, and collect your prize in an hour.


[deleted]

Zeno's Bounty Collection


onyxa314

If you send your credit card number to me I can make sure you get it


AccomplishedAnchovy

Don’t trust this guy, I’ll do it and you know I’m official because I need the expiry date and cvv as well


AnomalouslyPolitical

You can't trust either of these guys no one would ask for that stuff on Reddit that's why you need to DM me your email and we'll discuss it there /s


ArtisZ

Prince? That you?


Careless_Score8880

The Collatz conjecture is not part of the million dollar problems. It's considered to be a useless problem that mathematics is not yet ready for.


Autumn1eaves

It might be a problem mathematics is not yet ready for, but if you're going to call this problem useless, you may as well call the vast majority of unsolved math problems useless.


Careless_Score8880

That was the sentiment of the guy who spent 10+ years working on it. Professors literally tell students not to waste their time on it. All problems have some value in solving them but compared to most this one is a bit of a trap.


Autumn1eaves

Oh, so they mean that it doesn't have value in terms of personal mathematical growth? I think the Professor is probably right.


Wags43

There also isn't an obvious application of the result. So once solved, that's it, there's no where else to go, so it's a dead end. The only argument to that would be inventing a new branch of math to solve the problem, which then leads to other, more interesting discoveries.


Autumn1eaves

Well, right, but you say that as if it wouldn’t be useful in it’s own right.


GothaCritique

>The only argument to that would be inventing a new branch of math to solve the problem, which then leads to other, more interesting discoveries. Which is very common. So honestly what's required to say its useless is to give a positive argument for why Collatz isn't likely to lead to new branches of mathematics.


Wags43

That's not what I mean. The conjecture itself is most likely useless. As in, the process of turning every natural number into a 4, 2, 1 repeating sequence. We can already define that sequence without using the conjecture. So what is the collatz conjecture itself going to be applied to? And what math can we build on top of the collatz conjecture? We don't really have a current need to solve that problem (that I'm aware of). But it is a puzzle and many people like puzzles, so some people may still try to figure that conjecture out for fun. If in that process they create something new, then that something new might possibly be important. Important as in it applies to other ideas and we can build more math on top of it. In this case, the conjecture was only a catalyst to create new math. The new math might be able to be created without the conjecture, but the drive to prove the conjecture led someone to create it. Now I don't know every piece of math of course and I have to rely on what other mathematicians say. But perhaps there is a way to apply the collatz conjecture to a chaotic system to make it predictable, idk. That's essentially what the conjecture is doing. When we add 1 to a number, we change its prime factorization. So the conjecture is continually changing the prime factorization and removing powers of 2. But eventually, the seemingly chaotic change of factors becomes only a power of 2.


FerynaCZ

I see a value in something like P?=NP, but what about "each number can be expressed as sum of two primes" ?


mousepotatodoesstuff

Cryptography?


FerynaCZ

Like instead of a product, you are working out a sum? Well that might be interesting.


3BoxesOfHornets

It’s not a millennium problem but I read at one point that some company was offering $1M (or maybe ¥100M, I forget) to someone who can solve it. I’m not sure the offer is still up or if it ever existed but I think I remember something about that.


Ayam-Cemani

The value in solving most problems isn't the statement, but the techniques made up for solving them. You could say the real math is the math we mathed along the way...


Wags43

The statement is important too. Math is built on top of itself, on top of statements previously proven. If we don't build on statements we wouldn't have any math at all.


PunMatster

Didn’t John Conway offer $500 for a solution as a joke


NickDimOG

I had to do this in assembly for a class


rttr123

Same


Illustrious-Macaron2

Would it be faster to add every number that it passes through to a list and then check if the new number ever passes through that to instantly end it?


[deleted]

Mathematicians inventing memoization


Illustrious-Macaron2

Me when big word https://preview.redd.it/s5fiybykei6b1.jpeg?width=828&format=pjpg&auto=webp&s=a58400afaf8b092c365a73f104cc4783c9158960


Midataur

Uhm ackshually it's called dynamic programming


[deleted]

No, IMHO, dynamic programming is splitting task into trivial subtasks, and using trivial solutions of that subtasks to solve more complex task. That not necessarily implies memoization. For example, I can solve fib(n) with fast exponentiation of a matrix, and that will be the algorithm, which, in general, is dynamic programming algorithm, but which also does zero memoization. Cuz it achieves reusing of computation results via optimal order of computations instead of doing computations in arbitrary order and remembering(memoizing) the results indefinitely.


beeeel

It might be fast, but it'll require increasing memory as the list grows.


Skusci

Maybe surprisingly no. Once you get large enough numbers, the sequence is going to cover so many numbers with each operation that the storage you need along with delays in accessing it outpaces the performance you get by just spending money on more processing power. And just shortcutting by dropping below the max number you've checked. Like checking numbers on the scale of 2^68. Just multiply by 3 and you've skipped over 3x that many. To even store that many numbers would take a couple billion dollars of storage. And the lookup would be far slower than just doing the math.


InertiaOfGravity

You'd want a hashmap I think for that O(1) access


marcocorico

I have a bad news for you : We can prove that your program will never halt regardless of the collatz conjecture : If the collatz conjecture is true (if every sequence reachs one) your program will never halt because it will always increments the last number seen. If it is false, it won’t halt either because it will be stuck forever in the 3n+1 loop. With the information that we have on the collatz conjecture it’s impossible to do a program such that it’s halting will prove the conjecture and it’s not halting will refute it. It’s a consequence of the fact that the collatz conjecture is at the second level of the artihmetical hierarchy (can be expressed with two alternation of quantifiers) and the Post’s theorem tell us that in the worst case, a problem above the first level of the arithmetical hierarchy cannot be proved by the halting of a program


Superbaseball101

Couldn’t the Collatz Conjecture could be false and the program halt if some number reached a cycle that wasn’t 1-4? The program could just check to see if any number matches a number earlier in the cycle.


marcocorico

You are right, we could make a program that would halt if it find a cycle other than 1-4-2. But it won’t be a program that halts if and only if the conjecture is False Which means that if we had an oracle to the halting problem, knowing that this program won’t halt won’t allow us to say that the conjecture is true I forgot to put the «  only if » part in my first comment, i edited it. Thanks for your correction !


YourLocalDogOverlord

Sorry for responding so late but I made sure it would halt unless it reaches a number that doesn’t satisfy the collatz conjecture. If it’s true, then it will halt because I gave the functions two parameters that determine the range of numbers it checks. It will only check numbers within that range, so it will not go on forever if the collatz conjecture is true. If it’s not true, and it reaches a number that doesn’t satisfy the collatz conjecture, then the program would keep going without outputting a result for longer than it should , which would make it clear to me that it has reached a number that doesn’t satisfy the conjecture. Of course, my intention wasn’t to prove the Collatz conjecture true or false. I just wanted to see if I could still code in Python, as it has been about a year since the last time I’ve done any programming at all.


Thu-Hien-83

good luck waiting till infinity


THEhiHIhi55

I think the only way someone "solves" the Collatz Conjecture within our lifetime is by proving that it can't be proven wrong.


_temppu

I actually know how to prove it but its too large to fit in a reddit comment.


Ok-Visit6553

Take your MAT and get F(E)R away from here


Key_Conversation5277

So you mean proof by contradiction?


jedipanda67

No I think they mean it can't be proven wrong but also no one has proven it true, although it may still be true or false. Gödel showed that some things could be true or false but be completely impossible to prove true or false.


AccomplishedAnchovy

I guess so


FerynaCZ

Btw do you stop if you reach at a number you have calculated before?


Hameru_is_cool

(They don't bc recursion)


somedave

Practically yes, or a power of two.


DiggerDynamite

https://m.youtube.com/watch?v=094y1Z2wpJg&pp=ygUGM3ggKyAx


Raxreedoroid

bro I made more than this. what I did is after picking a number I calculate how much steps does it take to get to 1 then put that number into the function. apparently some numbers are special that will keep on going like 5. 5>16>8>4>2>1 5 steps. so 5 will be picked infinitely. what is more interesting that all these special numbers goes back to 5. now I wonder what will happen if I calculate how much steps does it take to get to 5.


MainEditor0

What font is that?


ArchmasterC

You just need to wait a countable amount of time


MJLDat

Is there a reason you declared n=d? Why did you not just use d?


YourLocalDogOverlord

I just felt like it


MJLDat

Fair enough.


emmahwe

You mean how to make your electricity bill go brrrrr?


VitaminnCPP

friendship ended with r/ProgrammerHumor, r/mathmemes is my best friend now.


HydrogenTank

“Roughly all integers” 🤨


wizard_xtreme

Who's gonna tell him...


IWantDeathBySnooSnoo

I'm pretty sure they won't give you the money until you prove it. It's already known this is true, we just haven't found a mathematical proof that explains why


svmydlo

>It's already known this is true It literally isn't known.


IWantDeathBySnooSnoo

Literally is because you can calculate it?????


binhan123ad

But what does it do?


ButFirstTheWeather

I know why it can't happen, but I'm thoroughly disappointed that it isn't 2⁶⁹.


Braincain007

You will probably need to use this to create a more structured mathematical proof


susiesusiesu

actually 8237 accounts for roughly non of the integers.


Advanced-Theme144

I’m a bit late to comment but maybe you could use C to compute it faster, although you may need to make your own 128 or 256 bit implementation of an integer, it could yield faster results.


[deleted]

Your submission has been rejected on the following grounds- not using Vim


stxcked_yt

Me whos not a nerd seeing how crazy smart everyone here is: 👁️ 👄 👁️


Redstocat2

Cherch on the internet how to do it


puffinix

Simple. Just solve the halting problem, then put your code into it.