1
$\begingroup$

A Poulet-number is a composite positive integer $\ N>1\ $ satisfying the condition $$2^{N-1}\equiv 1\mod N$$ The numbers $$10^{16}+8\ 663\ 854\ 653$$ and $$10^{17}+209\ 045\ 665\ 633$$ are Poulet-numbers.

Are the numbers the smallest Poulet-numbers above $10^{16}$ and $10^{17}$ respectively ?

How can I search the smallest Poulet number above a given number efficiently ?

$\endgroup$
2
  • $\begingroup$ Are you looking for a code that does it? ${}{}{}{}$ $\endgroup$
    – Ahmed S. Attaalla
    Commented Sep 4, 2018 at 21:43
  • $\begingroup$ @AhmedS.Attaalla Yes, but not a code using brute force. The algorithm should be considerably faster (if such an algorithm is known/actually exists). $\endgroup$
    – Peter
    Commented Sep 4, 2018 at 21:45

1 Answer 1

Reset to default
3
$\begingroup$

A tabulation of all the Poulet numbers less than $2^{64}(\approx1.8447\times10^{19})$ can be found here. There we find that the answer to your first question is no:

Your number $10^{16}+\hbox{8 663 854 653}$ is the third Poulet number beyond $10^{16}$; the first two are $10^{16}$ plus $\hbox{6 286 491 369}$ and $\hbox{8 250 001 701}$, respectively.

And your Poulet number $10^{17}+\hbox{209 045 665 633}$ is in fact the eighth Poulet number beyond $10^{17}$. The first seven are $$10^{17}+(10\ 102\ 756\ 401, 56\ 076\ 920\ 001,116\ 526\ 957\ 249,139\ 941\ 938\ 721,150\ 553\ 089\ 531, 157\ 387\ 600\ 201, \rm{and}\ 174\ 032\ 555\ 661),$$ respectively.

$\endgroup$
2
  • $\begingroup$ I did not expect that the list of Poulet-numbers upto $2^{64}$ has actually been published. (+1) $\endgroup$
    – Peter
    Commented Sep 7, 2018 at 9:04
  • $\begingroup$ Were you able to download and make use of the tabular data? The data files are rather large; for my own use I downloaded and converted to native binary format on my computer, so that I could load and search more efficiently. Not sure if you've explored completely Jan Feitsma's website: you might find the table of Poulet no, summary statistics (janfeitsma.nl/math/psp2/statistics) to be particularly useful. $\endgroup$
    – user15994
    Commented Sep 7, 2018 at 20:51

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .