Anonymous user
Talk:Proper divisors: Difference between revisions
→Shouldn't it be "The proper divisors of a STRICTLY positive integer N are those numbers..."?: - -
(→Python: comparisons: New timings for larger N) |
(→Shouldn't it be "The proper divisors of a STRICTLY positive integer N are those numbers..."?: - -) |
||
| (7 intermediate revisions by 5 users not shown) | |||
Line 12:
::::::The "unless n is 1" has been corrected -- 1 is not an exception. Some sources include the negatives of the proper divisors as well, leading some to the definition including "...is a positive divisor...". The input 0 is another oddball case -- Wolfram/Alpha and Pari/GP don't agree on its divisors, for example. [[User:Danaj|Danaj]] ([[User talk:Danaj|talk]]) 18:43, 17 December 2014 (UTC)
::::::: Should probably use "task has changed" warning for older solutions, when that's what happened. Not always a big deal, but sometimes this can help someone editing (or even just reading) the code understand what's going on. --[[User:Rdm|Rdm]] ([[User talk:Rdm|talk]]) 23:52, 17 December 2014 (UTC)
Below I think we show that there is a difference between finding factors for a single number and for a lot of numbers. While 20,000 isn't that many, I think if we mandate that this tasks starts from an efficient algorithm for factoring many integers then it continues from where Factors of an integer finished and adds to it rather than failing to use the lessons already learnt there--[[User:Nigel Galloway|Nigel Galloway]] ([[User talk:Nigel Galloway|talk]]) 13:04, 20 December 2014 (UTC)
== Definition ==
Line 28 ⟶ 30:
===Python: comparisons===
You may wish to look at the fourth example [[Factors_of_an_integer#Python]] for an efficient method of finding the factors of a large number of
Thanks Nigel,I should really turn all factor examples into proper divisor functions then time them for implementing, say, the [[Aliquot sequence classifications]] task which would probably thrash them the most. Hmmm. --[[User:Paddy3118|Paddy3118]] ([[User talk:Paddy3118|talk]]) 16:10, 19 December 2014 (UTC)
Line 113 ⟶ 115:
: Python 3.4.2 |Continuum Analytics, Inc.| (default, Oct 22 2014, 11:51:45) [MSC v.1600 64 bit (AMD64) for what it is worth, but it is the broad relative timings that might be of use.
:--[[User:Paddy3118|Paddy3118]] ([[User talk:Paddy3118|talk]]) 08:35, 20 December 2014 (UTC)
:: We ought to be careful when trying to decide what's a good way to do things here, because it depends on how the proper divisor routine is going to be used in the end. If we know we'll factorize a sizable chunk of contiguous integers, sieving is significantly faster due to lower overhead:
<lang python>from math import sqrt
def factors(bot, top):
max_p = int(sqrt(top - 1))
sieve = [True] * (max_p - 1)
for p in range(2, int(sqrt(max_p)) + 1):
if not sieve[p - 2]: continue
for x in range(p*p, max_p + 1, p):
sieve[x - 2] = False
primes = [b[0] for b in enumerate(sieve, 2) if b[1]]
divs = [() for _ in range(bot, top)]
for p in primes:
for x in range(max(p*p, (bot + p - 1)//p*p), top, p):
divs[x - bot] += (p,)
return divs
def prop_divs(bot, top):
for (v,f) in enumerate(factors(bot, top), bot):
pd = [1]
for p in f:
inc, s = [],1
while not v%p:
s,v = s*p, v//p
inc += [a*s for a in pd]
pd += inc
if v > 1:
pd += [a*v for a in pd]
yield(pd[:-1])
print(list(enumerate(prop_divs(1, 11), 1)))
print(max([(len(pd), v) for (v,pd) in enumerate(prop_divs(500000, 550001), 500000)]))</lang>
:: at least until you run out of memory. But the above code fares horribly if you try to factor a single large number, say <code>12345678901234567</code> (I'm not saying it'd do better when factorizing ''many'' huge numbers, it's just that other methods listed here would then be equally bad, if not worse). I think we don't need to look too hard for a "best" method, just something that's easy to understand and uses a sound algorithm (that being said, my own code tends to be quite unreadable -- doing the right thing is harder than advocating it). After all, if running time is the absolute priority, I wouldn't use Python to begin with. --[[User:Ledrug|Ledrug]] ([[User talk:Ledrug|talk]]) 08:35, 23 December 2014 (UTC)
:::I too don't think that run time alone should dictate what python solution should be preferred for this ''set'' of tasks. If a good looking solution is one of the fastest then it would make an easy choice. --[[User:Paddy3118|Paddy3118]] ([[User talk:Paddy3118|talk]]) 15:38, 23 December 2014 (UTC)
== Shouldn't it be "The proper divisors of a STRICTLY positive integer N are those numbers..."? ==
To my knowledge, "positive integer" means every whole number not less than zero whereas "strictly positive integer" means every whole number not less than one. Better yet, we could replace "positive integer N" with a completely unambiguous phrase such as those that I've used in my previous sentence. As it stands, the task description could be misread as desiring the use of zero. --[[User:ReeceGoding|ReeceGoding]] ([[User talk:ReeceGoding|talk]]) 20:57, 10 June 2020 (UTC)
: From [[wp:Integer#Order-theoretic_properties|Wikipedia]], quote:
<blockquote>An integer is positive if it is greater than zero and negative if it is less than zero. Zero is defined as neither negative nor positive.</blockquote>
: so, no the task verbiage need not contain the word "STRICTLY" as zero is not a positive integer. --[[User:Thundergnat|Thundergnat]] ([[User talk:Thundergnat|talk]]) 00:02, 11 June 2020 (UTC)
: WP has positive integers start from 1 not zero here https://en.m.wikipedia.org/wiki/Natural_number. With that, the linked article, and you not stating that it stops you completing the task, then any need seems small. --[[User:Paddy3118|Paddy3118]] ([[User talk:Paddy3118|talk]]) 00:11, 11 June 2020 (UTC)
| |||