[seqfan] Re: n = number of divisors of 2^n -1

[Charles Greathouse]

> I don't understand your argument.
> n = 2^k is in this sequence, if in particular 2^n - 1 is the product
> of k distinct prime factors.

2^(2^n)) - 1 divides 2^(2^(n+1)) - 1.  2^64-1 has too many prime
factors.  Higher powers add on at least one new prime at each level,
so the number of divisors will always exceed the exponent at or beyond
exponent 64.

> How did you do that without knowing factorization of numbers 2^m + 1
> for large m (for example, the complete factorization of 2^2881 + 1 is
> currently unknown, according to Cunningham tables) ?

You don't need the full factorization.  2^11524 - 1 (was this what you
were referring to when you mentioned 2^2881 + 1?) is divisible by 3^1,
5^1, and 173^1 (but not by 3^2, 5^2, or 173^2), so its number of
divisors is (1 + 1)(1 +1)(1 + 1) * unknown = 8 * unknown.  But 11524
is not divisible by 8, so 11524 is not in the sequence.

And it's not hard to find small divisors of large numbers when they're
close to a power.  You don't need to work with the large number
itself, just work mod the appropriate prime.

Charles Greathouse
Analyst/Programmer
Case Western Reserve University



On Wed, Apr 21, 2010 at 9:47 PM, Max Alekseyev <maxale at gmail.com> wrote:
> On Wed, Apr 21, 2010 at 4:01 PM, Charles Greathouse
> <charles.greathouse at case.edu> wrote:
>> Well, 32 is the last power of two in the sequence since
>> (2^64-1)/(2^32-1) = 641 * 6700417 is composite.
>
> I don't understand your argument.
> n = 2^k is in this sequence, if in particular 2^n - 1 is the product
> of k distinct prime factors.
>
>> Otherwise, I checked up to 16384 without finding any members.
>
> How did you do that without knowing factorization of numbers 2^m + 1
> for large m (for example, the complete factorization of 2^2881 + 1 is
> currently unknown, according to Cunningham tables) ?
>
> Regards,
> Max
>
>
> _______________________________________________
>
> Seqfan Mailing list - http://list.seqfan.eu/
>