Are all counterexamples of OEIS A226181 both Poulet numbers and Proth numbers?

Question

OEIS A226181:

3, 5, 7, 11, 13, 17, 19, 23, 29, 37, 41, 47, 53, 59, 61, 67, 71, 73, 79,  
83, 89, 97, 101, 103, 107, 113, 131, 137, 139, 149, 163, ...

Primes $p$ such that $p-1$ divided by the period of the binary expansion of $1/p$ equals $2^x$ for some nonnegative integer $x$. Composite numbers matching the conditions below $10^8$ are:

 12801, 348161, 3225601  

Poulet $n$. and Proth $n$. :

Poulet $n$.: A composite $n$ such that $2^n - 2$ is divisible by $n$.

Proth $n$.: A number of the form $k \cdot 2^n + 1$, with $k$ odd, $n > 0$, and $2^n > k$.

First numbers that belong to both sets:

1729, 4033, 8321, 12801, 65281, 130561, 348161, 3225601, 8355841,
8384513, 16773121, 40280065, 104988673, 2147418113,
4294901761, 4294967297, 53282340865, 68719214593, 137439477761.

Here's the question: are all counterexamples of OEIS A226181 both Poulet numbers and Proth numbers?

Answer 1

Let's first show that the numbers in the sequence are Poulet numbers. It is known that the length of the period of the binary expansion of $\frac{1}{n}$ is $ord_n 2$, the multiplicative order of $2 \pmod n$. So let $n$ be a composite number such that $\frac{n-1}{ord_n 2}=2^x$. Then $n$ is odd. Therefore, $2^n\equiv 2 \pmod n$ if and only if $2^{n-1}\equiv 1 \pmod n$ if and only if $ord_n 2\mid n-1$, which holds by assumprtion, so $n$ is a Poulet number.

I think the condition for Proth numbers should be $2^n>k$ instead of $2n>k$ (see the Wikipedia article), so I will use that definition. If $\frac{n-1}{ord_n 2}=2^x$, then $n=(ord_n 2)\cdot 2^x+1$. If $ord_n 2$ is odd, $n$ is a Proth number if and only if $2^x>ord_n 2$. Hence if $n$ is a Proth number and $ord_n 2$ is odd, we have $ord_n 2<\sqrt{n-1}$, so the order of $2\pmod n$ is very small compared to how large it could be; it could be close to $\varphi(n)$ at least if $n$ has few prime factors, and it holds that $\varphi(n)\gg\frac{n}{\log \log n}$. For that reason I suspect that there is an $n$ such that $n$ satisfies the condition but is not a Proth number (but I have no hard evidence now).

Answer 2

The answer is no, they aren't necessarily Proth numbers.

Consider $$n=7816642561=7\times 13\times 5581\times 15391 = 238545\times 2^{15}+1$$ for which we have $\mathrm{ord}_{n}(2)=954180 = (n-1)/2^{13}$. Another counterexample would be $$m = 49413980161=7\times 13\times 4231\times 128341 = 1507995\times 2^{15}+1$$ which gives us $\mathrm{ord}_m(2) = 6031980 = (m-1)/2^{13}$.

I'm fairly sure that $n$ is the least counterexample to your conjecture. The other number might not be the second-smallest one, though; my search was not exhaustive over the extended range.