Two more t600 factorizations.

[B]The first is especially useful[/B] because it clears a roadblock at

σ(5) = 2 * 3
σ(3^4) = 11^2
σ(11^4) = 5 * 3221
σ(3221^2) = 10378063
σ(10378063^30) = 124001 * C206
σ(124001^40) = C204

ECM to t50 by Pascal Ochem
SNFS sieving by RSALS
Post Processing by Carlos Pinho

[B]The second is interesting[/B] because it shows that some algebraic factors remain in the t lists. If comes from the fact that

Φ[sub]3[/sub](-x) divides Φ[sub]3[/sub](Φ[sub]5[/sub](x))

This generalizes to
Φ[sub]p[/sub](-x) divides Φ[sub]p[/sub](Φ[sub]q[/sub](x))

for primes p and q = 2kp-1.

This must be a "well known" result because it is simple to prove, but I don't know where to find it. If anybody knows, I'd appreciate the information in hopes there are other relationships in the same place that may be useful for factoring cyclotomic numbers.

[code]
σ(10378063^30) = 124001 * P103 * P104

P103 : 2041267618645492064177481059668887039258595276111661254188025491555522695254592044319100596029291931449
P104: 12027184981031802059856009972441839914449676567043085477315953738594472137349322180415007003971733880697


Residual from σ(200352613805032819912600348420612325430833525546106156675671920923953588489716195241607355764599737781^2)
Factors as P44 * C114

P44 = 10083260402669868760438182228013460439343771
[/code]

[quote=wblipp;223169]
[B]The second is interesting[/B] because it shows that some algebraic factors remain in the t lists. If comes from the fact that

Φ[sub]3[/sub](-x) divides Φ[sub]3[/sub](Φ[sub]5[/sub](x))

This generalizes to
Φ[sub]p[/sub](-x) divides Φ[sub]p[/sub](Φ[sub]q[/sub](x))

for primes p and q = 2kp-1.


[/quote]

For the benefit of those who didn't do maths at university, what does the Φ stand for?

Chris K

[QUOTE=chris2be8;223180]For the benefit of those who didn't do maths at university, what does the Φ stand for?

Chris K[/QUOTE]

[url]http://mathworld.wolfram.com/CyclotomicPolynomial.html[/url]

polcyclo in Pari/GP

[QUOTE=chris2be8;223180]For the benefit of those who didn't do maths at university, what does the Φ stand for?

Chris K[/QUOTE]

In the cases I've discussed, with p prime, Φ[sub]p[/sub](x) is just (x^p-1)/(x-1), which is also 1+x+x^2+ ... + x^(p-1). When n and p are both prime numbers, Φ[sub]p[/sub](n) = sigma(n^(p-1)). Factors of this, with n and p both prime, are what we are most often searching for to build factor chains for odd perfect numbers. I used Φ (Phi) rather than sigma because Φ(x) is polynomial in x, so I can make statements about polynomial factors that I cannot make using sigma because sigma is not a polynomial.

Although not relevant to my post, when n is composite and m divides n, then (x^m-1) divides (x^n-1). Φ[sub]n[/sub](x) is the quotient left after dividing out all possible (x^m-1), but it gets tricky because the smaller factors also divide the intermediate factors.

Φ[sub]x[/sub](-x) divides Φ[sub]3[/sub](Φ[sub]5[/sub](x)) is a fancy way of saying x^2 - x + 1 divides y^2 + y + 1 when y = x^4 + x^3 + x^2 + x + 1.

It's hardly with using Φ to say that, but it makes it much easier to state the generalization that
Φ[sub]p[/sub](-x) divides Φ[sub]p[/sub](Φ[sub]2kp-1[/sub](x))


For the given factor, this all means that
[code]
sigma(21156740205106357058426809^2) = 200352613805032819912600348420612325430833525546106156675671920923953588489716195241607355764599737781

and it is easy to find that

10083260402669868760438182228013460439343771

is a factor of

21156740205106357058426809^2 - 21156740205106357058426809 + 1

Hence

10083260402669868760438182228013460439343771

is also a factor of
sigma(200352613805032819912600348420612325430833525546106156675671920923953588489716195241607355764599737781^2)
[/code]

Finally, my question is "where do I look to find ideas like this?"

William

[quote=wblipp;223203] Although not relevant to my post, when n is composite and m divides n, then (x^m-1) divides (x^n-1). Φ[sub]n[/sub](x) is the quotient left after dividing out all possible (x^m-1), but it gets tricky because the smaller factors also divide the intermediate factors.
[/quote]

When I was playing with repunits a few years ago I wrote some code that checked if the gcd of the target and every shorter repunit was >1. Which isn't elegant but at least never misses factors.

Chris K

