[lnkForumImage]
TotalShareware - Download Free Software
Confronta i prezzi di migliaia di prodotti.
Asp Forum
 Home | Login | Register | Search 


 

Forums >

comp.lang.python

How to factor using Python?

Nathan Pinno

3/10/2008 5:08:00 AM

How do I factor a number? I mean how do I translate x! into proper
Python code, so that it will always do the correct math?

Thanks in advance,
Nathan P.
14 Answers

Gabriel Genellina

3/10/2008 5:48:00 AM

0

On 10 mar, 02:08, Nathan Pinno <MadComputer...@gmail.com> wrote:

> How do I factor a number? I mean how do I translate x! into proper
> Python code, so that it will always do the correct math?

Do you want to compute x! (factorial of x)? That is, you want a
program that given a 4, returns 24?
Think how would you compute it by hand and try to write the same thing
using Python instructions.

If you come with a program and have a specific problem someone here
will be able to help you, but don't expect your homework to be done
for free...

--
Gabriel Genellina

Mensanator

3/10/2008 6:11:00 PM

0

On Mar 10, 12:48 am, Gabriel Genellina <gagsl-...@yahoo.com.ar> wrote:
> On 10 mar, 02:08, Nathan Pinno <MadComputer...@gmail.com> wrote:
>
> > How do I factor a number?

If factoring is actually what you want, the sympy module can do it.

>>> n = 85085**3
>>> print n
615969217989125
>>> import sympy
>>> f = sympy.factorint(n)
>>> f
[(5, 3), (7, 3), (11, 3), (13, 3), (17, 3)]
>>> ff = [[i[0]]*i[1] for i in f]
>>> ff
[[5, 5, 5], [7, 7, 7], [11, 11, 11], [13, 13, 13], [17, 17, 17]]
>>> fff = sympy.flatten(ff)
>>> fff
[5, 5, 5, 7, 7, 7, 11, 11, 11, 13, 13, 13, 17, 17, 17]

Provided that your needs are modest. It claims to be
able to handle 10 digit factors, but it certainly can't
handle numbers of this magnitude:

50818429800343305993022114330311033271249313957919046352679206262204589342623811236647989889145173098650749

As it takes a couple hours of run-time only to crash
with an out of memory error.

If you need to handle something like that, you may want to
get factor.exe which is part of the MIRACL library. The library
is in C and doesn't have a Python interface, but you can run
the .exe from Python and capture the output.

Keep in mind two things: factor.exe doesn't have consistent
output making it more difficult to interpret the captured
output. I re-compiled my copy of factor.exe to provide
consistent output.

The other thing is that factor.exe sometimes gets confused
claiming a number is composite that factor.exe is fully
capable of factoring. Luckily this can be easily fixed in
the Python program that calls it.

In the following example, if factor!.exe (my re-compiled
version) returns any composites, I simply feed them back
into the program until all are factored or determinened to
be truly intractable.

Note the times. If you have serious factoring needs, the
MIRACL solution is better than sympy.

## ========================================
## Phase 1
## ['COMPOSITE_FACTOR',
'50818429800343305993022114330311033271249313957919046352679206262204589342623811236647989889145173098650749']
##
## ['PRIME_FACTOR', '37']
## ['PRIME_FACTOR', '43']
## ['PRIME_FACTOR', '167']
## ['COMPOSITE_FACTOR', '507787751']
## ['PRIME_FACTOR', '69847']
## ['PRIME_FACTOR', '30697']
## ['PRIME_FACTOR', '89017']
## ['PRIME_FACTOR', '3478697']
## ['PRIME_FACTOR', '434593']
## ['PRIME_FACTOR', '49998841']
## ['PRIME_FACTOR', '161610704597143']
## ['PRIME_FACTOR', '14064370273']
## ['COMPOSITE_FACTOR', '963039394703598565337297']
## ['PRIME_FACTOR', '11927295803']
##
## 0.860000133514 seconds
## ========================================
## Phase 2
## ['COMPOSITE_FACTOR', '507787751']
##
## ['PRIME_FACTOR', '29819']
## ['PRIME_FACTOR', '17029']
##
## 0.0780000686646 seconds
## ========================================
## Phase 3
## ['COMPOSITE_FACTOR', '963039394703598565337297']
##
## ['PRIME_FACTOR', '518069464441']
## ['PRIME_FACTOR', '1858900129817']
##
## 0.0469999313354 seconds
## ========================================
##
## Factoring complete
##
## PRIME_FACTOR 37
## PRIME_FACTOR 43
## PRIME_FACTOR 167
## PRIME_FACTOR 17029
## PRIME_FACTOR 29819
## PRIME_FACTOR 30697
## PRIME_FACTOR 69847
## PRIME_FACTOR 89017
## PRIME_FACTOR 434593
## PRIME_FACTOR 3478697
## PRIME_FACTOR 49998841
## PRIME_FACTOR 11927295803
## PRIME_FACTOR 14064370273
## PRIME_FACTOR 518069464441
## PRIME_FACTOR 1858900129817
## PRIME_FACTOR 161610704597143
##
## ========================================


> I mean how do I translate x! into proper
> > Python code, so that it will always do the correct math?
>
> Do you want to compute x! (factorial of x)? That is, you want a
> program that given a 4, returns 24?
> Think how would you compute it by hand and try to write the same thing
> using Python instructions.
>
> If you come with a program and have a specific problem someone here
> will be able to help you, but don't expect your homework to be done
> for free...
>
> --
> Gabriel Genellina

Nathan Pinno

3/10/2008 11:32:00 PM

0

On Mar 10, 12:10 pm, Mensanator <mensana...@aol.com> wrote:
> On Mar 10, 12:48 am, Gabriel Genellina <gagsl-...@yahoo.com.ar> wrote:
>
> > On 10 mar, 02:08, Nathan Pinno <MadComputer...@gmail.com> wrote:
>
> > > How do I factor a number?
>
> If factoring is actually what you want, the sympy module can do it.
>
> >>> n = 85085**3
> >>> print n
> 615969217989125
> >>> import sympy
> >>> f = sympy.factorint(n)
> >>> f
>
> [(5, 3), (7, 3), (11, 3), (13, 3), (17, 3)]>>> ff = [[i[0]]*i[1] for i in f]
> >>> ff
>
> [[5, 5, 5], [7, 7, 7], [11, 11, 11], [13, 13, 13], [17, 17, 17]]>>> fff = sympy.flatten(ff)
> >>> fff
>
> [5, 5, 5, 7, 7, 7, 11, 11, 11, 13, 13, 13, 17, 17, 17]
>
> Provided that your needs are modest. It claims to be
> able to handle 10 digit factors, but it certainly can't
> handle numbers of this magnitude:
>
> 50818429800343305993022114330311033271249313957919046352679206262204589342623811236647989889145173098650749
>
> As it takes a couple hours of run-time only to crash
> with an out of memory error.
>
> If you need to handle something like that, you may want to
> get factor.exe which is part of the MIRACL library. The library
> is in C and doesn't have a Python interface, but you can run
> the .exe from Python and capture the output.
>
> Keep in mind two things: factor.exe doesn't have consistent
> output making it more difficult to interpret the captured
> output. I re-compiled my copy of factor.exe to provide
> consistent output.
>
> The other thing is that factor.exe sometimes gets confused
> claiming a number is composite that factor.exe is fully
> capable of factoring. Luckily this can be easily fixed in
> the Python program that calls it.
>
> In the following example, if factor!.exe (my re-compiled
> version) returns any composites, I simply feed them back
> into the program until all are factored or determinened to
> be truly intractable.
>
> Note the times. If you have serious factoring needs, the
> MIRACL solution is better than sympy.
>
> ## ========================================
> ## Phase 1
> ## ['COMPOSITE_FACTOR',
> '50818429800343305993022114330311033271249313957919046352679206262204589342623811236647989889145173098650749']
> ##
> ## ['PRIME_FACTOR', '37']
> ## ['PRIME_FACTOR', '43']
> ## ['PRIME_FACTOR', '167']
> ## ['COMPOSITE_FACTOR', '507787751']
> ## ['PRIME_FACTOR', '69847']
> ## ['PRIME_FACTOR', '30697']
> ## ['PRIME_FACTOR', '89017']
> ## ['PRIME_FACTOR', '3478697']
> ## ['PRIME_FACTOR', '434593']
> ## ['PRIME_FACTOR', '49998841']
> ## ['PRIME_FACTOR', '161610704597143']
> ## ['PRIME_FACTOR', '14064370273']
> ## ['COMPOSITE_FACTOR', '963039394703598565337297']
> ## ['PRIME_FACTOR', '11927295803']
> ##
> ## 0.860000133514 seconds
> ## ========================================
> ## Phase 2
> ## ['COMPOSITE_FACTOR', '507787751']
> ##
> ## ['PRIME_FACTOR', '29819']
> ## ['PRIME_FACTOR', '17029']
> ##
> ## 0.0780000686646 seconds
> ## ========================================
> ## Phase 3
> ## ['COMPOSITE_FACTOR', '963039394703598565337297']
> ##
> ## ['PRIME_FACTOR', '518069464441']
> ## ['PRIME_FACTOR', '1858900129817']
> ##
> ## 0.0469999313354 seconds
> ## ========================================
> ##
> ## Factoring complete
> ##
> ## PRIME_FACTOR 37
> ## PRIME_FACTOR 43
> ## PRIME_FACTOR 167
> ## PRIME_FACTOR 17029
> ## PRIME_FACTOR 29819
> ## PRIME_FACTOR 30697
> ## PRIME_FACTOR 69847
> ## PRIME_FACTOR 89017
> ## PRIME_FACTOR 434593
> ## PRIME_FACTOR 3478697
> ## PRIME_FACTOR 49998841
> ## PRIME_FACTOR 11927295803
> ## PRIME_FACTOR 14064370273
> ## PRIME_FACTOR 518069464441
> ## PRIME_FACTOR 1858900129817
> ## PRIME_FACTOR 161610704597143
> ##
> ## ========================================
>
> > I mean how do I translate x! into proper
> > > Python code, so that it will always do the correct math?
>
> > Do you want to compute x! (factorial of x)? That is, you want a
> > program that given a 4, returns 24?
> > Think how would you compute it by hand and try to write the same thing
> > using Python instructions.
>
> > If you come with a program and have a specific problem someone here
> > will be able to help you, but don't expect your homework to be done
> > for free...
>
> > --
> > Gabriel Genellina

