A121707 -id:A121707 - cp's OEIS frontend

A317358 a(n) is the smallest number k > 1 such that 1^(k-1) + 2^(k-1) + ... + n^(k-1) == n (mod k).

2, 3, 5, 2, 2, 7, 11, 2, 2, 3, 3, 2, 2, 17, 17, 2, 2, 3, 3, 2, 2, 23, 29, 2, 2, 5, 3, 2, 2, 31, 37, 2, 2, 37, 35, 2, 2, 3, 41, 2, 2, 43, 47, 2, 2, 3, 3, 2, 2, 5, 5, 2, 2, 3, 3, 2, 2, 59, 61, 2, 2, 67, 3, 2, 2, 55, 71, 2, 2, 35, 35, 2, 2, 3, 5, 2, 2, 5, 5, 2, 2

Offset: 1

Thomas Ordowski, Jul 26 2018

nonn

a(n) = 2 if and only if n == {0, 1} (mod 4).
a(n) <= A151800(n).
A133906(n) <= a(n) <= A133907(n).
The sequence is unbounded.
Numbers n such that a(n-1) = n are 2, 3, 7, 23, 31, 43, 59, 139, 283, ...
By the Agoh-Giuga conjecture, if a(n-1) = n, then n is a prime.
It seems that if a(n) > n, then a(n) is a prime (the next prime after n).
If a(n) = n, then n is in A121707. These numbers are 35, 143, 187, 215, ...
Conjecture: all composite terms of the sequence are A121707.

Chai Wah Wu, Table of n, a(n) for n = 1..10000 (n = 1..1000 from Seiichi Manyama)
Wikipedia, Agoh-Giuga conjecture

Cf. A133906, A133907, A151800, A121707, A317058, A317357.

a[n_] := Block[{k=2}, While[Mod[Sum[PowerMod[j, k-1, k], {j, n}], k] != Mod[n, k], k++]; k]; Array[a, 81] (* Giovanni Resta, Jul 29 2018 *)

a(n) = for(k=2,oo, if (sum(j=1,n, Mod(j,k)^(k-1)) == n, return (k));); \\ Michel Marcus, Jul 26 2018

def g(n,p,q): # compute (-n + sum_{k=1,n} k^p)  mod q
    c = (-n) % q
    for k in range(1,n+1):
        c = (c+pow(k,p,q)) % q
    return c
def A317358(n):
    k = 2
    while g(n,k-1,k):
        k += 1
    return k # Chai Wah Wu, Jul 30 2018

More terms from Michel Marcus, Jul 26 2018

A316907 Numbers k such that 2^(k-1) == 1 (mod k) and p-1 does not divide k-1 for every prime p dividing k.

Original entry on oeis.org

7957, 23377, 35333, 42799, 49981, 60787, 129889, 150851, 162193, 164737, 241001, 249841, 253241, 256999, 280601, 318361, 452051, 481573, 556169, 580337, 617093, 665333, 722201, 838861, 877099, 1016801, 1251949, 1252697, 1325843, 1507963, 1534541, 1678541, 1826203, 1969417

Offset: 1

Thomas Ordowski, Jul 16 2018

nonn

Numbers k such that 2^k == 2 (mod k) and gcd(k,b^k-b) = 1 for some b > 2.
Problem: are there infinitely many such "anti-Carmichael pseudoprimes"?
All semiprime terms of A316906 are in the sequence; i.e., numbers m in A214305 such that p-1 does not divide q-1, where m = pq and p < q are primes.

			7957 = 73*109 is pseudoprime and 72 does not divide 7956 (of course also 108 does not divide 7956), note that 72 does not divide 108.
617093 = 43*113*127 is the smallest such pseudoprime with more than two prime factors.

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

Subsequence of A001567 and of A316906.

Cf. A121707 (probably "anti-Carmichael numbers": n such that p-1 does not divide n-1 for every prime p dividing n).

