mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Programming

Reply
 
Thread Tools
Old 2021-10-10, 20:11   #23
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

22·3·5·23 Posts
Default

If you press the button Show more divisors you will see the divisor 7 in the second batch.

My application sorts the results inside batches.

The number 18! has 14688 divisors. The application shows up to 1000 divisors at a time. So you will have to press the button Show more divisors 14 times to get all of them.

Last fiddled with by alpertron on 2021-10-10 at 20:15
alpertron is offline   Reply With Quote
Old 2021-10-11, 01:05   #24
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

22×3×5×23 Posts
Default

Quote:
Originally Posted by R. Gerbicz View Post
Say d1=4 from S1 then the divisors that using this d1 is just:
1*d1
3*d1
9*d1
27*d1
for example we are at d=3*d1 and this was the smallest divisor, then the next smallest (using this d1) will be 9*d1, and this is what happens in general you need to move to the next term in S2 [notice that S2 was sorted].

this is what happens in the algorithm:

at the beginning:
the priority queue contains: 1,2,4,8. At the top, the smallest is 1, we pop this, and push to the queue 3*d1=3*1=3.
now in the queue: 3,2,4,8, the smallest is 2, pop this and push 3*d1=3*2=6.
the updated queue: 3,6,4,8 the smallest is 3, pop this and push 9*d1=9*1=9.
the queue: 9,6,4,8 etc.

Say n has roughly 10^7 divisors then the best S1, S2 [in general/average case] contains roughly
sqrt(10^7)~3000 divisors and you can generate quickly the sorted divisors in batches in-fly using only these small S1,S2 sets.

ps.
you don't need a sorted S1.
ofcourse in the queue you need to maintain also the pointers to S2 [and S1] to construct the next numbers at push.
the above 9,6,4,8 is only a list to describe the algorithm; use built-in priority queue/heap or implement that.
I think I understood your method. The contents of the priority queue and the sorted divisors are the following:

Code:
S1 = {1,2,4,8}, S2 = {1,3,9,27}

1,2,4,8 -> 1
3,2,4,8 -> 2
3,6,4,8 -> 3
9,6,4,8 -> 4
9,6,12,8 -> 6
9,18,12,8 -> 8
9,18,12,24 -> 9
27,18,12,24 -> 12
27,18,36,24 -> 18
27,54,36,24 -> 24
27,54,36,72 -> 27
--,54,36,72 -> 36
--,54,108,72 -> 54
--,--,108,72 -> 72
--,--,108,216 -> 108
--,--,--,216 -> 216
alpertron is offline   Reply With Quote
Old 2021-10-11, 16:47   #25
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

2×32×83 Posts
Default

Quote:
Originally Posted by alpertron View Post
I think I understood your method. The contents of the priority queue and the sorted divisors are the following:
That looks like good, maybe not the best example, there omega(n1)=omega(n2)=1, it was Sardonicus's tiny number.
As said S2 should be sorted.
R. Gerbicz is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Phantom factorization - subcubic factorization of integers? Alberico Lepore Alberico Lepore 1 2020-05-27 12:20
MEGAPOST apps to compute mersenne primes, factorization and computing decimals of pi on android thorken Software 53 2019-01-29 15:34
GPU Computing Cheat Sheet (a.k.a. GPU Computing Guide) Brain GPU Computing 20 2015-10-25 18:39
Complete Factorization??? Khemikal796 Factoring 13 2005-04-15 15:21
The difference between P2P and distributed computing and grid computing GP2 Lounge 2 2003-12-03 14:13

All times are UTC. The time now is 16:04.


Tue Oct 19 16:04:39 UTC 2021 up 88 days, 10:33, 0 users, load averages: 2.13, 1.63, 1.40

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, 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.