mersenneforum.org > Math Why are numbers sum(2^(k*c)) smooth?
 Register FAQ Search Today's Posts Mark Forums Read

 2018-08-30, 04:50 #1 preda     "Mihai Preda" Apr 2015 32·151 Posts Why are numbers sum(2^(k*c)) smooth? 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?
2018-08-30, 05:03   #2
a1call

"Rashid Naimi"
Oct 2015
Remote to Here/There

2·1,009 Posts

Quote:
 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

Last fiddled with by a1call on 2018-08-30 at 05:16

2018-08-30, 06:14   #3
preda

"Mihai Preda"
Apr 2015

25178 Posts

Quote:
 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.

 2018-08-30, 06:46 #4 a1call     "Rashid Naimi" Oct 2015 Remote to Here/There 2×1,009 Posts 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. Last fiddled with by a1call on 2018-08-30 at 06:47
2018-08-30, 07:01   #5
Batalov

"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

2·3·1,571 Posts

Quote:
 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?

2018-08-30, 07:27   #6
preda

"Mihai Preda"
Apr 2015

32×151 Posts

Quote:
 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!

2018-08-30, 07:35   #7
Batalov

"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

2·3·1,571 Posts

Quote:
 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?"

Quote:
 Originally Posted by preda ... how are the factors affected?
Well the factors of 2^c-1 are taken away. There are still tons left.

2018-08-30, 07:35   #8
preda

"Mihai Preda"
Apr 2015

32·151 Posts

Quote:
 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?

2018-08-30, 08:16   #9
preda

"Mihai Preda"
Apr 2015

32·151 Posts

Quote:
 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.

Quote:
 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?

2018-08-30, 12:03   #10
preda

"Mihai Preda"
Apr 2015

32×151 Posts

Quote:
 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.

 2018-08-30, 15:17 #11 jcrombie     "Jonathan" Jul 2010 In a tangled web... 2×107 Posts This might be useful for playing around with.

 Similar Threads Thread Thread Starter Forum Replies Last Post Sam Kennedy Factoring 5 2012-11-10 07:54 Citrix Other Mathematical Topics 46 2012-03-06 14:55 CRGreathouse Math 3 2009-05-25 05:26 Citrix Math 9 2005-12-31 11:07 Yamato Math 1 2005-12-11 11:09

All times are UTC. The time now is 09:51.

Tue May 11 09:51:54 UTC 2021 up 33 days, 4:32, 1 user, load averages: 1.77, 1.54, 1.45

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.