|
%I #20 Aug 30 2017 04:09:30
%S 1,1,3,2,3,3,2,2,4,3,19,3,6,2,3,3,7,4,10,3,4,19,43,3,19,6,10,2,39,3,
%T 19,4,19,7,6,4,18,10,6,3,19,4,13,19,6,43,137,3,26,19,7,6,103,10,19,2,
%U 10,39,173,3,38,19,4,4,6,19,86,7,43,6,139,4,10,18,19,10,25,6,206,3,34,19,163
%N a(n) is the smallest k such that 2^psi(k) == 2^phi(n) (mod n).
%C Remainders when 2^phi(n) is divided by n are 0, 0, 1, 0, 1, 4, 1, 0, 1, 6, 1, 4, 1, 8, 1, 0, 1, 10, 1, 16, 1, 12, ... (i.e., the values of "1" come from Euler's totient theorem).
%C If n is odd, a(n) is the least k such that psi(k) is divisible by A002326((n-1)/2). - _Robert Israel_, Aug 29 2017
%e a(11) = 19 because 2^psi(19) == 2^phi(11) (mod 11) and 19 is the least number with this property.
%p N:= 1000: # to get terms before the first term > N
%p Psis:= Vector([$1..N]):
%p for p in select(isprime, [2,seq(i,i=3..N,2)]) do
%p pm:= p*[$1..N/p];
%p Psis[pm]:= map(`*`,Psis[pm],1+1/p);
%p od:
%p for n from 1 do
%p r:= 2 &^ numtheory:-phi(n) mod n;
%p for k from 1 to N do
%p if 2 &^ Psis[k] mod n = r then A[n]:= k; break fi
%p od:
%p if not assigned(A[n]) then break fi
%p od:
%p seq(A[i],i=1..n-1); # _Robert Israel_, Aug 29 2017
%t psi[n_] := If[n == 1, 1, n Times @@ (1 + 1/First /@ FactorInteger@ n)]; a[n_] := Block[{k = 1, v = PowerMod[2, EulerPhi[n], n]}, While[ PowerMod[2, psi[k], n] != v, k++]; k]; Array[a, 83] (* _Giovanni Resta_, Aug 30 2017 *)
%o (PARI) a001615(n) = my(f=factor(n)); prod(i=1, #f~, f[i, 1]^f[i, 2] + f[i, 1]^(f[i, 2]-1));
%o a(n) = {my(k=1); while (Mod(2, n)^a001615(k) != 2^eulerphi(n), k++); k; } \\ after _Charles R Greathouse IV_ at A001615
%Y Cf. A000010, A001615, A002326.
%K nonn
%O 1,3
%A _Altug Alkan_, Aug 29 2017
|
