mersenneforum.org > Math Can 1227133513 be the only composite number matching the conditions?
 Register FAQ Search Today's Posts Mark Forums Read

 2014-05-29, 11:50 #1 miket   May 2013 916 Posts 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.
 2014-05-29, 12:46 #2 CRGreathouse     Aug 2006 598710 Posts I suspect he checked only to 2^64 using Jan's list. Probably there are others but searching seems futile.
2014-05-29, 15:23   #3
R.D. Silverman

"Bob Silverman"
Nov 2003
North of Boston

165108 Posts

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

2014-05-29, 17:48   #4
CRGreathouse

Aug 2006

598710 Posts

Quote:
 Originally Posted by R.D. Silverman 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.

2014-05-29, 20:05   #5
R.D. Silverman

"Bob Silverman"
Nov 2003
North of Boston

1D4816 Posts

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

 2014-08-12, 00:41 #6 Rich   Apr 2011 A16 Posts 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

 Similar Threads Thread Thread Starter Forum Replies Last Post PaulineEinstein Lounge 27 2018-01-24 19:28 sdbardwick Lounge 1 2015-02-03 15:03 literka Factoring 5 2012-01-30 12:28 allasc Math 0 2010-12-27 13:37 Bundu Data 3 2004-08-14 12:21

All times are UTC. The time now is 16:02.

Sat Nov 26 16:02:41 UTC 2022 up 100 days, 13:31, 1 user, load averages: 1.05, 1.06, 1.00