factors of 2^k - 1
 

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

[QUOTE=preda;495095]f(k) = number of [prime] factors of 2^k - 1

Can somebody please help me analyze how f(k) depends on k?
[/QUOTE]

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

[QUOTE=R. Gerbicz;495097]Use [url]https://en.wikipedia.org/wiki/Zsigmondy%27s_theorem[/url] !!!
With that f(k)>=numdiv(k)-2.[/QUOTE]
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 [url]https://en.wikipedia.org/wiki/Big_O_notation[/url] )

[QUOTE=preda;495101]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)?
[/QUOTE]

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

[QUOTE=preda;495101]
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)?
[/QUOTE]

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 [url]https://en.wikipedia.org/wiki/Divisor_function[/url], 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]

[QUOTE=preda;495101] sqrt(k) a "sup" approximation for numdiv(k)?[/QUOTE]

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

[QUOTE=R. Gerbicz;495103]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[/QUOTE]
Nice, thanks!

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