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 10^{10} and certainly less than 10^{20} that Erick Wong is supposed to have checked to.
I claim that O = 1025 = 2^{10} + 1 = 5^{2} * 41
2^{1025} = 1 mod n
2^{1025 / 5} = 5533233944 mod n and 2^{1025 / 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  n1 as required.
The next solution seems to be 13857901601 = 6151 * 2252951 = 1025 * 13519904 + 1
2^{1025 / 5} = 12903300634 mod 13857901601 (hmm.. more digit pairs)
while
2^{1025} = 1 mod 13857901601
This proves the order of 2 is 1025 again while n1 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 20140812 at 00:52
Reason: Adding material
