factors of 2^k - 1

[preda]

f(k) = number of [prime] factors of 2^k - 1

Can somebody please help me analyze how f(k) depends on k?

In particular I'd like to know which Ks produce large values for f(k).

Empirically, I have this small list of k with large f(k):
? m=2; for(i=2,300,n=#factor(2^i-1)[,1]; if(n>m, m=n;print(i, " ", n)))
8 3
12 4
20 5
24 6
36 8
48 9
60 11
72 12
120 15
144 17
180 21
288 24

[R. Gerbicz]

Originally Posted by preda

f(k) = number of [prime] factors of 2^k - 1

Can somebody please help me analyze how f(k) depends on k?

Use https://en.wikipedia.org/wiki/Zsigmondy%27s_theorem !!!
With that f(k)>=numdiv(k)-2.

[preda]

Originally Posted by R. Gerbicz

Use https://en.wikipedia.org/wiki/Zsigmondy%27s_theorem !!!
With that f(k)>=numdiv(k)-2.

Interesting, thank you!

So you apply Zsigmondy's theorem with a=2 and b=1?
Then it states that 2^k-1 has a factor that doesn't divide any 2^i-1 with i<k.
But how do you progress to numdiv(k)?

I'd also like to understand how f(k) grows with k for the "best" Ks. Maybe this can be approximated with the growth of numdiv(k)?

So, I guess I want to find a simple function g(x) such that
limsup(k->inf, f(k)/g(k)) exists, is finite and >0. (I call g(x) a "sup approximation" of f(x)).

I venture a guess, would sqrt(log(k)) be such a "sup" approximation of f(k)? or sqrt(k) a "sup" approximation for numdiv(k)?

(Apparently, that's one of big-Omega's meanings https://en.wikipedia.org/wiki/Big_O_notation )

[R. Gerbicz]

Originally Posted by preda

Interesting, thank you!

So you apply Zsigmondy's theorem with a=2 and b=1?
Then it states that 2^k-1 has a factor that doesn't divide any 2^i-1 with i<k.
But how do you progress to numdiv(k)?

Yes, use a=2,b=1 sort the divisors of k in increasing order: d1=1<d2<...<d_u=k (if k has u divisors), then for any t it is true that 2^d_t-1 | 2^k-1, because d_t | k, but if d_t !=1,6 then with Zsigmondy theorem 2^d_t-1 has a new prime divisor, that doesn't divide 2^x-1 for every x<d_t. With this we'll have at least numdiv(k)-2 distinct prime divisors

Originally Posted by preda

I'd also like to understand how f(k) grows with k for the "best" Ks. Maybe this can be approximated with the growth of numdiv(k)?

My guess is that on average we see roughly c*numdiv(k)*log(k) prime divisors of 2^k-1, but if k has lots of divisors, then the magnitude of this is still numdiv(k). To get the growth of numdiv see https://en.wikipedia.org/wiki/Divisor_function, using that for fixed eps>0 we'll have infinitely many n for that
numdiv(n)>2^((1-eps)*log(n)/log(log(n))). [with the base=e]

[preda]

Originally Posted by preda

sqrt(k) a "sup" approximation for numdiv(k)?

According to https://en.wikipedia.org/wiki/Divisor_function
it seems numdiv(k) grows like k^(log(2) / log(log(k))) in the limsup sense. (if I didn't mess something up)

[preda]

Originally Posted by R. Gerbicz

Yes, use a=2,b=1 sort the divisors of k in increasing order: d1=1<d2<...<d_u=k (if k has u divisors), then for any t it is true that 2^d_t-1 | 2^k-1, because d_t | k, but if d_t !=1,6 then with Zsigmondy theorem 2^d_t-1 has a new prime divisor, that doesn't divide 2^x-1 for every x<d_t. With this we'll have at least numdiv(k)-2 distinct prime divisors

Nice, thanks!

[chris2be8]

To maximize the number of algebraic factors of 2^k-1 make k twice a primorial, ie make k 2*2*3*5*7*11*13*... 2 occurs twice because 2^(4n+2)+1 has Aurifeuillian factors (2^(2n-1)-2^n+1) and (2^(2n-1)+2^n+1). Raising odd primes to a higher power will add some more factors but fewer than adding another prime.

Chris