mersenneforum.org  

Go Back   mersenneforum.org > Math Stuff > Other Mathematical Topics

Reply
 
Thread Tools
Old 2019-12-19, 17:31   #1
jshort
 
"James Short"
Mar 2019
Canada

17 Posts
Default How much smaller can "primitive" factors be?

When looking for "easy" to find integers  N that are forced to be congruent to 1 + k \cdot p where the congruence factor p is "as large as possible" compared to N, are the primitive factors of integers of the form 2^{m} + 1 where m is a "highly composite number", the best way to find these?

https://en.wikipedia.org/wiki/Highly_composite_number

PS: technical question here...….how can I combine a link (reference) into a text while I'm writing it, instead of just writing it at the bottom of my post?

Last fiddled with by jshort on 2019-12-19 at 17:45 Reason: edit
jshort is offline   Reply With Quote
Old 2019-12-19, 18:23   #2
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

746010 Posts
Default

Quote:
Originally Posted by jshort View Post
When looking for "easy" to find integers  N that are forced to be congruent to 1 + k \cdot p where the congruence factor p is "as large as possible" compared to N,
This last phrase is meaningless.

And I suggest you use standard mathematical quantifiers/notation/terminology.

Nor have you defined "easy". And your use of the variable "p" is just plain wrong. Primitive factors of 2^m+1 are 1 mod m. What do you think "p" is?


Quote:
are the primitive factors of integers of the form 2^{m} + 1 where m is a "highly composite number", the best way to find these?
Huh? You have not specified a "way to find these". In fact, you have not said
anything at all. What method did you have in mind? Saying that factors
are 1 mod m does not specify a method. Using words such as "easy", "best",
"as large as possible" is meaningless gibberish without quantifying them.

The current "best" technique for finding primitive factors consists of

(1) trial division by candidates of the form 1 + km for k < B; B is your choice depending on hardware and time constraints. Typically B = O(log^2 (2^m+1)) is
a good choice.

(1a) perhaps followed by P-1, if desired.

(2) Followed by ECM; choice of parameters depends on your goals and time constraints.

(3) Followed by NFS if time and resources permit.
R.D. Silverman is offline   Reply With Quote
Old 2019-12-19, 21:57   #3
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

1111001010112 Posts
Default

I'm not sure what you mean to be asking. Obviously, the smallest positive integer congruent to 1 modulo any positive integer modulus m is 1.

If you want integers whose prime factors are necessarily congruent to 1 modulo a given modulus, I repost a link to this paper which gives pertinent results about cyclotomic polynomials vis a vis "primitive factors."

If you're asking how small the value of, say, \Phi_{n}(2) can be compared to 2^{n} - 1 I don't know off hand.

If you're asking about cracking primitive parts into prime factors, I refer you to the previous response.
Dr Sardonicus is offline   Reply With Quote
Old 2019-12-20, 15:13   #4
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

11·353 Posts
Default

Quote:
Originally Posted by Dr Sardonicus View Post
<snip>
If you're asking how small the value of, say, \Phi_{n}(2) can be compared to 2^{n} - 1 I don't know off hand.
After a bit of quiet reflection on the well-known formula

\Phi_{n}(x)\;=\;\prod_{d\mid n}(x^{d} \; - \; 1)^{\mu(\frac{n}{d})}

I noticed that substituting x = 2 and doing a bit of rearranging gives the crude but obvious bounds

K\cdot 2^{\varphi(n)} \; \le \; \Phi_{n}(2) \; \le \frac{1}{K}\cdot 2^{\varphi(n)}\text{ where}

K \; = \; \prod_{i=1}^{\infty}(1 \; - \; 2^{-i})

K = 0.288788+, and 1/K = 3.4627466+

Substituting x = a for a > 2 gives similar bounds.
Dr Sardonicus is offline   Reply With Quote
Old 2019-12-21, 06:51   #5
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

5,939 Posts
Default

Quote:
Originally Posted by Dr Sardonicus View Post
K \; = \; \prod_{i=1}^{\infty}(1 \; - \; 2^{-i})

K = 0.288788+, and 1/K = 3.4627466+
See A048651 and A065446 for those constants in the OEIS.
CRGreathouse is online now   Reply With Quote
Old 2019-12-21, 16:19   #6
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

11×353 Posts
Default

I find the function

F(z) \; = \; \prod_{i=1}^{\infty}(1 \; - \; z^{i})\text{, }|z|\;<\; 1

far more interesting than the decimal digits of its evaluation at a particular value of z. I note that

zF^{24}(z)

is the generating function for Ramanujan's tau function.

I also note that, using the above estimate, the question of how much smaller a primitive part of 2n - 1 can be than 2n is reduced to the question of how small \varphi(n) can be as a function of n. The best you can do here is taking n to be the product of the first umpteen primes, when

\varphi(n) \; \sim \; \frac{ne^{-\gamma}}{\log\log n}
Dr Sardonicus is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Aouessare-El Haddouchi-Essaaidi "test": "if Mp has no factor, it is prime!" wildrabbitt Miscellaneous Math 11 2015-03-06 08:17
"factors.txt.u1conflict..." files Flatlander Linux 3 2011-02-21 02:32
"On factors of Mersenne numbers" - Seiji Tomita cheesehead Math 6 2009-12-15 17:45
Would Minimizing "iterations between results file" may reveal "is not prime" earlier? nitai1999 Software 7 2004-08-26 18:12

All times are UTC. The time now is 04:29.

Wed Dec 2 04:29:02 UTC 2020 up 83 days, 1:40, 1 user, load averages: 2.53, 2.47, 2.37

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, 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.