Talk:Sylvester's sequence

From Wikipedia, the free encyclopedia

Good article Sylvester's sequence has been listed as one of the Mathematics good articles under the good article criteria. If you can improve it further, please do. If it no longer meets these criteria, you can delist it, or ask for a reassessment.
WikiProject Mathematics
Mathematics Portal
This article is within the scope of WikiProject Mathematics, which collaborates on articles related to mathematics.
Mathematics rating: Good article GA Class Mid Priority  Field: Number theory

Contents

[edit] Factorizations

I removed the factorizations of e_1 through e_5, because since most of them are prime, it was pretty pointless. The fact that 1807 = 13 * 139 is very easy to calculate. It is for the larger terms that I think it's actually useful to list prime factors. PrimeFan 19:06, 26 May 2006 (UTC)

1807 being composite is sufficiently nonobvious that in one version of the article I erroneously wrote that the first five terms are prime. So I think it's worth mentioning that one, at least in the text as we do now if not in the actual table. —David Eppstein 00:23, 30 November 2006 (UTC)

[edit] Comment on importance

Mid importance is about right for a general content encyclopedia. Sylvester's sequence has applications in several different problems, most of them relating to Egyptian fractions. If this was, say, PlanetMath or MathWorld, importance would have to be set to high. That is, if PlanetMathers could stop thinking about homeomorphisms and fictional curvature tensors for a couple of minutes. PrimeFan 23:01, 5 December 2006 (UTC)

I'm happy with mid importance also. To me the part about it being the fastest-growing rational series is a better argument for notability than the Egyptian fraction connection (much as I like Egyptian fractions) but neither is enough for me to call it of high importance. And the criterion for low importance says something about "could be trivial" which seems clearly untrue for this subject. So mid is a good fit. Should I ask what a "fictional curvature tensor" is? —David Eppstein 23:06, 5 December 2006 (UTC)
Yes inportance is a tricky one for maths articles. There are only 4 levels, which does not really leave enough scope to fit in 10 thousand maths articles. For me much of the importance characterisation is on how broad the concept is across all mathematical diciplines, possibly also encompassing depth. I find the grading of biographies from Wikipedia:WikiProject Biography/Core biographies more statisfying
Top - Must have had a large impact outside of their main discipline, across several generations, and in the majority of the world.
High - Must have had a large impact in their main discipline (i.e all of mathematics), across a couple of generations. Had some impact outside their country of origin.
Mid - Important in their discipline
Low - A contributor to their discipline and is included in Wikipedia to expand depth of knowledge of other articles.
this does not really cover the different fields of mathematics, so Sylvester's sequence are important in number theroy but not really of impact on other fields like geometry. Really I feel a need for a level between mid and low, for topics important in one field but not of wide importance across the whole of mathematics. --Salix alba (talk) 00:29, 6 December 2006 (UTC)
You don't think the question of which series can converge to a rational is a topic that goes beyond number theory? —David Eppstein 00:39, 6 December 2006 (UTC)
I think the graphical representation shows that Sylvester's sequence could have some application in geometry, but I can't say what that application would be right now. BTW, my compliments to the illustrator! PrimeFan 18:42, 6 December 2006 (UTC)
Thanks, again! BTW, the inspiration for the image was a comment by Nestor Romeral Andres on the OEIS page. —the illustrator (David Eppstein 19:08, 6 December 2006 (UTC))
I found another application to differential geometry this time; see the Boyer et al reference in the article. —David Eppstein 19:06, 8 December 2006 (UTC)

[edit] Good Article review

I've promoted this to a Good Article. Few inline cites, but that's ok for a math article given that everything is referenced, and there's no real ambiguity about what claims are referenced where. Twinxor t 09:23, 6 December 2006 (UTC)

The problem is, though, that it doesn't currently meet WP:LEAD, which is one of the good article criteria, and one which is handled pretty strictly these days. The lead is currently more like an opening section, whereas it should be an overview of the article. Can someone fix it? Geometry guy 15:18, 24 June 2007 (UTC)
Thanks to David Eppstein, it does now. Geometry guy 19:51, 24 June 2007 (UTC)

