login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A328914 Smallest index m such that from the m-th term on, the sequence {k^k mod A192135(n): k >= 0} enters into a cycle. 1
3, 3, 3, 3, 4, 7, 4, 7, 7, 4, 7, 11, 7, 11, 7, 11, 6, 11, 7, 15, 7, 15, 6, 15, 7, 15, 6, 19, 7, 19, 13, 6, 19, 19, 13, 8, 23, 6, 13, 23, 23, 8, 16, 11, 23, 16, 27, 11, 27, 8, 16, 27, 27, 16, 11, 8, 31, 16, 31, 11, 31, 16, 8, 31, 11, 22, 35, 35, 22, 8, 35, 16, 35, 22, 39, 8, 16, 25, 39, 39, 25, 12, 16, 39, 15, 25, 43 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,1

COMMENTS

Let f(n) be the smallest index m such that from the m-th term on, the sequence {k^k mod n: k >= 0} enters into a cycle, then:

(a) if gcd(n1,n2) = 1, then f(n1*n2) = max{f(n1), f(n2)}. For example, f(648) = max{f(8), f(81)} = 4;

(b) f(1) = 0; for primes p, f(p^e) = 1 if e <= p; f(p^e) is the largest s that is no greater than e and that s-1 is divisible by p but not by p^2.

Proof: If we define b(k) = k^k mod p^e if gcd(k,p) = 1, 0 otherwise, it is easy to see that {b(k): k >= 0} is purely periodic. As a result, for every k >= f(p^e), we have either gcd(k,p) = 1 or  p^e | k^k. In other words, let t be the largest number divisible by p such that p^e does not divide t^t, then f(p^e) = t+1.

If p^2 divides t, write t = r*p^2, then v(t^t,p) < v((t+p)^(t+p),p), where t(,p) is the p-adic valuation. This gives r = 0. As a result, f(p^e) is either 1 or a number s such that s-1 is divisible by p but not by p^2. In the latter case, v((s-1)^(s-1),p) = s-1, so s is the largest such number that is no greater than e.

The records in this sequence are {3, 4, 7, 11, 15, 19, 23, ...}

LINKS

Table of n, a(n) for n=1..87.

FORMULA

a(n) = f(A192135(n)), where f is defined in the comment section.

EXAMPLE

A table for f(p^e):

              p

   e  2  3  5  7 11 13

   1  1  1  1  1  1  1

   2  1  1  1  1  1  1

   3  3  1  1  1  1  1

   4  3  4  1  1  1  1

   5  3  4  1  1  1  1

   6  3  4  6  1  1  1

   7  7  7  6  1  1  1

   8  7  7  6  8  1  1

   9  7  7  6  8  1  1

  10  7  7  6  8  1  1

  11 11  7 11  8  1  1

  12 11  7 11  8 12  1

  13 11 13 11  8 12  1

  14 11 13 11  8 12 14

  15 11 13 11 15 12 14

  16 11 16 16 15 12 14

PROG

(PARI) b(p, e) = if(!e, 0, if(e<=p, 1, forstep(k=e, p+1, -1, if(k%p==1&&k%(p^2)!=1, return(k)))))

L=List(); my(lim=12); forprime(p=2, lim, for(n=p+1, lim*log(lim)\log(p), listput(L, p^n))); listsort(L); L \\ generates all terms of A192135 below lim^lim

for(k=1, #L, my(p=factor(L[k])[1, 1], e=factor(L[k])[1, 2]); print1(b(p, e), ", "))

CROSSREFS

Cf. A192135, A328920 (smallest N such that f(N) = n).

Sequence in context: A035936 A006671 A046074 * A295084 A068048 A176994

Adjacent sequences:  A328911 A328912 A328913 * A328915 A328916 A328917

KEYWORD

nonn

AUTHOR

Jianing Song, Oct 31 2019

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified September 25 12:57 EDT 2021. Contains 347654 sequences. (Running on oeis4.)