⚠️ Warning: This is a draft ⚠️

This means it might contain formatting issues, incorrect code, conceptual problems, or other severe issues.

If you want to help to improve and eventually enable this page, please fork RosettaGit's repository and open a merge request on GitHub.

== Dupe? ==

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 ==

I don't believe the definition used is correct. In particular "always includes 1" doesn't follow from the definition given at the linked site, or [http://mathworld.wolfram.com/ProperDivisor.html MathWorld] or [http://oeis.org/A032741 OEIS].

I believe you when you say the second version is faster than the first, but note (n + 1) // 2 + 1 can be replaced by floor(sqrt(n)) in the first version. 141 rather than 10,000 in the case of 20,000. This would be a fairer comparison!--[[User:Nigel Galloway|Nigel Galloway]] ([[User talk:Nigel Galloway|talk]]) 14:32, 19 December 2014 (UTC)

### 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 contiguous integers--[[User:Nigel Galloway|Nigel Galloway]] ([[User talk:Nigel Galloway|talk]]) 15:57, 19 December 2014 (UTC)

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)

:I hacked together timings and cut-n-pasted stuff into Ipython's command line...

```#... marshall the factorials (ommitted copy of code from tasks) ...

def fact2pd(factorise):
'Change factoriser to proper divisor function'
def proper_divs(n):
if n == 1:
return set()
if n == 0:
return {1}
f = set(factorise(n))
try:
f.remove(n)
except KeyError:
pass
return f
proper_divs.__doc__ = 'From %s: %s' % (factorise.__name__, factorise.__doc__)
return proper_divs

pd = [fact2pd(fact) for fact in (factors1, factors2, factors3, factors4, factors5)] + [proper_divs22, proper_divs21]

nmax = 50000
ans = [proper_divs21(n) for n in range(1, nmax)]
_divs.cache_clear()

for proper_divs in pd:
print(proper_divs.__doc__)
%time print('  OK' if ans == [proper_divs(n) for n in range(1, nmax)] else '  Whoops!')
```
```From factors1: Naive and slow but simplest (check all numbers from 1 to n):
OK
Wall time: 2min 38s
From factors2: Slightly better (realize that there are no factors between n/2 and n):
OK
Wall time: 1min 22s
From factors3: Much better (realize that factors come in pairs, the smaller of which is no bigger than sqrt(n)):
OK
Wall time: 1.44 s
From factors4: More efficient when factoring many numbers:
OK
Wall time: 1.06 s
From factors5: NEW 2014/12/20: More efficient when factoring many numbers:
OK
Wall time: 772 ms
A very literal interpretation
OK
Wall time: 1min 38s
Return the set of proper divisors of n.
OK
Wall time: 2.69 s
```

:If I time from 500,000 to 550,000 instead of from 1 to 50,000 we can see the effect of larger N:

```pd = [fact2pd(fact) for fact in (factors3, factors4, factors5)] + [ proper_divs21]
nrange = range(500000, 550001)
ans = [proper_divs21(n) for n in nrange]
_divs.cache_clear()

for proper_divs in pd:
print(proper_divs.__doc__)
%time print('  OK' if ans == [proper_divs(n) for n in nrange] else '  Whoops!')
```
```From factors3: Much better (realize that factors come in pairs, the smaller of which is no bigger than sqrt(n)):
OK
Wall time: 4.58 s
From factors4: More efficient when factoring many numbers:
OK
Wall time: 2.17 s
From factors5: NEW 2014/12/20: More efficient when factoring many numbers:
OK
Wall time: 1.22 s
Return the set of proper divisors of n.
OK
Wall time: 4.51 s
```

:(I dropped a few obviously slow functions). :All timings where done on the same lappy doing roughly the same things i.e. not much apart from the run. : 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:

```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)]))
```

:: at least until you run out of memory. But the above code fares horribly if you try to factor a single large number, say `12345678901234567` (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)