[QUOTE=wblipp;223169]It comes from the fact that Φ[sub]3[/sub](-x) divides Φ[sub]3[/sub](Φ[sub]5[/sub](x))
[code]
Residual from σ(200352613805032819912600348420612325430833525546106156675671920923953588489716195241607355764599737781^2)
Factors as P44 * C114
P44 = 10083260402669868760438182228013460439343771
[/code][/QUOTE]
Moreover, Φ[sub]3[/sub](Φ[sub]5[/sub](x))/Φ[sub]3[/sub](-x) = x^6+3x^5+5x^4+6x^3+7x^2+6x+3 gives an SNFS polynomial, here with x = 21156740205106357058426809 .
SNFS on the C114 cofactor actually worked. I don't know if GNFS would have been faster.
[code]C114=P54*P61
P54 = 313876426760805956819503756089549862540450067032468087
P61 = 2614348460677255305407490688398004009119889796458524428774839[/code]

[quote=wblipp;223203]Finally, my question is "where do I look to find ideas like this?"[/quote]
I don't know if algebraic factorizations like this are listed anywhere, but there doesn't seem to be much point of having such a list, since algebraic factors are simple to find by just factoring the polynomial (which is probably easier than looking it up in a table).

[QUOTE=Random Poster;223534]since algebraic factors are simple to find by just factoring the polynomial (which is probably easier than looking it up in a table).[/QUOTE]

Any particular factorization is easy to calculate, but it would be nice to know for what compositions factorizations exist. I'm thinking there may be some interesting and not too complicated algebra here. This works because
[CENTER]Φ[sub]5[/sub](-ζ[sub]3[/sub]) = ζ[sub]3[/sub][sup]2[/sup][/CENTER]
which generalizes to
[CENTER]Φ[sub]2kp-1[/sub](-ζ[sub]p[/sub]) = ζ[sub]p[/sub][sup]p-1[/sup][/CENTER]

I figure it's easier to stand on the shoulders of giants than to stand tall, and I'm guessing the giants already know if there are other two-level nesting factorizations, any three- or more-level factorizations, and especially any tricks comparable to Aurifeuillian factorizations.

So it's not a table of factorizations I am seeking. It's a discussion of the algebra that might reveal additional styles of factorizations.

William

Here is a Brent composite that is also a roadblock, although not a first composite. (251^101-1)/250 factors as P87 * P154.

ECM to t50 by yoyo@home
SNFS sieving by RSALS
Post Processing by Carlos Pinho

[code]
roadblock at
sigma(127^30) = 1310825268269643509279336731098526398390609803239319801398048897
sigma(1310825268269643509279336731098526398390609803239319801398048897^4)=251*C251
sigma(251^100)=240

P87: 116766037056531323104599508145214689479742861762780229989615902726444247646024673579231
P154: 7976076671385939501034954167242489099546597300317611893426665720846493780894261559023852746619493639560311659464648209471306854625418360780136090747261271[/code]

[quote=wblipp;223541]I figure it's easier to stand on the shoulders of giants than to stand tall, and I'm guessing the giants already know if there are other two-level nesting factorizations, any three- or more-level factorizations, and especially any tricks comparable to Aurifeuillian factorizations.[/quote]
There certainly are n-level factorizations for any n; if p and q1, q2,... are primes (qi not necessarily distinct) and p divides qi for all i, then Φ[sub]p[/sub](Φ[sub]q1[/sub](Φ[sub]q2[/sub](x))) has three factors, Φ[sub]p[/sub](Φ[sub]q1[/sub](Φ[sub]q2[/sub](Φ[sub]q3[/sub](x)))) has four factors and so on.

[QUOTE=wblipp;223541]Any particular factorization is easy to calculate, but it would be nice to know for what compositions factorizations exist.
<snip>
So it's not a table of factorizations I am seeking. It's a discussion of the algebra that might reveal additional styles of factorizations.

William[/QUOTE]

Well, I've gone and created a couple of tables of factorizations. Perhaps this will help in discovering algebraic relations.

I've created 3 files (all inside the attached zip file). They are 2phi1phi.txt, 3phi1phi.txt, and 3phi2phi.txt. Where:
2phi1phi lists Φ[sub]a[/sub](Φ[sub]b[/sub](x))/Φ[sub]c[/sub](x) [in tuples like a,b;c]
3phi1phi lists Φ[sub]a[/sub](Φ[sub]b[/sub](Φ[sub]c[/sub](x)))/Φ[sub]d[/sub](x) [in tuples like a,b,c;d]
3phi2phi lists Φ[sub]a[/sub](Φ[sub]b[/sub](Φ[sub]c[/sub](x)))/Φ[sub]d[/sub](Φ[sub]e[/sub](x)) [in tuples like a,b,c;d,e]

For 2phi1phi, the limits are 1 <= a,b,c <= 100
For 3phi1phi, the limits are 1 <= a,b,c,d <= 20
For 3phi2phi, the limits are 1 <= a,b,c,d,e <= 15

I didn't use -x in my calculations because I noticed, from your example, that Φ[sub]3[/sub](-x) = Φ[sub]6[/sub](x). There may be some interesting relationships using -x, but someone else will have to run a program to find that. Speaking of, in each file I've included the line of pari/gp code I used to create the results in that file. Hopefully someone will find this useful. Also, to make the pari/gp code a little shorter, I created an alias like so:
p(x)=polcyclo(x)
With that definition you can run the commands from each file.

I tried searching Google for tables or discussions of the above, but I couldn't find anything. That's why I created the tables. Hopefully it will spark a discussion here on what relationships we can find (and also on what constructs like this should be called!).