mersenneforum.org  

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

Reply
 
Thread Tools
Old 2014-05-29, 11:50   #1
miket
 
May 2013

118 Posts
Default Can 1227133513 be the only composite number matching the conditions?

Conditions:

n such that O | n - 1 and O - 1 = 2^x , n āˆˆ 2N + 1, O = Ord_n(2), x āˆˆ Zā‰„0.

Can 1227133513 be the only composite number matching the conditions?

Erick Wong has check up to 10^20, see: Are there composite numbers matching the conditions?

More info of 1227133513: Ord_{1227133513}(2) = 33 and 33 | 2^33 - 1.
miket is offline   Reply With Quote
Old 2014-05-29, 12:46   #2
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

3·1,993 Posts
Default

I suspect he checked only to 2^64 using Jan's list.

Probably there are others but searching seems futile.
CRGreathouse is offline   Reply With Quote
Old 2014-05-29, 15:23   #3
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22·5·373 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
I suspect he checked only to 2^64 using Jan's list.

Probably there are others but searching seems futile.
On very rough probability grounds one might expect there to be
O(loglog N) examples up to N
R.D. Silverman is offline   Reply With Quote
Old 2014-05-29, 17:48   #4
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

3×1,993 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
On very rough probability grounds one might expect there to be
O(loglog N) examples up to N
Abusively assuming the big-O constant to be 1, the expected number of new examples up to 10^25 is 1/4. To get a 95% chance of finding and example you'd need to go above 10^385.
CRGreathouse is offline   Reply With Quote
Old 2014-05-29, 20:05   #5
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22×5×373 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
Abusively assuming the big-O constant to be 1, the expected number of new examples up to 10^25 is 1/4. To get a 95% chance of finding and example you'd need to go above 10^385.
The constant should be derivable, but offhand I am unsure how to
do it.
R.D. Silverman is offline   Reply With Quote
Old 2014-08-12, 00:41   #6
Rich
 
Apr 2011

10102 Posts
Default

Sorry, I must be confused because n = 601 * 1801 * 6151 = 6657848551 seems to work. This is the same order of magnitude as the other solution quoted so it's unlikely to have been missed. It's less than 1010 and certainly less than 1020 that Erick Wong is supposed to have checked to.
I claim that O = 1025 = 210 + 1 = 52 * 41
21025 = 1 mod n
21025 / 5 = 5533233944 mod n and 21025 / 41 = 33554432 (which seem to have more than their fair share of digit pairs 33, 44 and 55)
This proves that the order of 2 is 1025 as required.
Finally n = 1025 * 6495462 + 1 so O | n-1 as required.

The next solution seems to be 13857901601 = 6151 * 2252951 = 1025 * 13519904 + 1
21025 / 5 = 12903300634 mod 13857901601 (hmm.. more digit pairs)
while
21025 = 1 mod 13857901601
This proves the order of 2 is 1025 again while n-1 is of the required form.

I believe there are a total of 4079 solutions with O=1025 of which an impressive one (but by no means the largest) is n = 19858924506932274923192217121413840253555986701099656443876494287833804013531009915252291156116144835199447717419022262305584364955410801

Indeed shouldn't any product of the primes where 2 has the required order qualify as a composite of the required form? As the orders get larger, the number of primes with the required order increase as well.

Contrary to what Bob claims, I believe that when we start talking about numbers n where log(log(n)) is not small then these sorts of numbers are actually quite common.

Last fiddled with by Rich on 2014-08-12 at 00:52 Reason: Adding material
Rich is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Number Composite Astronomical M281414479 PaulineEinstein Lounge 27 2018-01-24 19:28
Largest number of LL tests before matching residues achieved? sdbardwick Lounge 1 2015-02-03 15:03
Fermat number F6=18446744073709551617 is a composite number. Proof. literka Factoring 5 2012-01-30 12:28
Please help me find a composite number (test2) allasc Math 0 2010-12-27 13:37
How long before you found your first composite number? Bundu Data 3 2004-08-14 12:21

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


Tue Oct 26 09:32:20 UTC 2021 up 95 days, 4:01, 0 users, load averages: 2.26, 2.03, 2.03

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.