mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2018-08-30, 04:50   #1
preda
 
preda's Avatar
 
"Mihai Preda"
Apr 2015

32·151 Posts
Default 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?
preda is offline   Reply With Quote
Old 2018-08-30, 05:03   #2
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

2·1,009 Posts
Default

Quote:
Originally Posted by preda View Post
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
a1call is offline   Reply With Quote
Old 2018-08-30, 06:14   #3
preda
 
preda's Avatar
 
"Mihai Preda"
Apr 2015

25178 Posts
Default

Quote:
Originally Posted by a1call View Post
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.
preda is offline   Reply With Quote
Old 2018-08-30, 06:46   #4
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

2×1,009 Posts
Default

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
a1call is offline   Reply With Quote
Old 2018-08-30, 07:01   #5
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

2·3·1,571 Posts
Default

Quote:
Originally Posted by preda View Post
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?
Batalov is offline   Reply With Quote
Old 2018-08-30, 07:27   #6
preda
 
preda's Avatar
 
"Mihai Preda"
Apr 2015

32×151 Posts
Default

Quote:
Originally Posted by Batalov View Post
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!
preda is offline   Reply With Quote
Old 2018-08-30, 07:35   #7
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

2·3·1,571 Posts
Default

Quote:
Originally Posted by preda View Post
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 View Post
... how are the factors affected?
Well the factors of 2^c-1 are taken away. There are still tons left.
Batalov is offline   Reply With Quote
Old 2018-08-30, 07:35   #8
preda
 
preda's Avatar
 
"Mihai Preda"
Apr 2015

32·151 Posts
Default

Quote:
Originally Posted by a1call View Post
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 is offline   Reply With Quote
Old 2018-08-30, 08:16   #9
preda
 
preda's Avatar
 
"Mihai Preda"
Apr 2015

32·151 Posts
Default

Quote:
Originally Posted by Batalov View Post
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?
preda is offline   Reply With Quote
Old 2018-08-30, 12:03   #10
preda
 
preda's Avatar
 
"Mihai Preda"
Apr 2015

32×151 Posts
Default

Quote:
Originally Posted by preda View Post
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.
preda is offline   Reply With Quote
Old 2018-08-30, 15:17   #11
jcrombie
 
jcrombie's Avatar
 
"Jonathan"
Jul 2010
In a tangled web...

2×107 Posts
Default

This might be useful for playing around with.
jcrombie is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Not smooth enough numbers Sam Kennedy Factoring 5 2012-11-10 07:54
Special Smooth numbers Citrix Other Mathematical Topics 46 2012-03-06 14:55
Smooth and rough numbers CRGreathouse Math 3 2009-05-25 05:26
Finding smooth numbers Citrix Math 9 2005-12-31 11:07
Smooth Numbers 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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

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.