A276976 - OEIS

%I #96 Jun 03 2022 12:59:59

%S 0,1,1,2,1,2,1,4,3,2,1,2,1,2,3,4,1,6,1,4,3,2,1,4,5,2,9,4,1,2,1,8,3,2,

%T 11,6,1,2,3,4,1,6,1,4,9,2,1,4,7,10,3,4,1,18,15,8,3,2,1,4,1,2,3,16,5,6,

%U 1,4,3,10,1,6,1,2,15,4,17,6,1,4,27,2,1

%N Smallest m such that b^m == b^n (mod n) for every integer b.

%C It suffices to check all bases 0 < b < n for n > 2.

%C The congruence n == a(n) (mod A002322(n)) is always true.

%C a(n) = 1 iff n is a prime or a Carmichael number.

%C We have a(n) > 0 for n > 1, and a(n) <= n/2.

%C If n > 2 then a(n) is odd iff n is odd.

%C Conjecture: a(n) <= n/3 for every n >= 9.

%C Professor Andrzej Schinzel proved this conjecture (in a letter to the author). - _Thomas Ordowski_, Sep 30 2016

%C Note: a(n) = n/3 for n = A038754 >= 3.

%C Numbers n such that a(n) > A270096(n) are A290960.

%C Information from Carl Pomerance: a(n) > A002322(n) if and only if 8|n and n is in A050990; such n = 8, 24, 56, ... - _Thomas Ordowski_, Jun 21 2017

%C Number of integers k < n such that b^k == b^n (mod n) for every integer b is f(n) = (n - a(n))/lambda(n). For n > 1, f(n) = floor((n-1)/lambda(n)) if and only if a(n) <= lambda(n), where lambda(n) = A002322(n). - _Thomas Ordowski_, Jun 21 2017

%C a(n) >= A051903(n); numbers n such that a(n) = A051903(n) are 1, primes, Carmichael numbers, and A327295. - _Thomas Ordowski_, Dec 06 2019

%H Charles R Greathouse IV, <a href="/A276976/b276976.txt">Table of n, a(n) for n = 1..10000</a>

%F a(p) = 1 for prime p.

%F a(2*p) = 2 for prime p.

%F a(3*p) = 3 for odd prime p.

%F a(p^k) = p^(k-1) for odd prime p and k >= 1.

%F a(2*p^k) = 2*p^(k-1) for odd prime p and k >= 1.

%F a(2^k) = 2^(k-2) for k >= 4.

%F From _Thomas Ordowski_, Jul 09 2017: (Start)

%F Full description of the function:

%F a(n) = lambda(n) if lambda(n)|n except n = 1, 8, and 24;

%F a(n) = lambda(n)+2 if lambda(n)|(n-2) and 8|n;

%F a(n) = n mod lambda(n) otherwise;

%F where lambda(n) = A002322(n). (End)

%F For n <> 8 and 24, a(n) = A(n) if A(n) >= A051903(n) or a(n) = A002322(n) + A(n) otherwise, where A(n) = A219175(n). - _Thomas Ordowski_, Nov 30 2019

%t With[{nn = 83}, Table[SelectFirst[Range[nn/4 + 10], Function[m, AllTrue[Range[2, n - 1], PowerMod[#, m , n] == PowerMod[#, n , n] &]]] - Boole[n == 1], {n, nn}]] (* _Michael De Vlieger_, Aug 15 2017 *)

%t a[1] = 0; a[8] = a[24] = 4; a[n_] := If[(rem = Mod[n, (lam = CarmichaelLambda[n])]) >= Max @@ Last /@ FactorInteger[n], rem, rem + lam]; Array[a, 100] (* _Amiram Eldar_, Nov 30 2019 *)

%o (PARI) a(n)=if(n<3, return(n-1)); forstep(m=1,n,n%2+1, for(b=0,n-1, if(Mod(b,n)^m-Mod(b,n)^n, next(2))); return(m)) \\ _Charles R Greathouse IV_, Sep 23 2016

%o (Python) def a(n): return next(m for m in range(0, n+1) if all(pow(b,m,n)==pow(b,n,n) for b in range(1, 2*n+1))) # _Nicholas Stefan Georgescu_, Jun 03 2022

%Y Cf. A002322, A002997, A038754, A050990, A051903, A124240, A219175, A270096, A290960, A327295.

%K nonn,nice

%O 1,4

%A _Thomas Ordowski_, Sep 23 2016

%E More terms from _Altug Alkan_, Sep 23 2016