Why are numbers sum(2^(k*c)) smooth?

[preda]

I made this experimental observation, that numbers of the form:

2^(0*c) + 2^(1*c) + 2^(2c) + ... + 2^(k*c) are smooth. (by this I mean that the largest factor in their factorization is very small; they also have many factors).

Somebody can explain me why?

[a1call]

Originally Posted by preda

I made this experimental observation, that numbers of the form:

2^(0*c) + 2^(1*c) + 2^(2c) + ... + 2^(k*c) are smooth. (by this I mean that the largest factor in their factorization is very small; they also have many factors).

Somebody can explain me why?

My 2 cents:
In its simplest form for c=1, every consecutive-consecutive double pair are coprime.
Summing up bunch of coprimes will result in a number of small factors, but could also include some very large prime factors.
For c>1, you end up with multiples of the simplest form c= 1.

ETA One important variable which makes a great difference is if the total number of addend terms is odd or even.
See below for a parallel.
http://www.mersenneforum.org/showpos...19&postcount=9

[preda]

Originally Posted by a1call

My 2 cents:
In its simplest form for c=1, every consecutive-consecutive double pair are coprime.
Summing up bunch of coprimes will result in a number of small factors, but could also include some very large prime factors.
For c>1, you end up with multiples of the simplest form c= 1.

ETA One important variable which makes a great difference is if the total number of addend terms is odd or even.
See below for a parallel.
http://www.mersenneforum.org/showpos...19&postcount=9

I don't really understand your explanation.. maybe a bit slower for me.

But I did test the odd/even hypothesis; in pari-gp (which I barely know):
f(c,n)=for(m=1,n,print(#factor(sum(k=0,m,2^(k*c)))[,1]))

f(10, 16)
2
4
4
4
9
6
6
9
9
9
13
6
12
11
9
4

? f(15, 16)
3
3
8
4
8
8
12
7
10
7
18
5
18
11
18
8

? f(20, 16)
2
7
4
8
11
10
7
17
14
13
17
13
14
22
11
12

Thus I don't see much support for odd/even.

[a1call]

Try it with s primorial initial valve and add your terms to it.
This will exaggerate the effect.
I predict you should see a frequency of 4 cycles.

[Batalov]

Originally Posted by preda

2^(0*c) + 2^(1*c) + 2^(2c) + ... + 2^(k*c) are ...


Somebody can explain me why?

Why is \({2^{c(k+1)} - 1} \over {2^c - 1}\) smooth?
Is it because \({2^{c(k+1)} - 1}\) has tons of algebraic factors, maybe? Someone played paper darts too much in the 8th grade math class?

[preda]

Originally Posted by Batalov

Why is \({2^{c(k+1)} - 1} \over {2^c - 1}\) smooth?
Is it because \({2^{c(k+1)} - 1}\) has tons of algebraic factors, maybe? Someone played paper darts too much in the 8th grade math class?

Now I see the error of my ways :)

But what happens when 2^c - 1 does not divide \(2^{c(k+1)} - 1\), how are the factors affected?

In which situation is the number of factors maximized -- e.g. is it good for k+1 to be a power of 2? is it good or bad for c to be even? or c to be a power of 2?

Thanks!

[Batalov]

Originally Posted by preda

But what happens when 2^c - 1 does not divide \(2^{c(k+1)} - 1\), ...

That's not possible. This is like asking "at what length of a string of 9s, the number 999999999...99999999 is not divisible by 9?"

Originally Posted by preda

... how are the factors affected?

Well the factors of 2^c-1 are taken away. There are still tons left.

[preda]

Originally Posted by a1call

Try it with s primorial initial valve and add your terms to it.
This will exaggerate the effect.
I predict you should see a frequency of 4 cycles.

Are you saying that adding a primorial to the sum() would increase the number of factors? -- why?

[preda]

Originally Posted by Batalov

That's not possible. This is like asking "at what length of a string of 9s, the number 999999999...99999999 is not divisible by 9?"

sorry, that was a silly question.

Well the factors of 2^c-1 are taken away. There are still tons left.

Do you know which conditions (on k and c) would tend to maximize the number of factors left?

[preda]

Originally Posted by preda

Do you know which conditions (on k and c) would tend to maximize the number of factors left?

I'll attempt a rough analysis of the number of factors of

N(c, k) = sum(i=0, k, 2^(c*i)) == (2^(c*(k+1)) - 1) / (2^c - 1)

When k == 2^p - 1, then:

N(c, k) == prod(i=0, p-1, 2^(c * 2^i) + 1)

Let's take an example,
N(c, 7) = (2^(8c) - 1)/(2^c - 1) = (2^c + 1) * (2^(2c) + 1) * (2^(4c) + 1)

So the number of factors of N(c, k) is the sum of the nb. of factors of 2^(c*2^i) + 1, with i from 0 to log2(k). This may turn out to be O(log(k)^2), and seems to be larger for highly composite c.

Also, I confirm that indeed the number of factors of N(c, k) seems to be larger for odd k than for even k.

[jcrombie]

This might be useful for playing around with.