/sci/ - Science & Math » Thread #14203403

84KiB, 1280x605, neogastonism.jpg

View Same Google iqdb SauceNAO

Anonymous Tue 08 Feb 23:20:05 2022 No.14203403 View Reply Original Report

Quoted By: >>14203557 >>14203642 >>14203670 >>14203729 >>14203733

I figured out a way to factorize an arbitrarily large integer in O(1). On my machine shit takes about 30 seconds.

Anonymous

Anonymous Tue 08 Feb 2022 23:54:51 No.14203557 Report

Quoted By: >>14203733 >>14203737 >>14203753 >>14203887 >>14203936

>>14203403
Factorize 10^10^10^10^10^10^10 - 23

Anonymous

Anonymous Wed 09 Feb 2022 00:18:00 No.14203642 Report

Quoted By: >>14203664 >>14203674

>>14203403
It's not possible for it to be O(1). That would mean the number of bits (amount of information) needed to represent the prime factors is always constant, e.g. m bits where m is a constant. However, you could find the largest number n whose prime factors can be represented with m bits and add 1 to it, thereby finding a number (n + 1) whose prime factors cannot be represented in only m bits.

Anonymous

View Same Google iqdb SauceNAO 64b60574a89d445912ef725087e36069.jpg, 3MiB, 2404x2076

Anonymous Wed 09 Feb 2022 00:25:33 No.14203664 Report

Quoted By:

>>14203642
Another reason it can't be true is that integer square root grows at about log(N), which is a basic computation for integer decomposition algorithms.

Anonymous

Anonymous Wed 09 Feb 2022 00:27:25 No.14203670 Report

Quoted By:

>>14203403
OP perhaps you meant O(n), however if you get O(1) and O(n) confused then you definitely didn't find a O(n) algorithm.

Anonymous

Anonymous Wed 09 Feb 2022 00:28:52 No.14203674 Report

Quoted By: >>14203685 >>14203688

>>14203642
Not if your program uses multiple ways of encoding factors as bits

Anonymous

Anonymous Wed 09 Feb 2022 00:34:08 No.14203685 Report

Quoted By:

>>14203674
Sorry but you're not roping in any idiots here. Maybe Q-Anon will take you.

Anonymous

Anonymous Wed 09 Feb 2022 00:35:56 No.14203688 Report

Quoted By: >>14203696

>>14203674
There are infinitely many primes, but the maximum number of unique encodings for some amount of finite bits m is 2^m.

Anonymous

Anonymous Wed 09 Feb 2022 00:38:50 No.14203696 Report

Quoted By: >>14203704

>>14203688
What? There are infinitely many encodings for even a single bit

Anonymous

Anonymous Wed 09 Feb 2022 00:40:54 No.14203704 Report

Quoted By: >>14203713

>>14203696
The encodings themselves must be represented as information (e.g. bits).

Anonymous

Anonymous Wed 09 Feb 2022 00:42:52 No.14203713 Report

Quoted By: >>14203727

>>14203704
There are infinitely many ways to encode those encodings as well

Anonymous

Anonymous Wed 09 Feb 2022 00:47:40 No.14203727 Report

Quoted By: >>14203748

>>14203713
If you're not constricting yourself to a finite set of encodings then your encodings are neither part of your algorithm or an output of your algorithm. If that is the case then they provide no additional information beyond what your algorithm provides, i.e. finite information.

Anonymous

Anonymous Wed 09 Feb 2022 00:48:03 No.14203728 Report

Quoted By:

>O(1)
ask me how I know you're lying

Anonymous

Anonymous Wed 09 Feb 2022 00:48:24 No.14203729 Report

Quoted By:

>>14203403
Easy!
>check if it's below a constant X
>if it isn't, return "BAKA! It's too big!!!"
>if it is, do a regular factorization algorithm
Time complexity O(X), but since X is constant, it's O(1).

Anonymous

Anonymous Wed 09 Feb 2022 00:49:24 No.14203733 Report

Quoted By:

>>14203403
>>14203557
OP it's been 54 minutes, your program should be finished with this factorization by now.

Anonymous

Anonymous Wed 09 Feb 2022 00:50:36 No.14203737 Report

Quoted By: >>14203742 >>14203771

>>14203557
>Factorize 10^10^10^10^10^10^10 - 23
It's O(1) time but the size of this number won't fit on my machine. Or all machines put together for that matter even if we dedicated the entire universe to storing it.

Anonymous

Anonymous Wed 09 Feb 2022 00:51:59 No.14203742 Report

Quoted By:

>>14203737
i can fit it on $m^{y}$ machine.

Anonymous

Anonymous Wed 09 Feb 2022 00:53:52 No.14203748 Report

Quoted By:

>>14203727
The encodings are a part of the algorithm, algorithm is an $\omega$ -meta algorithm which operates on encodings, encodings of encodings, etc., in operations sequenced a. la. the typical enumeration of a countable union of countable lists

Anonymous

Anonymous Wed 09 Feb 2022 00:55:48 No.14203753 Report

Quoted By:

>>14203557
The sum of its digits is likely 5.

Anonymous

Anonymous Wed 09 Feb 2022 01:04:14 No.14203771 Report

Quoted By: >>14203908 >>14203986

>>14203737
Factor this:
6635673557951336506410682813697466329709038157097469768284379445279453129741669480614879165312958855421325212749475386780189508784567522515874714849693298542548576124270292084455433886545434907578051744149003427906652551670698734283056101995280081456556690737565696628386395172912796485774333362090955300171991263927306845563640515102995318757363222511382852839262313412493468433426263460827645644025325428546959784155462714424719234461146497310245991280370884349613260445436442236863320957581165664770475065910238983798191421416433730144053505930075470826483167799355184943606608106594594136863656229865673491821886296739436523682261104743032136085051749023339379995982676014282064128575109254270271403009581004844647898759509880416662190060819358874394823710267898466369104881060418223957463510192540047077915103675953967822618268621875808590179630090148782174826168763648127342482647775591710955540054045666761152040235352369338167933782137377970290318095520194362198699201911973221853080158390323636594994581063554079611235041303624787464557120875814184417956459649945205460414537798769542013133417965572154585562816910498929400231402614915802315996823005777292331607368755070181536929656330908450319424765512346336650073532758961118957011248388400833843482918441129836588447671697241050157122493048461527880041300171309757615191665382188178366155596689019563555341547683871698562252298690610339392028049008791647903767880355678784189468624453260994410936478776953854742339710836342330812344900932381783924323848845454906884643742222951616710236390934831694185783038080610834959332050284427065385455816888922650719890304986059756606506856304414671419766966403690878606910415127042545966258304919120584456237519027041508260566770436377467317372216153603232042570342807933354594167783718612127194957519724622347689954259553940009346393573617723894100166204959053039147390693829199197304580820179162

Anonymous

Anonymous Wed 09 Feb 2022 01:36:12 No.14203887 Report

Quoted By: >>14203932

>>14203557
it's prime

Anonymous

Anonymous Wed 09 Feb 2022 01:42:21 No.14203908 Report

Quoted By: >>14203914 >>14203944

>>14203771
It's been 40 minutes. Where's the factorization, OP?

Anonymous

Anonymous Wed 09 Feb 2022 01:44:32 No.14203914 Report

Quoted By:

>>14203908
sneed

Anonymous

View Same Google iqdb SauceNAO unknown.png, 12KiB, 429x40

Anonymous Wed 09 Feb 2022 01:49:21 No.14203932 Report

Quoted By:

>>14203887
Kek, it won't terminate

Anonymous

Anonymous Wed 09 Feb 2022 01:50:26 No.14203936 Report

Quoted By:

>>14203557
Alot of 9's ending in 77.

Anonymous

Anonymous Wed 09 Feb 2022 01:52:53 No.14203944 Report

Quoted By: >>14203990

>>14203908
He said it's O(1) but the constant is larger than the age of the universe even when compiled in the most efficient manner on the fastest supercomputing clusters in any world (i.e. over all technologically advanced civilizations in the universe), 100 millennia into the future.
Unfortunate but true! Vixra upload coming soon.

Anonymous

Anonymous Wed 09 Feb 2022 02:04:05 No.14203986 Report

Quoted By:

>>14203771
I want to say its 2 taken to a hyper-operation of maybe 20?

Anonymous

Anonymous Wed 09 Feb 2022 02:05:21 No.14203990 Report

Quoted By: >>14204016

>>14203944
>it's O(1) but the """constant"""" factor grows with size of input

Anonymous

Anonymous Wed 09 Feb 2022 02:11:09 No.14204016 Report

Quoted By:

>>14203990
it constantly grows

Capcode	All Only User Posts Only Moderator Posts Only Admin Posts Only Developer Posts
Show Posts	All Only With Images Only Without Images
Deleted Posts	All Only Deleted Posts Only Non-Deleted Posts
Ghost Posts	All Only Ghost Posts Only Non-Ghost Posts
Post Type	All Only Sticky Threads Only Opening Posts Only Reply Posts
Results	All Grouped By Threads
Order	Latest Posts First Oldest Posts First

Your latest searches