A321575 Nexus primary pretenders: a(n) is the smallest composite k such that n^k - (n-1)^k == 1 (mod k).

9, 4, 341, 4, 6, 4, 9, 4, 14, 4, 6, 4, 9, 4, 21, 4, 6, 4, 9, 4, 15, 4, 6, 4, 9, 4, 10, 4, 6, 4, 9, 4, 62, 4, 6, 4, 9, 4, 49, 4, 6, 4, 9, 4, 33, 4, 6, 4, 9, 4, 14, 4, 6, 4, 9, 4, 10, 4, 6, 4, 9, 4, 65, 4, 6, 4, 9, 4, 49, 4, 6, 4, 9, 4, 111, 4, 6, 4, 9, 4, 15

Offset: 0

Author

Thomas Ordowski, Nov 13 2018

Keywords

• nonn

Comments

The sequence is bounded, namely a(n) <= 561 (the smallest Carmichael number), since if n^k == n (mod k) and (n-1)^k == n-1 (mod k), then n^k - (n-1)^k == 1 (mod k).

Problem: find all distinct terms of the sequence. Is this sequence periodic like the primary pretenders?

Note that a(n) > 9 if and only if n == 2 (mod 6). We have a(6m+2) = 341, 14, 21, 15, 10, 62, 49, 33, 14, 10, 65, 49, 111, 15, 10, ... for m >= 0. Found a(n) = 561 for the smallest n = 6*70+2 = 422.

From Robert Israel, Nov 27 2018: (Start)

Since a(n) depends only on the residues of n mod k for composites k <= 561, it must be periodic with period at most the lcm of those composites.

Up to n=2*10^6, the last term to appear for the first time is 478 = a(184748).

Conjecture: the only terms of the sequence that are not squarefree are 4, 9 and 49. (End)

Links

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

Crossrefs

Cf. A000790, A108574.

Programs

Maple

Comps:= remove(isprime, [$4..561]):
f:= proc(n) local k;
  for k in Comps do if n&^k - (n-1)&^k - 1 mod k = 0 then return k fi od
end proc:
map(f, [$0..100]); # Robert Israel, Nov 27 2018

Mathematica

a[n_]:=Module[{k=4}, While[PrimeQ[k] || Mod[n^k-(n-1)^k,k]!=1, k++]; k]; Array[a, 100, 0] (* Amiram Eldar, Nov 13 2018 *)

PARI

a(n)=forcomposite(k=4,,Mod(n,k)^k-Mod(n-1,k)^k==1&&return(k)) \\ M. F. Hasler, Nov 13 2018

Formula

a(n) = 4 iff n == 1,3,5 (mod 6), thus n is odd.

a(n) = 6 iff n == 4 (mod 6).

a(n) = 9 iff n == 0 (mod 6).

Extensions

More terms from Amiram Eldar, Nov 13 2018