[edit] Question open??

Has it been proven that 0, 1, 2, 3, and 5 are the only values of n for which Sylvester(n) is prime?? This article says it is composite for all n 4-18 except 5. Georgia guy 18:22, 8 December 2006 (UTC)

I don't know of any such proof, although Sylvester himself mentioned the question of primality of these numbers. I imagine that the problem is of similar difficulty to that of primality of the Fermat numbers. —David Eppstein 19:06, 8 December 2006 (UTC)

[edit] New factor of s13

Mostly to Sairvin: thanks for adding the new factor of s13, 287001545675964617409598279. It's easy to check that it's correct, but I'd like to credit the appropriate source if a source can be found. Is this described somewhere else on the net? —David Eppstein 21:11, 26 April 2007 (UTC)

The factor was found by Sairvin and like some other factors by him, it was not mentioned elsewhere (I have e-mailed with him). I (Jens Kruse Andersen) have now created Factorization of Sylvester's sequence which lists this and all other known factors, verified with a simple PARI/GP script on the page. The only new factor for our table is 50201023123 in s18 (smaller than the already listed factor). I suggest extending the table to s22 which is now the largest for which the unfactored part of sn has been prp tested (it was composite). The end of the table would become:
Factors of sn
n Factorization
18 50201023123 × 139263586549 × C53339
19 C106721
20 352867 × C213435
21 387347773 × 1620516511 × C426863
22 91798039513 × C853750
Reliable sources like MathWorld mention computational prime number results by me, and use other pages on my site as reference for computational results. PrimeHunter 13:33, 3 September 2007 (UTC)
Ok, added. In general for easily-verified calculations like this I'm less worried about including self-published sources than I would be for other types of facts, but it's still good to have something to cite. —David Eppstein 18:14, 3 September 2007 (UTC)
Thanks. I have also accepted some selfpublished sources for utterly uncontroversial computer verified results. Something potentially controversial would be a different matter. PrimeHunter 20:53, 3 September 2007 (UTC)
How do you measure controversiality of citation of computer calculations? I would measure it by how many people can verify it on their own computers. Is this something anyone with a CAS can verify? Or does it take downloading and compiling some highly specialized program? Anton Mravcek 02:38, 5 September 2007 (UTC)
All it takes is computing the recurrence for Sylvester's sequence modulo the purported factor, which any competent programmer or CAS user should be able to do. In fact, here's a program you can run to do it:
# Usage: python checksyl.py p n
# checks whether p is a factor of Sylvester(n)

import sys
p = int(sys.argv[1])
n = int(sys.argv[2])

s = 2
for i in range(n):
    s = (s*(s-1)+1) % p

if s == 0:
    print "%d is a factor of s_%d" % (p,n)
else:
    print "%d is not a factor of s_%d" % (p,n)
—David Eppstein 02:56, 5 September 2007 (UTC)

As mentioned, there is also a PARI/GP test on my page. It's compact but maybe harder to read:

isfactor(i,p) = local(j,s);s=2%p;for(j=1,i,s=(s*(s-1)+1)%p);s==0

There is another function which calls it with all known factors. The verification output is given on the page. PARI/GP is free and anybody can run it to duplicate the verification. The compositeness proof for the large factors also have given output from a free program, PrimeForm/GW (but it takes longer to run at that size). "utterly uncontroversial" was probably a bad formulation. I was also thinking of the topic when I wrote it. Controversial topics, for example statistical analysis of published reliable raw data about something disputed, would usually need a good source. PrimeHunter 14:11, 5 September 2007 (UTC)

