How to factor using Python?

[Nathan Pinno]

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.

[Gabriel Genellina]

On 10 mar, 02:08, Nathan Pinno <[e-mail]:

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]

On Mar 10, 12:48*am, Gabriel Genellina <[e-mail]:

On 10 mar, 02:08, Nathan Pinno <[e-mail]:

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:

50818429800343305993022114330311033271249313957919 04635267920626220458934262381123664798988914517309 8650749

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',
'5081842980034330599302211433031103327124931395791 90463526792062622045893426238112366479898891451730 98650749']
##
## ['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]

On Mar 10, 12:10 pm, Mensanator <[e-mail]:

On Mar 10, 12:48 am, Gabriel Genellina <[e-mail]:

On 10 mar, 02:08, Nathan Pinno <[e-mail]:

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:

50818429800343305993022114330311033271249313957919 04635267920626220458934262381123664798988914517309 8650749

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',
'5081842980034330599302211433031103327124931395791 90463526792062622045893426238112366479898891451730 98650749']
##
## ['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]

On Mar 10, 6:32*pm, Nathan Pinno <[e-mail]:

On Mar 10, 12:10 pm, Mensanator <[e-mail]:

On Mar 10, 12:48 am, Gabriel Genellina <[e-mail]:

On 10 mar, 02:08, Nathan Pinno <[e-mail]:

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 iin 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:

50818429800343305993022114330311033271249313957919 0463526792062622045893426*238112366479898891451730 98650749

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',
'5081842980034330599302211433031103327124931395791 9046352679206262204589342*623811236647989889145173 098650749']
##
## *['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]

On Mar 10, 7:32*pm, Nathan Pinno <[e-mail]:

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]

On Mon, Mar 10, 2008 at 1:08 AM, Nathan Pinno <Ma************@gmail.comwrote:

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]

On Tue, Mar 11, 2008 at 10:38 AM, Joe Riopel <go****@gmail.comwrote:

On Mon, Mar 10, 2008 at 1:08 AM, Nathan Pinno <Ma************@gmail.comwrote:

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]

On Mar 10, 7:32*pm, Nathan Pinno <[e-mail]:

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]

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]

If one wants to do serious math using Python, the best bet is to use
Sage ( http://www.sagemath.org ). 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.999999999999999999999999999999999999999999999999 99999999999999999999999999999999999999999999999999 99999999999999999999999999999999999999999999999999 99999999999999999999999999999999999999999999999999 99999999999999999999999999999999999999999999999999 99999999999999999999999999999999999999999999999923 43

sage: a =
50818429800343305993022114330311033271249313957919 04635267920626220458934262381123664798988914517309 8650749
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
12660816705155468836399250883904079032946160943256 17831128683357589913968497538978358203322629420841
sage: a.is_prime()
False
sage: b = a.next_prime(); b
89756658686457522187698386237178908088713348759742 44952657480072373614614471639002293590745490978883
sage: b.is_prime()
True

--Mike

[Lie]

On Mar 10, 12:08*pm, Nathan Pinno <[e-mail]:

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.

Factorial algorithm is a very simple and common algorithm, and it's
one of the most basic of all recursive algorithm
def fact(x):
return x * fact(x - 1)

That recursive function is very close to the basic definition of
factorials, that is
x! = x * (x - 1)!

If however, you expected x to be a real (float) value, you'd better
consider the gamma function as Mark Dickinson pointed out. Wikipedia
is a good start to create your gamma function:
http://en.wikipedia.org/wiki/Factorial
http://en.wikipedia.org/wiki/Gamma_function

[Lie]

On Mar 11, 11:47*pm, Lie <[e-mail]:

On Mar 10, 12:08*pm, Nathan Pinno <[e-mail]:

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.

Factorial algorithm is a very simple and common algorithm, and it's
one of the most basic of all recursive algorithm
def fact(x):
* * return x * fact(x - 1)

As an exercise (actually I forget), I'll let you figure out yourself
why the above function doesn't work. There is only one simple line to
be added and all's done.

Hint: There are two important elements in all recursive algorithm, the
catch-all return statement (which I've given you) and the conditioned
return statement (which you've got to figure out yourself)

[Shane Geiger]

def fact(x):
if x == 1: return 1 # don't forget this
else: return x * fact(x - 1)

print fact(5)

Factorial algorithm is a very simple and common algorithm, and it's
one of the most basic of all recursive algorithm
def fact(x):
return x * fact(x - 1)

That recursive function is very close to the basic definition of
factorials, that is
x! = x * (x - 1)!

If however, you expected x to be a real (float) value, you'd better
consider the gamma function as Mark Dickinson pointed out. Wikipedia
is a good start to create your gamma function:
http://en.wikipedia.org/wiki/Factorial
http://en.wikipedia.org/wiki/Gamma_function

--
Shane Geiger
IT Director
National Council on Economic Education
sg*****@ncee.net | 402-438-8958 | http://www.ncee.net

Leading the Campaign for Economic and Financial Literacy

[Mensanator]

On Mar 11, 10:57*am, Mike Hansen <[e-mail]:

If one wants to do serious math using Python, the best bet is to use
Sage (http://www.sagemath.org). *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.999999999999999999999999999999999999999999999999 9999999999999999999999999*999999999999999999999999 99999999999999999999999999999999999999999999999999 9*999999999999999999999999999999999999999999999999 999999999999999999999999999*9999999999999999999999 99999999999999999999999999999999999999999999999999 923*43

If one wants to do serious math using Python, it would be even
better to understand the math before breaking out Sage.

Didn't you realize that cos(pi*n) is a red herring? That you
only need to know if the rational factorial(z-1)/z has a denominator

>1 (although you have to make allowances when it's 2)?

2 Prime: True True Prime: True 1/2
3 Prime: True True Prime: True 2/3
4 Prime: False True Prime: False 3/2
5 Prime: True True Prime: True 24/5
6 Prime: False True Prime: False 20
7 Prime: True True Prime: True 720/7
8 Prime: False True Prime: False 630
9 Prime: False True Prime: False 4480
10 Prime: False True Prime: False 36288
11 Prime: True True Prime: True 3628800/11
12 Prime: False True Prime: False 3326400
13 Prime: True True Prime: True 479001600/13
14 Prime: False True Prime: False 444787200
15 Prime: False True Prime: False 5811886080
16 Prime: False True Prime: False 81729648000
17 Prime: True True Prime: True 20922789888000/17
18 Prime: False True Prime: False 19760412672000
19 Prime: True True Prime: True 6402373705728000/19

>
sage: a =
50818429800343305993022114330311033271249313957919 0463526792062622045893426*238112366479898891451730 98650749
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
12660816705155468836399250883904079032946160943256 1783112868335758991396849*753897835820332262942084 1
sage: a.is_prime()
False
sage: b = a.next_prime(); b
89756658686457522187698386237178908088713348759742 4495265748007237361461447*163900229359074549097888 3
sage: b.is_prime()
True

--Mike