2^n mod n = e
Joe Crump
joecr at microsoft.com
Fri Jun 11 23:49:32 CEST 1999
The online integer encyclopedia contains several sequences
of 2^n mod n.
http://www.research.att.com/~njas/sequences/index.html
In particular, the info Richard Guy pointed out is in:
http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?An
um=036236
----------------------------------------------------------------------------
--------------------
ID Number: A036236
Sequence:
3,4700063497,6,19147,10669,25,9,2228071,18,262279,3763,95,1010,481,20,
45,35,2873,2951,3175999,42,555,50,95921,27,174934013,36,777,49,140039,
56
Name: a(n) = least k with 2^k mod k = n (inverse of A015910).
Comments: No n exists with 2^n mod n = 1. a(3) first computed by Lehmers.
References R. K. Guy, Unsolved Problems in Number Theory, Section F10.
See also: Cf. A015910, A036237.
Keywords: hard,nonn,nice
Offset: 2
Author(s): David Wilson (wilson at ctron.com)
Extension: a(33) <= 319020450922208555, per Dean Hickerson
----------------------------------------------------------------------------
--------------------
I've added a few in the past, such as 2^n mod n = 7, 11, 15. But,
they
don't go very far (just ran a brute-force app for a few hours)...
http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?An
um=033981
http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?An
um=033982
http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?An
um=033983
Are there any decent algorithms, or helpful tricks for finding
solutions 'n' to
2^n mod n = e, where 'e' very small, say e <= 31? Or have these numbers
already
been computed and collected somewhere?
Thanks!
- Joe
-----Original Message-----
From: Richard Guy [mailto:rkg at cpsc.ucalgary.ca]
Sent: Thursday, June 10, 1999 8:49 PM
To: NMBRTHRY at LISTSERV.NODAK.EDU
Subject: Re: n|[(2^n)-3] ; Ron Graham ...
There was some email about this recently, from a different enquirer, I
think. F10 (p.250 of 2nd edition) of UPINT [Unsolved Problems in
Number Theory, by Guy:ed.] states that the Lehmers have shown that the
smallest solution of 2^n = 3 mod n is n=470063497=19*47*5263229.
Graham had asked the Lehmers to look for a solution. In a sense they
were lucky, as they planned to go only to half a billion. At the time
there were those who thought that there might not be a solution. I
don't know of another, and would be interested to learn if one is
found. It may be that this is the only place that the result is
published. R.
More information about the SeqFan
mailing list