Thanks on the factoring bit, but I did mean factorial, not factoring.
How do I code that correctly, so that I can figure the following
equation out: cos(Pi * (z-1)! / z). Python returns a invalid syntax
error and highlight the !. So it would be nice to find a way to solve
such a problem.

Thanks,
Nathan P.

Mensanator

3/11/2008 1:17:00 AM

0

On Mar 10, 6:32 pm, Nathan Pinno <MadComputer...@gmail.com> wrote:
> On Mar 10, 12:10 pm, Mensanator <mensana...@aol.com> wrote:
>
>
>
>
>
> > On Mar 10, 12:48 am, Gabriel Genellina <gagsl-...@yahoo.com.ar> wrote:
>
> > > On 10 mar, 02:08, Nathan Pinno <MadComputer...@gmail.com> wrote:
>
> > > > How do I factor a number?
>
> > If factoring is actually what you want, the sympy module can do it.
>
> > >>> n = 85085**3
> > >>> print n
> > 615969217989125
> > >>> import sympy
> > >>> f = sympy.factorint(n)
> > >>> f
>
> > [(5, 3), (7, 3), (11, 3), (13, 3), (17, 3)]>>> ff = [[i[0]]*i[1] for i in f]
> > >>> ff
>
> > [[5, 5, 5], [7, 7, 7], [11, 11, 11], [13, 13, 13], [17, 17, 17]]>>> fff = sympy.flatten(ff)
> > >>> fff
>
> > [5, 5, 5, 7, 7, 7, 11, 11, 11, 13, 13, 13, 17, 17, 17]
>
> > Provided that your needs are modest. It claims to be
> > able to handle 10 digit factors, but it certainly can't
> > handle numbers of this magnitude:
>
> > 508184298003433059930221143303110332712493139579190463526792062622045893426­23811236647989889145173098650749
>
> > As it takes a couple hours of run-time only to crash
> > with an out of memory error.
>
> > If you need to handle something like that, you may want to
> > get factor.exe which is part of the MIRACL library. The library
> > is in C and doesn't have a Python interface, but you can run
> > the .exe from Python and capture the output.
>
> > Keep in mind two things: factor.exe doesn't have consistent
> > output making it more difficult to interpret the captured
> > output. I re-compiled my copy of factor.exe to provide
> > consistent output.
>
> > The other thing is that factor.exe sometimes gets confused
> > claiming a number is composite that factor.exe is fully
> > capable of factoring. Luckily this can be easily fixed in
> > the Python program that calls it.
>
> > In the following example, if factor!.exe (my re-compiled
> > version) returns any composites, I simply feed them back
> > into the program until all are factored or determinened to
> > be truly intractable.
>
> > Note the times. If you have serious factoring needs, the
> > MIRACL solution is better than sympy.
>
> > ##  ========================================
> > ##  Phase 1
> > ##  ['COMPOSITE_FACTOR',
> > '50818429800343305993022114330311033271249313957919046352679206262204589342­623811236647989889145173098650749']
> > ##
> > ##  ['PRIME_FACTOR', '37']
> > ##  ['PRIME_FACTOR', '43']
> > ##  ['PRIME_FACTOR', '167']
> > ##  ['COMPOSITE_FACTOR', '507787751']
> > ##  ['PRIME_FACTOR', '69847']
> > ##  ['PRIME_FACTOR', '30697']
> > ##  ['PRIME_FACTOR', '89017']
> > ##  ['PRIME_FACTOR', '3478697']
> > ##  ['PRIME_FACTOR', '434593']
> > ##  ['PRIME_FACTOR', '49998841']
> > ##  ['PRIME_FACTOR', '161610704597143']
> > ##  ['PRIME_FACTOR', '14064370273']
> > ##  ['COMPOSITE_FACTOR', '963039394703598565337297']
> > ##  ['PRIME_FACTOR', '11927295803']
> > ##
> > ##  0.860000133514 seconds
> > ##  ========================================
> > ##  Phase 2
> > ##  ['COMPOSITE_FACTOR', '507787751']
> > ##
> > ##  ['PRIME_FACTOR', '29819']
> > ##  ['PRIME_FACTOR', '17029']
> > ##
> > ##  0.0780000686646 seconds
> > ##  ========================================
> > ##  Phase 3
> > ##  ['COMPOSITE_FACTOR', '963039394703598565337297']
> > ##
> > ##  ['PRIME_FACTOR', '518069464441']
> > ##  ['PRIME_FACTOR', '1858900129817']
> > ##
> > ##  0.0469999313354 seconds
> > ##  ========================================
> > ##
> > ##  Factoring complete
> > ##
> > ##  PRIME_FACTOR 37
> > ##  PRIME_FACTOR 43
> > ##  PRIME_FACTOR 167
> > ##  PRIME_FACTOR 17029
> > ##  PRIME_FACTOR 29819
> > ##  PRIME_FACTOR 30697
> > ##  PRIME_FACTOR 69847
> > ##  PRIME_FACTOR 89017
> > ##  PRIME_FACTOR 434593
> > ##  PRIME_FACTOR 3478697
> > ##  PRIME_FACTOR 49998841
> > ##  PRIME_FACTOR 11927295803
> > ##  PRIME_FACTOR 14064370273
> > ##  PRIME_FACTOR 518069464441
> > ##  PRIME_FACTOR 1858900129817
> > ##  PRIME_FACTOR 161610704597143
> > ##
> > ##  ========================================
>
> > > I mean how do I translate x! into proper
> > > > Python code, so that it will always do the correct math?
>
> > > Do you want to compute x! (factorial of x)? That is, you want a
> > > program that given a 4, returns 24?
> > > Think how would you compute it by hand and try to write the same thing
> > > using Python instructions.
>
> > > If you come with a program and have a specific problem someone here
> > > will be able to help you, but don't expect your homework to be done
> > > for free...
>
> > > --
> > > Gabriel Genellina
>
> Thanks on the factoring bit, but I did mean factorial, not factoring.
> How do I code that correctly, so that I can figure the following
> equation out: cos(Pi * (z-1)! / z). Python returns a invalid syntax
> error and highlight the !.

