A232616 Least positive integer m such that {2^k - k: k = 1,...,m} contains a complete system of residues modulo n.

1, 2, 4, 5, 10, 6, 14, 10, 12, 18, 29, 13, 33, 22, 40, 19, 38, 18, 58, 21, 36, 58, 75, 26, 60, 66, 40, 64, 195, 53, 87, 36, 158, 67, 130, 37, 133, 94, 90, 42, 95, 42, 105, 112, 112, 140, 247, 51, 122, 94, 119, 120, 311, 54, 126, 90, 184, 223, 264, 61

Offset: 1

Author

Zhi-Wei Sun, Nov 26 2013

Keywords

• nonn

Comments

By a result of the author (see arXiv:1312.1166), for any integers a and n > 0, the set {a^k - k: k = 1, ..., n^2} contains a complete system of residues modulo n. (We may also replace a^k - k by a^k + k.) Thus a(n) always exists and it does not exceed n^2.

Conjectures:

(i) a(n) < 2*(prime(n)-1) for all n > 0.

(ii) The Diophantine equation x^n - n = y^m with m, n, x, y > 1 only has two integral solutions: 2^5 - 5 = 3^3 and 2^7 - 7 = 11^2. Also, the Diophantine equation x^n + n = y^m with m, n, x, y > 1 only has two integral solutions: 5^2 + 2 = 3^3 and 5^3 + 3 = 2^7.

Examples

			a(3) = 4 since {2 - 1, 2^2 - 2, 2^3 - 3} = {1, 2, 5} does not contain a complete system of residues mod 3, but {2 - 1, 2^2 - 2, 2^3 - 3, 2^4 - 4} = {1, 2, 5, 12} does.
		

Links

• Chai Wah Wu, Table of n, a(n) for n = 1..10000 (n = 1..700 from Zhi-Wei Sun)
• Zhi-Wei Sun, On a^n + b*n modulo m, preprint, arXiv:1312.1166 [math.NT], 2013-2014.

Crossrefs

Cf. A000079, A000325, A231201, A231725, A232398, A232548, A232862.

Programs

Mathematica

L[m_,n_]:=Length[Union[Table[Mod[2^k-k,n],{k,1,m}]]]
Do[Do[If[L[m,n]==n,Print[n," ",m];Goto[aa]],{m,1,n^2}];
Print[n," ",0];Label[aa];Continue,{n,1,60}]