I should also have mentioned time consumption. There are some factorizations I could have my computer verify, but it would take days of computation and I only have one computer and a dozen other things to do on it. Anton Mravcek 19:39, 5 September 2007 (UTC)
In this case, it's just 3n arithmetic operations modulo the given factor, which for n in the twenties and factors with a few dozen digits takes a trivial amount of time. —David Eppstein 20:13, 5 September 2007 (UTC)
Yes, it's trivial to verify that they are factors - around 0.001 second in total on my PC for our table to s22 with the above isfactor(i,p). Proving primality of the listed prime factors with PARI/GP took around 2 seconds for P156 and a fraction of a second for the rest together. The only non-trivial verification is to show that the very large cofactors (especially that with 853750 digits) are composite. A claim that they were not composite would be remarkable and more verification would be preferred in that case. Extraordinary claims require extraordinary evidence. PrimeHunter 21:49, 5 September 2007 (UTC)
The command FactorInteger[e[8]] on Mathematica takes 12 seconds, so I'm not going to try it with s13. However, dividing s13 by ( 52387 × 5020387 × 5783021473 × 401472621488821859737 × 287001545675964617409598279 ) gives an integer and is instantaneous.
All of us here have access to Maple or Mathematica, but some people reading the page might be limited to the Calculator provided by their OS. A citation would therefore be nice, but hardly a priority. PrimeFan 22:31, 5 September 2007 (UTC)
If my site [1] is considered acceptable for computer verified results then it could be moved from External links to Footnotes. I think it is the only existing mention of some of the factors, except for Wikipedia and mirrors.[2] I actually got the idea for the site after failing to find a reference to the factors added here by Sairvin (he later told me that he added them to the article after discovering them himself and didn't mention them elsewhere). PrimeHunter 00:40, 6 September 2007 (UTC)
If you've been cited by Eric Weisstein at Mathworld, then I think you're good enough for Wikipedia. Anton Mravcek 16:27, 6 September 2007 (UTC)
Thanks. Maybe I should add that I have contributed to almost all the MathWorld entries which cite me: [3][4][5][6][7][8][9]. MathWorld is professionally edited and I can only make suggestions. PrimeHunter 17:55, 6 September 2007 (UTC)

BTW, re your comments on your web site about not having the Vardi reference: I do have a copy of it. He states explicitly (p.84) that the prime factors must be 1 mod 3, long prior to your mention of Dario Alpern observing this in 2006. He also observes that one can eliminate the primes for which the quartic polynomial (x2 - x + 1)2 - (x2 - x + 1) + 1 = 0 (mod p) has no solution. And rather than doing full modular multiplication in each iteration, he squares the previous iterate by repeated addition (analogously to the usual powermod algorithm for taking modular powers by repeated multiplication). Was there anything else you wanted checked in it? —David Eppstein 01:15, 6 September 2007 (UTC)

Thanks a lot. I will update my page later. Our article says "Via this technique he found that 1166 out of the first three million primes are divisors of Sylvester numbers". I found and verified 1167 primes that are divisors, starting with 2 and 3. Can you confirm he says 1166, and do you know whether he excludes 2 which divides s0 = 2? PrimeHunter 01:41, 6 September 2007 (UTC)
He writes (p.87) "Using these method[sic], one finds 1166 primes p out of the first three million primes (i.e., p smaller than fifty million) which divide a Euclid number." There's no obvious statement restricting this to odd primes, and this is immediately following a code listing that only tests primes congruent to 1 mod 3, so it seems strange that he would omit 2 but not omit 3. His list of prime factors of sn for p < 5×107 and n ≤ 200 does include 2 and 3. —David Eppstein 18:39, 6 September 2007 (UTC)
Thanks. I have recomputed and triple checked the factors below prime(3000000) = 49979687. I still get the 1167 in [10]: 2, 3, 7, ..., 49967221. The next is above fifty million. Vardi's book is considered more reliable by Wikipedia and I have a COI so I will let others decide whether to mention my conflicting count (or maybe avoid the problem by mentioning no count?). It's a minor detail anyway. PrimeHunter 20:55, 6 September 2007 (UTC)
I see David Eppstein has mentioned my conflicting count in the article. I have updated my site with information he gave about Vardi, and added newly computed factors from 109 to 3×109 in si for i>200 (doesn't affect our table which has i<=22). I will continue to 232 and maybe suggest the factor counts to MathWorld. PrimeHunter 18:10, 9 September 2007 (UTC)