mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > FactorDB

Reply
 
Thread Tools
Old 2022-10-20, 15:30   #45
xilman
Bamboozled!
 
xilman's Avatar
 
"๐’‰บ๐’ŒŒ๐’‡ท๐’†ท๐’€ญ"
May 2003
Down not across

22·3·5·193 Posts
Default

Quote:
Originally Posted by kruoli View Post
Yes, it would take some time, but I would assert it is a reasonable amount of time. You could "trial factor" each number by trying each prime known to FactorDB up to sqrt(number). I am thinking you could even improve that a lot by using some GCD trickery.
Undoubtedly the case. It can run in O(log(N)) number of GCDs, where N is the number of primes, whereas it takes O(N) by successive trial division. A GCD is also sub-linear in the number of basic arithmetic operations.
xilman is offline   Reply With Quote
Old 2022-10-20, 16:06   #46
kruoli
 
kruoli's Avatar
 
"Oliver"
Sep 2017
Porta Westfalica, DE

23068 Posts
Default

So it sounds like it would be a workable idea to back FactorDB up by simply downloading all the primes. Maybe we can ask Markus whether he is up to giving some of us a download link for these?
kruoli is offline   Reply With Quote
Old 2022-10-20, 19:29   #47
chalsall
If I May
 
chalsall's Avatar
 
"Chris Halsall"
Sep 2002
Barbados

2×5,431 Posts
Default

Quote:
Originally Posted by kruoli View Post
So it sounds like it would be a workable idea to back FactorDB up by simply downloading all the primes. Maybe we can ask Markus whether he is up to giving some of us a download link for these?
Indeed. Sometimes a simple conversation can result in wonderful convergence.

Just to put this out there... I often use rsync for IPC data exchange. Whenever possible, stand on the shoulders of giants.
chalsall is offline   Reply With Quote
Old 2022-10-21, 00:05   #48
Happy5214
 
Happy5214's Avatar
 
"Alexander"
Nov 2008
The Alamo City

863 Posts
Default

Quote:
Originally Posted by LaurV View Post
1. How do you do this with the current (redundant) information in FDB? (think about, no need to reply).

2. In which situation do you actually need to "go back"? (i.e. given 19, get 65 and 75 out of it) (idem)

The "procedure", as I know it, is always in the opposite direction - you are giving 65, or 77, and need to get 19. Of course, to reconstruct the complete tree you need to be given BOTH 65 and 77, AND their factors [...]
I think you missed the point. There would be two lines in your proposed database for 19, wouldn't there? The lowest sequence and the longest sequence in the two branches could not be reconciled.

Last fiddled with by Happy5214 on 2022-10-21 at 00:06 Reason: Clip
Happy5214 is offline   Reply With Quote
Old 2022-10-23, 01:01   #49
Happy5214
 
Happy5214's Avatar
 
"Alexander"
Nov 2008
The Alamo City

863 Posts
Default

I'd like to add that, for a database website, its understanding of HTTP methods is terrible. GET requests should not change meaningful data, including creating new entries, especially without explicitly declaring that intent. That's just a basic rule of web design. Ideally, all new IDs would be created through POST or PUT requests, and queries that result in a non-existent entry would return the queried formula or say "entry not found" (or something similar).

Last fiddled with by Happy5214 on 2022-10-23 at 01:02 Reason: Clarify
Happy5214 is offline   Reply With Quote
Old 2022-10-29, 08:21   #50
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
"name field"
Jun 2011
Thailand

3×5×683 Posts
Default

