find all multiplicands and multipliers for a number

[Steven D'Aprano]

On Sat, 11 Apr 2015 04:08 pm, Paul Rubin wrote:

> Steven D'Aprano <steve+comp.lang.python at pearwood.info> writes:
>> It may be a bit slow for very large numbers. On my computer, this takes
>> 20 seconds:
>> py> pyprimes.factors.factorise(2**111+1)
>> [3, 3, 1777, 3331, 17539, 25781083, 107775231312019L]
> 
> This takes about 4 seconds on a Intel(R) Core(TM) i5-3230M CPU @ 2.60GHz
> laptop (64 bit linux):

Nice for some who have fast machines, but on my old jalopy, your code takes
110 seconds, more than five times slower than mine. It also returns the
wrong result:

[3, 3, 3, 3, 7, 19, 73, 87211, 262657, 1.4411518807585587e+17]

Oops, you have a float in there, how did that happen?

We can tell your code gives the wrong result. It claims that 7 is a factor
of 2**111+1:

py> n = 2**111 + 1
py> itertools.islice(fac(n), 0, 5)
<itertools.islice object at 0xb7c8f914>
py> list(itertools.islice(fac(n), 0, 5))
[3, 3, 3, 3, 7]


but that can't be right:

py> n % 7
2L

Seven in not a factor of 2**111 + 1.

The reason your code gives wrong results is that you perform true division /
rather than integer division // which means that you with n a float, which
loses precision:

py> (n/9) % 3  # nine is a factor
0.0
py> (n//9) % 3  # exact, without rounding
1L



-- 
Steven