cp's OEIS Frontend

A247248 a(n) is the least k such that n divides 2^k + k.

%I A247248 #43 May 22 2025 10:21:40
%S A247248 1,2,1,4,4,2,6,8,7,4,3,8,12,6,7,16,16,14,18,4,19,8,22,8,33,12,7,40,11,
%T A247248 26,23,32,8,16,6,32,5,18,37,24,40,38,42,8,7,22,10,32,61,84,38,12,35,
%U A247248 32,46,40,32,28,24,44,17,30,61,64,66,8,66,16,67,6,11,32
%N A247248 a(n) is the least k such that n divides 2^k + k.
%C A247248 For every positive integer n, there exists an integer k such that 2^k + k is divisible by n. The proof is given in the link, p. 63.
%H A247248 Chai Wah Wu, <a href="/A247248/b247248.txt">Table of n, a(n) for n = 1..10000</a>
%H A247248 International Mathematical Olympiad, <a href="http://www.imo-official.org/problems/IMO2006SL.pdf">Problem N7</a>, IMO-2006, p. 63.
%e A247248 a(7) = 6 because 2^6 + 6 = 70 is divisible by 7.
%p A247248 f:= proc(n) local k;
%p A247248 for k from 1 do
%p A247248   if 2^k + k mod n = 0 then return k fi
%p A247248 od
%p A247248 end proc:
%p A247248 seq(f(n), n=1..100); # _Robert Israel_, Dec 01 2014
%t A247248 Table[s=0; k=0; While[k++; s=Mod[2^k+k, n]; s>0]; k, {n, 50}]
%t A247248 lk[n_]:=Module[{k=1},While[Mod[2^k+k,n]!=0,k++];k]; Array[lk,120] (* _Harvey P. Dale_, Jun 18 2022 *)
%o A247248 (Python)
%o A247248 def A247248(n):
%o A247248     if n == 1:
%o A247248         return 1
%o A247248     else:
%o A247248         x, k, kr = 1,0,0
%o A247248         while (x+kr) % n:
%o A247248             x, kr = (2*x) % n, (kr+1) % n
%o A247248             k += 1
%o A247248         return k
%o A247248 # _Chai Wah Wu_, Dec 03 2014
%o A247248 (PARI) a(n) = for(m=1, oo, if(Mod(2, n)^m==-m, return(m))); \\ _Jinyuan Wang_, Mar 15 2020
%Y A247248 Cf. A135366, A006127 (2^n+n).
%K A247248 nonn
%O A247248 1,2
%A A247248 _Michel Lagneau_, Dec 01 2014