mersenneforum.org How much smaller can "primitive" factors be?
 Register FAQ Search Today's Posts Mark Forums Read

 2019-12-19, 17:31 #1 jshort   "James Short" Mar 2019 Canada 2·32 Posts 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
2019-12-19, 18:23   #2
R.D. Silverman

"Bob Silverman"
Nov 2003
North of Boston

1D8616 Posts

Quote:
 Originally Posted by jshort 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.

 2019-12-19, 21:57 #3 Dr Sardonicus     Feb 2017 Nowhere 2·32·5·71 Posts 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.
2019-12-20, 15:13   #4
Dr Sardonicus

Feb 2017
Nowhere

18F616 Posts

Quote:
 Originally Posted by Dr Sardonicus 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.

2019-12-21, 06:51   #5
CRGreathouse

Aug 2006

598810 Posts

Quote:
 Originally Posted by Dr Sardonicus $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.

 2019-12-21, 16:19 #6 Dr Sardonicus     Feb 2017 Nowhere 2·32·5·71 Posts 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}$

 Similar Threads Thread Thread Starter Forum Replies Last Post wildrabbitt Miscellaneous Math 11 2015-03-06 08:17 Flatlander Linux 3 2011-02-21 02:32 cheesehead Math 6 2009-12-15 17:45 nitai1999 Software 7 2004-08-26 18:12

All times are UTC. The time now is 14:07.

Thu Jun 8 14:07:34 UTC 2023 up 294 days, 11:36, 0 users, load averages: 2.36, 1.93, 1.54