A290543 -id:A290543 - cp's OEIS frontend

A290542 a(n) is the least integer k in the interval [2, sqrt(n)] such that k^n == k (mod n), or 0 if no such integer exists.

0, 2, 0, 2, 0, 0, 0, 2, 0, 2, 0, 0, 0, 2, 0, 2, 0, 0, 0, 2, 0, 0, 0, 0, 4, 2, 0, 2, 0, 0, 0, 0, 0, 2, 0, 0, 0, 2, 0, 2, 0, 0, 0, 2, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 2, 0, 2, 0, 0, 0, 5, 3, 2, 0, 0, 0, 2, 0, 2, 0, 0, 0, 0, 0, 2, 0, 0, 0, 2, 0, 4, 0, 0, 0, 2, 0

Offset: 4

Arkadiusz Wesolowski, Aug 05 2017

nonn

Antti Karttunen, Table of n, a(n) for n = 4..20000

Cf. A010051, A290543.

lst:=[]; for n in [4..90] do r:=Floor(Sqrt(n)); for k in [2..r] do if Modexp(k, n, n) eq k then Append(~lst, k); break; end if; if k eq r then Append(~lst, 0); end if; end for; end for; lst;

Table[SelectFirst[Range[2, Sqrt@ n], PowerMod[#, n , n] == Mod[#, n] &] /. k_ /; MissingQ@ k -> 0, {n, 4, 90}] (* Michael De Vlieger, Aug 09 2017 *)

a(n) = for (k=2, sqrtint(n), if (Mod(k, n)^n == k, return(k));); return (0); \\ Michel Marcus, Aug 19 2017

a(A000040(n)) = 2 for n >= 3.
a(A001567(n)) = 2 for n >= 1.
a(A006935(n)) = 2 for n >= 2.
For n >= 3, a(x) = 2*A010051(x), where x = A000040(n).

A290812 Odd composite numbers m such that k^(m - 1) == 1 (mod m) and gcd(k^((m - 1)/2) - 1, m) = 1 for some integer k in the interval [2, sqrt(m) + 1].

Original entry on oeis.org

91, 247, 325, 343, 485, 703, 871, 901, 931, 949, 1099, 1111, 1157, 1247, 1261, 1271, 1387, 1445, 1525, 1649, 1765, 1807, 1891, 1975, 2047, 2059, 2071, 2117, 2501, 2701, 2863, 2871, 3277, 3281, 3365, 3589, 3845, 4069, 4141, 4187, 4291, 4371, 4411, 4525

Offset: 1

Arkadiusz Wesolowski, Aug 11 2017

nonn

If the condition "odd composite numbers" in the definition is replaced by "odd numbers", then every odd prime number is in the sequence.

This is not a subsequence of A290543 (for example, 65683 is missing in A290543).

			91 is in the sequence because:
1) it is an odd composite number.
2) k^90 == 1 (mod 91) and gcd(k^45 - 1, 91) = 1 with k = 10 < sqrt(91) + 1.

Giovanni Resta, Table of n, a(n) for n = 1..10000 (first 1000 terms from A. Wesolowski)
Wikipedia, Pocklington primality test.
Index entries for sequences related to pseudoprimes.

Cf. A130569, A290543.

lst:=[]; for n in [3..4525 by 2] do if not IsPrime(n) then for a in [2..Floor(Sqrt(n)+1)] do if Modexp(a, n-1, n) eq 1 and GCD(a^Truncate((n-1)/2)-1, n) eq 1 then Append(~lst, n); break; end if; end for; end if; end for; lst;

Select[Range[3, 4525, 2], Function[n, And[CompositeQ@ n, AnyTrue[Range[2, Sqrt[n] + 1], And[PowerMod[#, n - 1, n] == 1, CoprimeQ[#^((n - 1)/2) - 1, n]] &]]]] (* Michael De Vlieger, Aug 16 2017 *)

is(n) = if(n > 1 && n%2==1 && !ispseudoprime(n), for(x=2, sqrt(n)+1, if(Mod(x, n)^(n-1)==1 && gcd(x^((n-1)/2)-1, n)==1, return(1)))); 0 \\ Felix Fröhlich, Aug 18 2017

cp's OEIS Frontend

A290542 a(n) is the least integer k in the interval [2, sqrt(n)] such that k^n == k (mod n), or 0 if no such integer exists.

Views

Author

Keywords

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Formula