A063994 -id:A063994 - cp's OEIS frontend

A211455 The number of bases b for which A181780(n) is a Fermat pseudoprime.

2, 2, 2, 2, 2, 2, 2, 6, 4, 2, 2, 2, 2, 2, 14, 4, 2, 2, 2, 2, 2, 14, 2, 34, 2, 2, 2, 14, 2, 2, 2, 6, 2, 8, 2, 2, 2, 2, 2, 34, 2, 2, 2, 14, 2, 2, 14, 2, 2, 2, 2, 14, 10, 2, 2, 10, 4, 2, 2, 14, 4, 2, 2, 8, 6, 2, 2, 2, 14, 2, 2, 2, 2, 2, 34, 2, 14, 6, 38, 6, 2, 2

Offset: 1

T. D. Noe, Apr 13 2012

nonn

Sequences A211456 and A211457 give the smallest and largest bases b; A211458 lists all bases.

Every term in this sequence is even. - Geoffrey Critzer, Apr 08 2015

Cf. A181780, A211456, A211457, A211458.

t = {}; n = 1; While[Length[t] < 100, n++; If[! PrimeQ[n], s = Select[Range[2, n-2], PowerMod[#, n-1, n] == 1 &]; If[s != {}, AppendTo[t, {n, Length[s], s}]]]]; Transpose[t][[2]]
f[n_] := If[ PrimeQ@ n, {}, Count[ Table[ PowerMod[k, n - 1, n], {k, 2, n - 2}], 1]] /. {0 -> {}}; Array[f, 237] // Flatten (* Robert G. Wilson v, Apr 08 2015 *)

a(n) = A063994(m) - 2 for odd m in A181780. a(n) = A063994(m) - 1 for even m in A181780. - Thomas Ordowski, Dec 13 2013

A191311 Numbers n such that exactly half of the a such that 0

Original entry on oeis.org

4, 6, 15, 91, 703, 1891, 2701, 11305, 12403, 13981, 18721, 23001, 30889, 38503, 39865, 49141, 68101, 79003, 88561, 88831, 91001, 93961, 104653, 107185, 137149, 146611, 152551, 157641, 176149, 188191, 204001, 218791, 226801, 228241

Offset: 1

Jason Holt, Jun 04 2011

Values of n for which half the witnesses in the Fermat primality test are false.
When n=pq with p,q=2p-1 prime, a^(n-1) = 1 (mod p) iff a is a quadratic residue mod q. So A129521 is a subsequence. - Gareth McCaughan, Jun 05 2011
From Robert G. Wilson v, Aug 13 2011: (Start)
Number of terms less than 10^n: 2, 4, 5, 7, 22, 60, 129, 303, 690, 1785, …, .
In reference to the numbers in the b-file: (1) number of terms which have k>0 prime factors: 1, 1058, 139, 512, 339, 102, 6; (2) about half of the terms, 1058, are members of A129521, those which have just two prime factors; (3) except for the first term, all terms are squarefree, except for the first two terms, all terms are odd; and (4) most terms, more than 98.5%, are congruent to 1 modulo 6. (End)

David W. Wilson and Robert G. Wilson v, Table of n, a(n) for n = 1..2157
While exploring Carmichael numbers, I noticed a few values on the chart on this page for which exactly half of the relatively prime witnesses to the Fermat primality test were false witnesses.

A063994 gives the number of false witnesses for every n.

A129521 is a subsequence. See also A191592.

fQ[n_] := Block[{pf = First /@ FactorInteger@ n}, 2Times @@ GCD[n - 1, pf - 1] == n*Times @@ (1 - 1/pf)]; Select[ Range@ 250000, fQ] (* Robert G. Wilson v, Aug 08 2011 *)

import math
for x in range(2, 1000):
  false_witnesses = 0
  relatively_prime_values = 0
  for y in range(x):
    if math.gcd(y, x) == 1:
      relatively_prime_values += 1
    if (pow(y, x-1, x) == 1):
      false_witnesses += 1
  if false_witnesses * 2 == relatively_prime_values:
    print(x, "is a Fermat Half-Prime")

Integers, n, such that A063994(n) = 2*A000010(n). - Robert G. Wilson v, Aug 13 2011

Edited by N. J. A. Sloane, Jun 07 2011. I made use of a more explicit definition due to Gareth McCaughan, Jun 05 2011.

A329726 Number of witnesses for Solovay-Strassen primality test of 2*n+1.

Original entry on oeis.org

2, 4, 6, 2, 10, 12, 2, 16, 18, 2, 22, 4, 2, 28, 30, 2, 2, 36, 2, 40, 42, 4, 46, 6, 2, 52, 2, 2, 58, 60, 2, 8, 66, 2, 70, 72, 2, 2, 78, 2, 82, 8, 2, 88, 18, 2, 2, 96, 2, 100, 102, 8, 106, 108, 2, 112, 2, 4, 2, 10, 2, 4, 126, 2, 130, 18, 2, 136, 138, 2, 2, 8, 2

Offset: 1

Amiram Eldar, Nov 20 2019

nonn

Number of bases b, 1 <= b <= 2*n, such that GCD(b, 2*n+1) = 1 and b^n == (b / 2*n+1) (mod 2*n+1), where (b / 2*n+1) is a Jacobi symbol.
If 2*n+1 is composite then it is the number of bases b, 1 <= b <= 2*n, in which 2*n+1 is an Euler-Jacobi pseudoprime.
Differs from A071294 from n = 22.

			a(1) = 2 since there are 2 bases b in which 2*1 + 1 = 3 is an Euler-Jacobi pseudoprime: b = 1 since GCD(1, 3) = 1 and 1^1 == (1 / 3) == 1 (mod 3), and b = 2 since GCD(2, 3) = 1 and 2^1 == (2 / 3) == -1 (mod 3).

Paulo Ribenboim, The Little Book of Bigger Primes, 2nd ed., Springer-Verlag, New York, 2004, p. 96.

Amiram Eldar, Table of n, a(n) for n = 1..10000
Louis Monier, Evaluation and comparison of two efficient primality testing algorithms, Theoretical Computer Science, Vol. 11 (1980), pp. 97-108.
Eric Weisstein's World of Mathematics, Euler-Jacobi Pseudoprime.
Wikipedia, Euler-Jacobi pseudoprime.
Wikipedia, Solovay-Strassen primality test.

Cf. A006093, A007324, A007814, A047713, A063994, A071294.

v[n_] := Min[IntegerExponent[#, 2]& /@ (FactorInteger[n][[;;, 1]] - 1)];
pQ[n_, p_] := OddQ[IntegerExponent[n, p]] && IntegerExponent[p-1, 2] < IntegerExponent[n-1, 2];
psQ[n_] := AnyTrue[FactorInteger[n][[;;, 1]], pQ[n, #] &];
delta[n_] := If[IntegerExponent[n-1, 2] == v[n], 2, If[psQ[n], 1/2, 1]];
a[n_] := delta[n] * Module[{p = FactorInteger[n][[;;, 1]]}, Product[GCD[(n-1)/2, p[[k]]-1], {k, 1, Length[p]}]];
Table[a[n], {n, 3, 147, 2}]

a(n) = delta(n) * Product_{p|n} gcd((n-1)/2, p-1), where delta(n) = 2 if nu(n-1, 2) = min_{p|n} nu(p-1, 2), 1/2 if there is a prime p|n such that nu(p, n) is odd and nu(p-1, 2) < nu(n-1, 2), and 1 otherwise, where nu(n, p) is the exponent of the highest power of p dividing n.

a(p) = p-1 for prime p.

A340189 a(n) = n + A340187(n).

Original entry on oeis.org

2, 1, 1, 4, 1, 9, 1, 8, 11, 17, 1, 11, 1, 25, 27, 16, 1, 13, 1, 17, 41, 41, 1, 24, 37, 49, 25, 21, 1, 1, 1, 32, 69, 65, 79, 40, 1, 73, 83, 40, 1, -7, 1, 35, 21, 89, 1, 48, 79, 17, 111, 39, 1, 61, 131, 60, 125, 113, 1, 83, 1, 121, 27, 64, 145, -27, 1, 53, 153, -49, 1, 71, 1, 145, 23, 57, 193, -31, 1, 80, 83, 161, 1, 131

Offset: 1

Antti Karttunen, Dec 31 2020

sign

Antti Karttunen, Table of n, a(n) for n = 1..8191
Antti Karttunen, Data supplement: n, a(n) computed for n = 1..65537

Cf. A063994, A318828, A340187, A340188.

Cf. also A318833.

up_to = 65537;
A063994(n) = { my(f=factor(n)); prod(i=1, #f~, gcd(f[i, 1]-1, n-1)); };
DirInverse(v) = { my(u=vector(#v)); u[1] = (1/v[1]); for(n=2, #v, u[n] = -sumdiv(n, d, if(dA063994(n)));
A340187(n) = v340187[n];
A340189(n) = (n+A340187(n));

a(n) = n + A340187(n).

a(n) = A340188(n) + A318828(n).

A175101 The number of bases b for which the odd squarefree semiprime A046388(n) is a Fermat pseudoprime.

Original entry on oeis.org

2, 2, 2, 2, 2, 2, 2, 2, 14, 2, 2, 14, 2, 34, 2, 2, 2, 2, 2, 2, 2, 34, 2, 2, 14, 2, 2, 2, 2, 2, 14, 2, 2, 2, 14, 2, 2, 2, 34, 2, 14, 2, 2, 34, 2, 2, 34, 14, 2, 2, 2, 2, 2, 34, 2, 14, 2, 2, 2, 2, 2, 2, 2, 2, 98, 2, 14, 2, 14, 2, 2, 2, 2, 34, 2, 2, 2, 2, 2, 34, 2, 14, 2, 98, 2, 34, 2, 2, 142, 14, 2, 14, 2

Offset: 1

T. D. Noe, Dec 02 2010

nonn

A number x is a Fermat pseudoprime for base b if b^(x-1) = 1 (mod x).
Comment from Karsten Meyer: (Start) Each term pq of the sequence A046388 is at least a Fermat pseudoprime to the two bases which have the property that |l*p - m*q| = 2 and b is the number between l*p and m*q. There are no more bases of this form below pq.
There may exist other bases smaller than pq, but just two bases have the property that they are direct neighbors of a multiple of p and a multiple of q. For example, 39=3*13 is a Fermat pseudoprime to the bases 14 and 25 because 14 is the number between 13 and 3*5 and 25 is the number between 3*8 and 2*13.
91=7*13 is a Fermat pseudoprime to the bases 27 and 64 because 27 is the number between 2*13 and 4*7 and 64 is the number between 9*7 and 5*13. For 91, the bases 3, 4, 9, 10, 12, 16, 17, 22, 23, 25, 29, 30, 36, 38, 40, 43, 48, 51, 53, 55, 61, 62, 66, 68, 69, 74, 75, 79, 81, 82, 87, 88 also exist, but neither of them lies between a multiple of 7 and a multiple of 13. (End)
Looking at odd squarefree semiprimes less than 10000, it appears that the number of bases is always of the form 2(2k^2-1), which is A060626 and twice A056220. Using the formula in A063994, the number of bases for pq (including bases 1 and pq-1) is gcd(p-1,pq-1) * gcd(q-1,pq-1).

			For A046388(1) = 15, the bases b in the range [2,13] are 4 and 11. So a(1) = 2.

Amiram Eldar, Table of n, a(n) for n = 1..10000

Cf. A046388, A063994 (number of bases b for which b^(n-1) = 1 (mod n)).

a(n) = A063994(A046388(n)) - 2.

A318840 a(n) = phi(n) - Product_{primes p dividing n} gcd(p-1, n-1).

Original entry on oeis.org

0, 0, 0, 1, 0, 1, 0, 3, 4, 3, 0, 3, 0, 5, 4, 7, 0, 5, 0, 7, 8, 9, 0, 7, 16, 11, 16, 9, 0, 7, 0, 15, 16, 15, 20, 11, 0, 17, 20, 15, 0, 11, 0, 19, 16, 21, 0, 15, 36, 19, 28, 21, 0, 17, 36, 23, 32, 27, 0, 15, 0, 29, 32, 31, 32, 15, 0, 31, 40, 21, 0, 23, 0, 35, 36, 33, 56, 23, 0, 31, 52, 39, 0, 23, 48, 41, 52, 39, 0, 23, 36, 43, 56, 45, 68, 31

Offset: 1

Antti Karttunen, Sep 11 2018

nonn

Antti Karttunen, Table of n, a(n) for n = 1..65537

Cf. A000010, A063994, A318828, A318830.

A063994(n) = { my(f=factor(n)[,1]); prod(i=1, #f, gcd(f[i]-1, n-1)); };
A318840(n) = (eulerphi(n) - A063994(n));

a(n) = A000010(n) - A063994(n).

a(n) = A318828(n) - A051953(n).

A340148 a(n) = Product_{distinct primes p dividing n} gcd(q-1, A003961(n)-1), where q = A151800(p), the next prime larger than p.

Original entry on oeis.org

1, 2, 4, 2, 6, 4, 10, 2, 4, 4, 12, 8, 16, 4, 4, 2, 18, 4, 22, 4, 4, 4, 28, 4, 6, 4, 4, 4, 30, 16, 36, 2, 16, 4, 4, 8, 40, 4, 16, 4, 42, 16, 46, 8, 12, 4, 52, 8, 10, 4, 4, 16, 58, 4, 36, 4, 4, 4, 60, 8, 66, 4, 4, 2, 4, 8, 70, 4, 16, 40, 72, 4, 78, 4, 8, 4, 4, 8, 82, 4, 4, 4, 88, 8, 36, 4, 4, 4, 96, 16, 4, 8, 16

Offset: 1

Antti Karttunen, Dec 30 2020

nonn

Prime shifted analog of A063994.

Antti Karttunen, Table of n, a(n) for n = 1..8191
Antti Karttunen, Data supplement: n, a(n) computed for n = 1..65537
Index entries for sequences computed from indices in prime factorization

Cf. A003961, A003972, A063994, A340147.

A003961(n) = { my(f = factor(n)); for(i=1, #f~, f[i, 1] = nextprime(f[i, 1]+1)); factorback(f); };
A063994(n) = { my(f=factor(n)[,1]); prod(i=1, #f, gcd(f[i]-1, n-1)); };
A340148(n) = A063994(A003961(n));

A340148(n) = { my(f=factor(n)[,1], u=A003961(n)); prod(i=1, #f, gcd(nextprime(1+f[i])-1, u-1)); };

A340148(n) = { my(u=A003961(n), f=factor(u)[,1]); prod(i=1, #f, gcd(f[i]-1, u-1)); };

a(n) = A063994(A003961(n)).

a(n) = A003972(n) / A340147(n).

A348259 Number of bases 1

Original entry on oeis.org

0, 0, 1, 0, 3, 0, 5, 0, 1, 0, 9, 0, 11, 0, 3, 0, 15, 0, 17, 0, 3, 0, 21, 0, 3, 0, 1, 2, 27, 0, 29, 0, 3, 0, 3, 0, 35, 0, 3, 0, 39, 0, 41, 0, 7, 0, 45, 0, 5, 0, 3, 2, 51, 0, 3, 0, 3, 0, 57, 0, 59, 0, 3, 0, 15, 4, 65, 0, 3, 2, 69, 0, 71, 0, 3

Offset: 1

Robert G. Wilson v, Oct 08 2021

This is a count of Fermat Pseudoprimes.
Numbers not in the sequence: 13, 25, 33, 37, 43, 49, 53, 61, 67, 73, 75, 83, 85, 89, 91, 93, 97, ..., .
First occurrence of k=0..: 1, 3, 28, 5, 66, 7, 232, 45, 190, 11, 276, 13, 1106, -1, 286, 17, 1854, ..., .

			a(3) = 1 since 2^3 = 8 == 2 (mod 3);
a(5) = 2 since {2, 3, 4}^5 = {32, 243, 1024} == {2, 3, 4} (mod 5);
a(9) = 1 since 8^9 = 134217728 == 8;
a(15) = 3 since {4, 11, 14}^15 = {1073741824, 4177248169415651, 155568095557812224} == {4, 11, 14} (mod 15); etc.

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

Cf. A000040, A039772, A063994.

a[n_] := Length@ Select[Range[2, n -1], CoprimeQ[#, n] && PowerMod[#, n, n] == # &]; Array[a, 75]

a(n) = sum(b=2, n-1, if (gcd(b, n)==1, Mod(b, n)^n == b)); \\ Michel Marcus, Oct 09 2021

a(n) = A063994(n)-1.
a(2n) must be even. Those that exceed 0 are A039772.
a(p) = p-2 iff p is a prime (A000040).
a(2n-1) < 2n-3 iff 2n-1 is composite and a(2n-1) is odd.
a(n) = (Product_{primes p|n} gcd(p-1, n-1)) - 1. - Jianing Song, Nov 20 2021

cp's OEIS Frontend

A211455 The number of bases b for which A181780(n) is a Fermat pseudoprime.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

A191311 Numbers n such that exactly half of the a such that 0

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Python

Formula

Extensions

A329726 Number of witnesses for Solovay-Strassen primality test of 2*n+1.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

Formula

A340189 a(n) = n + A340187(n).

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Formula

A175101 The number of bases b for which the odd squarefree semiprime A046388(n) is a Fermat pseudoprime.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A318840 a(n) = phi(n) - Product_{primes p dividing n} gcd(p-1, n-1).

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Formula

A340148 a(n) = Product_{distinct primes p dividing n} gcd(q-1, A003961(n)-1), where q = A151800(p), the next prime larger than p.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

PARI

PARI

Formula

A348259 Number of bases 1

Views

Author

Keywords

Comments

Examples