Select[Select[Range[2*10^6], PowerMod[2, # - 1, #] == 1 &], Function[k, AllTrue[FactorInteger[k][[All, 1]] - 1, Mod[k - 1, #] != 0 &]]] (* Michael De Vlieger, Jul 20 2018 *)

a(7)-a(34) from Michel Marcus, Jul 16 2018

A316940 Smallest "anti-Carmichael pseudoprime" to base n.

Original entry on oeis.org

35, 7957, 16531, 1247, 17767, 35, 817, 2501, 697, 4141, 2257, 143, 9577, 2257, 4187, 1247, 3991, 221, 7957, 2059, 55, 161, 1027, 115, 403, 475, 247, 4553, 35, 247, 6289, 697, 1853, 35, 1247, 35, 589, 221, 95, 533, 35, 559, 77, 215, 253, 235, 221, 329, 247, 119

Offset: 1

Thomas Ordowski, Jul 17 2018

nonn

a(n) is the smallest k such that n^(k-1) == 1 (mod k) and p-1 does not divide k-1 for every prime p dividing k.

All listed terms are semiprime and squarefree, except a(26) = 475 = 5^2*19.

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

Cf. A121707 (probably "anti-Carmichael numbers": n such that p-1 does not divide n-1 for every prime p dividing n).

Cf. A316907 ("anti-Carmichael pseudoprimes" to base 2).

Table[Block[{k = 2}, While[Nand[PowerMod[n, k - 1, k] == 1, AllTrue[FactorInteger[k][[All, 1]] - 1, Mod[k - 1, #] != 0 &]], k++]; k], {n, 50}] (* Michael De Vlieger, Jul 20 2018 *)

isok(k, n) = {if (!isprime(k) && Mod(n, k)^(k-1) == 1, f = factor(k)[,1]; for (j=1, #f~, if (!((k-1) % (f[j]-1)), return (0));); return (1);); return (0);}
a(n) = {my(k=2); while(!isok(k, n), k++); k;} \\ Michel Marcus, Jul 17 2018

More terms from Michel Marcus, Jul 17 2018

A319386 Semiprimes k = pq with primes p < q such that p-1 does not divide q-1.

Original entry on oeis.org

35, 55, 77, 95, 115, 119, 143, 155, 161, 187, 203, 209, 215, 221, 235, 247, 253, 287, 295, 299, 319, 323, 329, 335, 355, 371, 377, 391, 395, 403, 407, 413, 415, 437, 473, 493, 497, 515, 517, 527, 533, 535, 551, 559, 581, 583, 589, 611, 623, 629, 635, 649, 655, 667, 689, 695, 697, 707, 713, 731

Offset: 1

Thomas Ordowski, Sep 18 2018

nonn

The "anti-Carmichael semiprimes" defined: semiprimes k such that lpf(k)-1 does not divide k-1; then also gpf(k)-1 does not divide k-1.
All the terms are odd and indivisible by 3.
If k is in the sequence, then gcd(k,b^k-b)=1 for some integer b.
These numbers are probably all semiprimes in A121707.

			35 = 5*7 is a term since 5-1 does not divide 7-1.
35 is a term since lpf(35)-1 = 5-1 does not divide 35-1.

Robert Israel, Table of n, a(n) for n = 1..10000

Subsequence of A046388.
Complement of A162730 w.r.t. A006881.
Cf. A001358, A121707.

N:= 1000: # for terms <= N
P:= select(isprime,{seq(i,i=5..N/5,2)}):
S:= {}:
for p in P do
  Qs:= select(q -> q > p and q <= N/p and (q-1 mod (p-1) <> 0), P);
  S:= S union map(`*`,Qs,p);
od:
sort(convert(S,list)); # Robert Israel, Apr 14 2020

spndQ[n_]:=Module[{fi=FactorInteger[n][[All,1]]},PrimeOmega[n]==2 && Length[ fi]==2&&Mod[fi[[2]]-1,fi[[1]]-1]!=0]; Select[Range[800],spndQ] (* Harvey P. Dale, Jun 06 2021 *)

isok(n) = {if ((bigomega(n) == 2) && (omega(n) == 2), my(p = factor(n)[1, 1], q = factor(n)[2, 1]); (q-1) % (p-1) != 0;);}  \\ Michel Marcus, Sep 18 2018

list(lim)=my(v=List(),s=sqrtint(lim\=1)); forprime(q=7,lim\5, forprime(p=5,min(min(q-2,s),lim\q), if((q-1)%(p-1), listput(v,p*q)))); Set(v) \\ Charles R Greathouse IV, Apr 14 2020

A214606 a(n) = gcd(n, 2^n - 2).

Original entry on oeis.org

1, 2, 3, 2, 5, 2, 7, 2, 3, 2, 11, 2, 13, 2, 3, 2, 17, 2, 19, 2, 3, 2, 23, 2, 5, 2, 3, 14, 29, 2, 31, 2, 3, 2, 1, 2, 37, 2, 3, 2, 41, 2, 43, 2, 15, 2, 47, 2, 7, 2, 3, 2, 53, 2, 1, 2, 3, 2, 59, 2, 61, 2, 3, 2, 5, 2, 67, 2, 3, 14, 71, 2, 73, 2, 3, 2, 1, 2, 79

Offset: 1

Alex Ratushnyak, Jul 22 2012

Greatest common divisor of n and 2^n - 2.
a(n)=n iff n=1 or n is prime or n is Fermat pseudoprime to base 2 or even pseudoprime to base 2. - Corrected by Thomas Ordowski, Jan 25 2016
Indices of 1's: A121707 preceded by 1. - False, see A267999.
Numbers n such that a(n) does not equal A020639(n) (the least prime factor of n): A146077.

			a(3) = 3 because 2^3 - 2 = 6 and gcd(3, 6) = 3.
a(4) = 2 because 2^4 - 2 = 14 and gcd(4, 14) = 2.

Charles R Greathouse IV, Table of n, a(n) for n = 1..10000

Cf. A000918, A064535, A121707, A020639, A146077.

import java.math.BigInteger;
public class A214606 {
  public static void main (String[] args) {
    BigInteger c1 = BigInteger.valueOf(1);
    BigInteger c2 = BigInteger.valueOf(2);
    for (int n=0; n<222; n++) {
      BigInteger bn=BigInteger.valueOf(n),pm2=c1.shiftLeft(n).subtract(c2);
      System.out.printf("%s, ", bn.gcd(pm2).toString());
    }
  }
}

[GCD(n, 2^n-2): n in [1..80]]; // Vincenzo Librandi, Jan 26 2016

seq(igcd(n, (2&^n - 2) mod n), n=1 .. 1000); # Robert Israel, Jan 26 2016

Table[GCD[n, 2^n - 2], {n, 1, 59}] (* Alonso del Arte, Jul 22 2012 *)

a(n)=gcd(n,lift(Mod(2,n)^n-2)) \\ Charles R Greathouse IV, May 29 2014

A263022 a(n) = gcd(n, 1^(n-1) + 2^(n-1) + ... + (n-1)^(n-1)) for n > 1.

Original entry on oeis.org

1, 1, 4, 1, 3, 1, 8, 3, 5, 1, 12, 1, 7, 5, 16, 1, 9, 1, 20, 7, 11, 1, 24, 5, 13, 9, 28, 1, 15, 1, 32, 11, 17, 35, 36, 1, 19, 13, 40, 1, 21, 1, 44, 3, 23, 1, 48, 7, 25, 17, 52, 1, 27, 55, 56, 19, 29, 1, 60, 1, 31, 21, 64, 13, 33, 1, 68, 23, 35, 1, 72, 1, 37, 25, 76, 77, 39, 1, 80, 27, 41, 1, 84, 17, 43, 29, 88, 1, 45, 13, 92, 31, 47, 95, 96

Offset: 2

Thomas Ordowski, Oct 07 2015

nonn

a(n) = 1 if and only if n is a prime or n is a Carmichael number.
a(n) is divisible by 4 if n is divisible by 4, otherwise a(n) is odd. - Robert Israel, Oct 08 2015
a(n) = n iff 4|n or n = 35, 55, 77, 95; A121707 ?
a(5005) = 11: this is the first case where a(n) is prime and A001222(n) > 3. - Altug Alkan, Oct 08 2015

Robert Israel, Table of n, a(n) for n = 2..10000

Cf. A002997 (see my Oct 09 2013 comment).

f:= n -> igcd(n, add(j &^(n-1) mod n, j=1..n-1)):
seq(f(n), n=2..1000); # Robert Israel, Oct 08 2015

Table[GCD[n, Total@ Map[#^(n - 1) &, Range[n - 1]]], {n, 2, 96}] (* Michael De Vlieger, Oct 08 2015 *)

vector(100, n, gcd(n+1, sum(k=1, n, k^n))) \\ Altug Alkan, Oct 08 2015

a(4n) = 4n.

a(n) = gcd(A031971(n-1), n). - Michel Marcus, Oct 08 2015

A300762 Numbers k > 1 such that 2^k == 2 (mod k) and gcd(k, 3^k - 3) = 1.

Original entry on oeis.org

35333, 42799, 49981, 60787, 150851, 162193, 164737, 241001, 253241, 256999, 280601, 452051, 481573, 556169, 617093, 665333, 722201, 838861, 1016801, 1252697, 1507963, 1534541, 1678541, 1826203, 2134277, 2269093, 2304167, 2313697, 2537641, 2617451, 2811271

Offset: 1

Thomas Ordowski, Aug 15 2018

nonn

Numbers k > 1 such that 2^(k-1) == 1 (mod k) and gcd(k, 3^(k-1)-1) = 1.

Are there infinitely many such "anti-Carmichael pseudoprimes (2,3)"?

Subsequence of A001567 and of A316907 and probably of A121707.

Select[Range[2 10^6], PowerMod[2, #, #] == 2 && GCD[#, # + PowerMod[3, #, #] - 3] == 1 &] (* Giovanni Resta, Aug 18 2018 *)

isok(k) = (k != 1) && (Mod(2, k)^k == Mod(2, k)) && (gcd(k, 3^k - 3) == 1); \\ Michel Marcus, Aug 15 2018

More terms from Michel Marcus, Aug 15 2018

More terms from Giovanni Resta, Aug 18 2018

A308963 Lerch pseudoprimes: composite numbers m such that Sum_{k=1..m-1} k^{m-1} - (m-1)! == m (mod m^2).

Original entry on oeis.org

77, 161, 2261, 12839, 14231, 18668831, 1591100357

Offset: 1

Amiram Eldar and Thomas Ordowski, Jul 03 2019

According to Lerch's congruence (1905), if p is an odd prime, then Sum_{k=1..p-1} k^(p-1) - (p-1)! == p (mod p^2).
Equivalently, numbers m > 4 such that Sum_{k=1..m-1} k^(m-1) == m (mod m^2).
Equivalently, numbers m > 1 such that m*B_{m-1} == m (mod m^2), where B_k is the k-th Bernoulli number.
Equivalently, terms m of A121707 such that B_{m-1} == 1 (mod m).
Equivalently, numbers m > 1 such that A027641(m-1) == A027642(m-1) (mod m).
If m is a Lerch pseudoprime, then p-1 does not divide m-1 for every prime divisor p of m.
From M. F. Hasler, Jul 22 2019: (Start)
The Lerch primes A197632 satisfy Lerch's congruence "even" modulo p^3.
Up to a(7) all terms are either multiples of 7 or of 37, but not both. Will this pattern prevail?
We also note: a(1) = 7*11; a(2) = 7*(2*11 + 1) = a(1)/11*23; a(3) = 7*(2*7*23 + 1) = a(2)/23*17*19, a(5) = a(3)/17*107, i.e., a term in this subsequence has all but one of the prime factors of the preceding one. The subsequence (a(4), a(6), ...?) of terms divisible by 37 so far consists of semiprimes and therefore also has this property. (End)

Mathias Lerch, Zur Theorie des Fermatschen Quotienten (a^(p-1)-1)/p = q(a), Mathematische Annalen, Vol. 60, No. 4 (1905), pp. 471-490.
Jonathan Sondow, Lerch quotients, Lerch primes, Fermat-Wilson quotients, and the Wieferich-non-Wilson primes 2, 3, 14771, In: Nathanson M. (eds) Combinatorial and Additive Number Theory. Springer Proceedings in Mathematics & Statistics, Vol. 101, Springer, New York, NY, 2014, pp. 243-255. Preprint: arXiv:1110.3113 [math.NT].

A subsequence of A191677 and A121707.

Cf. A027641, A027642, A197630, A197632.

s={}; Do[If[CompositeQ[n] && Mod[Sum[PowerMod[k, n-1, n^2], {k, 1, n-1}] - (n-1)! - n, n^2] == 0, AppendTo[s, n]],{n,1,2500}] ; s

is_A308963(m)={sum(k=1,m-1,Mod(k,m^2)^(m-1))==m&&!isprime(m)&&m>4}
forcomposite(m=1,,is_A308963(m)&&print1(m",")) \\ Slow beyond 10000. - M. F. Hasler, Jul 22 2019

a(6)-a(7) from Max Alekseyev, Jul 09 2019

A316111 a(n) is the smallest k > 1 such that gcd(k, n^k - n) = 1, for n > 1.

Original entry on oeis.org

35, 35, 77, 77, 143, 55, 55, 77, 119, 119, 35, 55, 187, 143, 77, 35, 35, 77, 143, 247, 95, 35, 77, 77, 77, 55, 55, 143, 77, 77, 35, 35, 247, 143, 143, 35, 35, 77, 77, 143, 55, 95, 119, 119, 77, 35, 55, 143, 143, 77, 35, 35, 119, 299, 221, 55, 35, 77, 77, 77, 55, 55, 187, 119

Offset: 2

Thomas Ordowski, Aug 13 2018

nonn

Conjecture: all the terms are in A121707. If k is a term, then k is an "anti-Carmichael number": p-1 does not divide k-1 for every prime p dividing k.
The sequence is unbounded, since a(m!) > m.
Prediction: a(n) < n for all sufficiently large n.
GCD(n, a(n)) = 1. a(n) is odd. Is a(n) squarefree? - David A. Corneth, Aug 13 2018

Cf. A121707, A267999.

a(n) = {my(k=2); while (gcd(k, n^k - n) != 1, k++); k;} \\ Michel Marcus, Aug 13 2018

a(n) = {my(k=3); while (gcd(k, n^k - n) != 1, k+=2; while(gcd(n, k) > 1, k+=2)); k} \\ David A. Corneth, Aug 13 2018

More terms from Michel Marcus, Aug 13 2018

A316348 a(n) is the smallest k > 1 such that gcd(k, m^k - m) = 1 for all m = 2,...,n.

Original entry on oeis.org

35, 35, 77, 77, 143, 143, 143, 143, 299, 299, 323, 323, 323, 323, 437, 437, 667, 667, 667, 667, 899, 899, 899, 899, 899, 899, 1457, 1457, 1739, 1739, 1739, 1739, 1739, 1739, 1763, 1763, 1763, 1763, 2021, 2021, 2491, 2491, 2491, 2491, 3127, 3127, 3127, 3127, 3127

Offset: 2

Thomas Ordowski, Aug 13 2018

nonn

Conjecture: all the terms are in A121707.
From David A. Corneth, Aug 13 2018: (Start)
GCD(n, a(n)) = 1. a(n) is odd.
Is a(n) squarefree?
a(n+1) >= a(n) by definition. (End)
It seems that a(prime(n+1)-1) > a(prime(n)-1) for n > 1. - Thomas Ordowski, Aug 13 2018

Michel Marcus, Table of n, a(n) for n = 2..306

Cf. A121707, A267999, A316111.

isok(k, n)= {for (m=2, n, if (gcd(k, m^k - m) != 1, return (0));); return(1);}
a(n) = {my(k=2); while (! isok(k, n), k++); k;} \\ Michel Marcus, Aug 13 2018

Conjecture: a(n) ~ n^2.

More terms from Michel Marcus, Aug 13 2018

cp's OEIS Frontend

A317358 a(n) is the smallest number k > 1 such that 1^(k-1) + 2^(k-1) + ... + n^(k-1) == n (mod k).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Python

Extensions

A316907 Numbers k such that 2^(k-1) == 1 (mod k) and p-1 does not divide k-1 for every prime p dividing k.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Extensions

A316940 Smallest "anti-Carmichael pseudoprime" to base n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A319386 Semiprimes k = pq with primes p < q such that p-1 does not divide q-1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

A214606 a(n) = gcd(n, 2^n - 2).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Java

Magma

Maple

Mathematica

PARI

A263022 a(n) = gcd(n, 1^(n-1) + 2^(n-1) + ... + (n-1)^(n-1)) for n > 1.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A300762 Numbers k > 1 such that 2^k == 2 (mod k) and gcd(k, 3^k - 3) = 1.

Views

Author

Keywords

Comments

Crossrefs