Quote:
Originally Posted by Happy5214 View Post
I think you missed the point. There would be two lines in your proposed database for 19, wouldn't there?
No. The line for 19 will look like "19, 1, 65, 65" as long as you only factored all numbers under 100 and not higher. Your database in this case has the first 98 lines starting with numbers from 2 to 99. There is only one line for 19, and one line for any other number. There are more lines reaching higher, as some of the sequences starting under 99 reach higher. For example, numbers like 156, 176, 184, 196, 203, 236 may also be in the DB, because they come (at least) from sequence 96 (not in this order, but they will be in order in the DB), and their presence will depend of how high sequence 96 was worked. Last in the chain may not be fully factored. But the first 98 lines will have the numbers from 2 to 99, in order, as a start of the line. Fully factored, or not (some of them also reach higher than 99). The line for 19 will look like "19, 1, 65, 65", as I said. Why should I change the last one to 77? 77 is totally uninteresting, it is higher than 65 (so, not the smallest) and it is not the longest either (its length is not bigger than 65's length).

Once you start "solving" the aliquot 100, this will add to the database the line for 100, and the line for 117, etc. When the sequence 100 is finished (it may or may not be in this step - think about numbers with many digits, not about 117 itself which is very easy to factor - finishing the sequence starting with 100 may take years ) - and we will find out that 100 ends in 19 too, then the line for 19 will look like "19, 1, 65 100" (as 100 is longer than 65). You don't need to "finish" the sequence 100, as immediately when you will get to 65, you will find that in the DB already, looking like "65, 5, 13, 65, 65" (see note below about flags and cofactor) and this will be modified to "65, 5, 13, 65, 100" (or "65, 5, 100 F", see below). Job done.

Also, 77 is never "lost", it has its own line in the DB, that looks like "77, 7, 11, 77, 77" (note that 11 can be missing, and I ignored flags, to avoid complicating the explanation - in fact, the line for 77 is, assuming you only got to 100, "77, 7, F" - the flags can signal there is no merge here, yet, and that it is fully factored, so you don't need to store the last cofactor and the double 77 at the end - this is not the same F as above, it is used generic - about 7 bits will be enough to keep al situations, so the flag will always be a small decimal number).

So, what's your problem?

Last fiddled with by LaurV on 2022-10-29 at 08:44
LaurV is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
seasonal or long term trends kriesel Cloud Computing 19 2021-05-26 16:51
Long term evidence of civilization. xilman Science & Technology 65 2021-05-07 12:26
Using long long's in Mingw with 32-bit Windows XP grandpascorpion Programming 7 2009-10-04 12:13
I think it's gonna be a long, long time panic Hardware 9 2009-09-11 05:11
Long-term Primenet archive delta_t Data 3 2005-08-25 00:31

All times are UTC. The time now is 05:30.


Fri Dec 2 05:30:44 UTC 2022 up 106 days, 2:59, 0 users, load averages: 0.85, 0.92, 1.02

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.

โ‰  ยฑ โˆ“ รท ร— ยท โˆ’ โˆš โ€ฐ โŠ— โŠ• โŠ– โŠ˜ โŠ™ โ‰ค โ‰ฅ โ‰ฆ โ‰ง โ‰จ โ‰ฉ โ‰บ โ‰ป โ‰ผ โ‰ฝ โŠ โŠ โŠ‘ โŠ’ ยฒ ยณ ยฐ
โˆ  โˆŸ ยฐ โ‰… ~ โ€– โŸ‚ โซ›
โ‰ก โ‰œ โ‰ˆ โˆ โˆž โ‰ช โ‰ซ โŒŠโŒ‹ โŒˆโŒ‰ โˆ˜ โˆ โˆ โˆ‘ โˆง โˆจ โˆฉ โˆช โจ€ โŠ• โŠ— ๐–• ๐–– ๐–— โŠฒ โŠณ
โˆ… โˆ– โˆ โ†ฆ โ†ฃ โˆฉ โˆช โŠ† โŠ‚ โŠ„ โŠŠ โŠ‡ โŠƒ โŠ… โŠ‹ โŠ– โˆˆ โˆ‰ โˆ‹ โˆŒ โ„• โ„ค โ„š โ„ โ„‚ โ„ต โ„ถ โ„ท โ„ธ ๐“Ÿ
ยฌ โˆจ โˆง โŠ• โ†’ โ† โ‡’ โ‡ โ‡” โˆ€ โˆƒ โˆ„ โˆด โˆต โŠค โŠฅ โŠข โŠจ โซค โŠฃ โ€ฆ โ‹ฏ โ‹ฎ โ‹ฐ โ‹ฑ
โˆซ โˆฌ โˆญ โˆฎ โˆฏ โˆฐ โˆ‡ โˆ† ฮด โˆ‚ โ„ฑ โ„’ โ„“
๐›ข๐›ผ ๐›ฃ๐›ฝ ๐›ค๐›พ ๐›ฅ๐›ฟ ๐›ฆ๐œ€๐œ– ๐›ง๐œ ๐›จ๐œ‚ ๐›ฉ๐œƒ๐œ— ๐›ช๐œ„ ๐›ซ๐œ… ๐›ฌ๐œ† ๐›ญ๐œ‡ ๐›ฎ๐œˆ ๐›ฏ๐œ‰ ๐›ฐ๐œŠ ๐›ฑ๐œ‹ ๐›ฒ๐œŒ ๐›ด๐œŽ๐œ ๐›ต๐œ ๐›ถ๐œ ๐›ท๐œ™๐œ‘ ๐›ธ๐œ’ ๐›น๐œ“ ๐›บ๐œ”