Because Python doesn't support the factorial operator.

> So it would be nice to find a way to solve
> such a problem.

Instead of using MIRACL which doesn't have a Python interface,
you could instaed get the GMP library which DOES have a Python
interface (Google for gmpy, make sure to get the version that
matches your Python version).

Then you can do gmpy.fac(z-1) to get the factorial.

or

>>> import math
>>> import gmpy
>>> a = math.cos(gmpy.pi(0)*gmpy.fac(4-1)/4)
>>> print a
-1.83690953073e-016



>
> Thanks,
> Nathan P.- Hide quoted text -
>
> - Show quoted text -

Mark Dickinson

3/11/2008 2:13:00 PM

0

On Mar 10, 7:32 pm, Nathan Pinno <MadComputer...@gmail.com> wrote:
> Thanks on the factoring bit, but I did mean factorial, not factoring.
> How do I code that correctly, so that I can figure the following
> equation out: cos(Pi * (z-1)! / z).

Is z an integer in this expression? (Note: it's not an equation---
there's no equality sign.) This looks suspiciously like
a formula that's supposed to be valid for real and possibly even
complex z, in which case what you're after is the gamma function.
(gamma(z) = (z-1)!). The real version of this should certainly
be present in numpy/scipy, and possibly the complex version too.

If z really is supposed to be an integer then you should be aware
that evaluating the expression directly is going to give almost
no accuracy, for z greater than 30 or so: the absolute error in the
argument to cosine will likely be much larger than 2*pi, so that
the result of the cos() evaluation is meaningless. You might be
better off computing w = (factorial(z-1) % (2*z)) as an integer;
then cos(pi*(z-1)!/z) can be computed as cos(pi * w/z).

Also, there are algebraic simplifications possible. If z is an
integer greater than 4, and not a prime number, then the value
of your expression is always going to be 1. If z is a prime
number then Wilson's theorem is going to come in handy.
(Google "Wilson's theorem prime").

Where does the expression come from? Is z a real or an integer?
Is this a genuine real-world formula, or something that appeared
in an elementary number theory textbook?

Mark

Joe Riopel

3/11/2008 2:38:00 PM

0

On Mon, Mar 10, 2008 at 1:08 AM, Nathan Pinno <MadComputerGuy@gmail.com> wrote:
> How do I factor a number? I mean how do I translate x! into proper
> Python code, so that it will always do the correct math?

This should work to do x! (factorial of x).

reduce(lambda x,y: x*y, range(1, x+1))

Joe Riopel

3/11/2008 2:41:00 PM

0

On Tue, Mar 11, 2008 at 10:38 AM, Joe Riopel <goon12@gmail.com> wrote:
> On Mon, Mar 10, 2008 at 1:08 AM, Nathan Pinno <MadComputerGuy@gmail.com> wrote:
> > How do I factor a number? I mean how do I translate x! into proper
> > Python code, so that it will always do the correct math?
>
> This should work to do x! (factorial of x).
>
> reduce(lambda x,y: x*y, range(1, x+1))


Sorry, the variable naming was confusing in that code.
>>> def dofact(x):
.... return reduce(lambda a,b: a*b, range(1,x+1))
....
>>> dofact(5)
120
>>>

Mark Dickinson

3/11/2008 2:51:00 PM

0

On Mar 10, 7:32 pm, Nathan Pinno <MadComputer...@gmail.com> wrote:
> Thanks on the factoring bit, but I did mean factorial, not factoring.
> How do I code that correctly, so that I can figure the following
> equation out: cos(Pi * (z-1)! / z). Python returns a invalid syntax
> error and highlight the !. So it would be nice to find a way to solve
> such a problem.

Aha. I've just found the "Is there a mathematical formula that will
find prime numbers?" thread that you started over on sci.math.
It looks like at least one of us has been trolled. I suggest you:

(1) Ignore the formula Gerry gave you. It's completely impractical as
a way of determining primality, and I'm certain that Gerry knew this.

(2) Learn some elementary number theory before trying to crack RSA.

Mark

Neal Becker

3/11/2008 3:04:00 PM

0

Nathan Pinno wrote:

> How do I factor a number? I mean how do I translate x! into proper
> Python code, so that it will always do the correct math?
>
> Thanks in advance,
> Nathan P.

import os
os.system('factor 25')

Mike Hansen

3/11/2008 3:57:00 PM

0

If one wants to do serious math using Python, the best bet is to use
Sage ( http://www.sa... ). Here are some examples:

sage: def f(x, bits=53):
.....: R = RealField(bits); z = R(x)
.....: return cos(R(pi) * factorial(z-1) / z)
sage: f(100.00,bits=1000)
0.999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999992343

sage: a =
50818429800343305993022114330311033271249313957919046352679206262204589342623811236647989889145173098650749
sage: time ecm.factor(a)
CPU times: user 0.00 s, sys: 0.06 s, total: 0.06 s
Wall time: 2.63

[3478697,
49998841,
11927295803,
518069464441,
1858900129817,
161610704597143,
157394131396743433859615518992811454816816449]

sage: a = ZZ.random_element(10**100); a
1266081670515546883639925088390407903294616094325617831128683357589913968497538978358203322629420841
sage: a.is_prime()
False
sage: b = a.next_prime(); b
8975665868645752218769838623717890808871334875974244952657480072373614614471639002293590745490978883
sage: b.is_prime()
True

--Mike