long-term sustainability

[xilman]

Originally Posted by kruoli

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.

[kruoli]

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?

[chalsall]

Originally Posted by kruoli

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.

[Happy5214]

Originally Posted by LaurV

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.

[Happy5214]

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).

[LaurV]

Originally Posted by Happy5214

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?