Wikipedia:Reference desk/Archives/Mathematics/2024 January 29

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is a transcluded archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

January 29

List of factorization of 2ⁿ-1

Is there a list of factorizations available of 2ⁿ-1 for n up to about 175? Bubba73 ^{You talkin' to me?} 04:00, 29 January 2024 (UTC)

Funny enough, I found such a list embedded in somebody's Python file on Github. Here ya go. GalacticShoe (talk) 04:38, 29 January 2024 (UTC)

Thanks a million! It is missing a few, starting at n=193, but I believe that is sufficient for my needs. Bubba73 ^{You talkin' to me?} 04:47, 29 January 2024 (UTC)

For future reference, the missing values of $n$ (up to 256) are 193, 211, 227, 229, 251, 253; attempting to factor them with WolframAlpha shows that indeed the composite numbers that need to be factored are very large. GalacticShoe (talk) 05:18, 29 January 2024 (UTC)

Yes, apparently they were using their own program to factor them, until they got to a certain size, then they switched to using Wolfram Alpha, which did most of the rest, except for ones that took too long. ~~

I also found this page with a list up to 263: [1]. It has a dead link for "more data", but you can find it on the Wayback Machine: [2]. This page has some very extensive data products such as [3] with an explanation of the format [4]. For 193 it lists:

     M( 193 )C: 13821503
     M( 193 )C: 61654440233248340616559
     M( 193 )D

The text on the page notes that "the largest prime factor is almost always implied, as some of them are _very_ large". --Amble (talk) 17:31, 29 January 2024 (UTC)

Thanks, I'll look at that. Bubba73 ^{You talkin' to me?} 00:37, 30 January 2024 (UTC)

See the Cunningham table: [5], also this list 210.244.72.152 (talk) 03:00, 3 February 2024 (UTC)

Followup remark: I implemented this in a program, to look up these factorizations rather than factor them each time. I did a test and it was 62x faster, so it can do in a minute what would take an hour, etc. Bubba73 ^{You talkin' to me?} 10:39, 1 February 2024 (UTC)

@Bubba73: http://factordb.com has a database with billions of known prime factors of various numbers. It accepts expressions like 2^253-1. You can also enter 2^n-1 and get a list of factorizations. Composite factors are blue. 2^1277-1 is the smallest without a known factor so the whole number is listed in blue. I don't know whether there are smaller numbers with a partial but not full factorization. PrimeHunter (talk) 17:59, 1 February 2024 (UTC)

Thanks, I didn't know about that. I needed a table of complete factorizations for four types of numbers. I got what I need with my own program on three of them, but 2^n-1 bogged down about n=139. But I got it up to n=192 from the source somewhere above, which I think will be sufficient. But if it turns out that I need more, I can use this. Bubba73 ^{You talkin' to me?} 20:53, 1 February 2024 (UTC)

@PrimeHunter: At factordb.com, can you enter a series and loop on that? That is, if $f_{n}$ is the sum of a series up to n, can you get the factors of $f_{n}$, for n = 1 to x? Bubba73 ^{You talkin' to me?} 05:31, 3 February 2024 (UTC)

@Bubba73: I don't think so. PrimeHunter (talk) 10:41, 3 February 2024 (UTC)